Comp SciNotes – Recursion

Previously we have discussed the fundamental control mechanisms of sequence, alternation (if-else), and iteration (while). Recursion is another control mechanism. Sometimes problems are stated in a recursive fashion, and a program that solves the problem is most easily written using recursion.

  • There are two parts to Recursion:
  • If the problem is easy, solve it immediately.
  • If the problem can't be solved immediately, divide it into easier problems, then solve the easier problems.

Forget programming for a while. Think about a real-world problem that does not involve computers:

Example 1: It is the day after Thanksgiving and the only parking spot you can find at the shopping mall is far from the entrance (horrors!) How do you get from your car to the mall?

Answer: A journey of a 1000 yards begins with a single step.

The instructions: a journey of a 1000 yards begins with a single step tell how to reduce the size of the problem. The problem is how to cross the parking lot. After taking a single step, the problem is slightly smaller.

Of course, now you reduce the size of the new problem by taking yet another step. Before long, the problem is so reduced in size that it can be solved in one step

Here is the solution in more detail: (Think two parts to Recursion)

  1. If you are one step from the mall, take that step and you are done.
  2. If you are further than one step from the mall, divide the distance into two parts:
  3. a single step, and
  4. the remaining distance.

Now take a step and then cross the remaining distance.

The over-all strategy is to find some easily applied action that breaks the problem into smaller pieces. Some of the pieces can be dealt with immediately; others may need to be further broken up.

Example 2: Say that you wish to divide a line into 16 equal pieces.

What is the first thing that you do? Answer: Divide the line in half. Now you have two lines, each half as small as the original:

The problem "divide the line into 16 equal pieces" has been transformed into two smaller problems: "divide each of two lines into 8 equal pieces."

The two halves of the original line are divided into two, which results in four lines:

We don't have the required 16 equal divisions, so the process is applied to each of the quarter-sized lines:

Now there are 8 pieces. Apply the process to each of those pieces to get:

Recursion in Java

The total number of pins in a triangular arrangement is called a triangle number. (Think of how bowling pins are arranged for example.) The total number of pins in a triangular arrangement of 5 rows is 5 plus the number of pins in 4 rows. Let us call this number Triangle(5).

Triangle Numbers
Rows / Triangle(Rows) / Formula
1 / base case
2 / 2 + Triangle(1)
3 / 3 + Triangle(2)
4 / 4 + Triangle(3)
5 / 5 + Triangle(4)
6 / 6 + Triangle(5)

The table shows values of the Triangle() function. For example, Triangle(4) = 10. But it stops at seven. What is Triangle(12)?

We have figured out that the following is true:

totalnumber of pins inn rows = n + total number of pins inn-1 rows (this is recursively defined)

This can be written as a formula:

Triangle( n ) = n + Triangle(n - 1 )

So the number of pins in a 12 row arrangement is 12 + number of pins in 11 rows.

This keeps on going. Each round divides the problem into an integer and a problem that is smaller by one. Eventually you reach the end:

number of pins in 12 rows = 12 + number of pins in 11 rows

number of pins in 11 rows = 11 + number of pins in 10 rows

. . .

number of pins in 3 rows = 3 + number of pins in 2 rows

number of pins in 2 rows = 2 + number of pins in 1 row

= 2 + 1

The number of pins in 1 row is called a base case. A base case is a problem that can solved immediately. In this example, the number of pins in 1 row is 1. In terms of the two parts to recursion it is:

  1. Triangle( 1 ) = 1 (If the problem is easy, solve it immediately.)
  2. Triangle(n ) = n + Triangle(n -1 ) (If the problem can't be solved immediately, divide it into smaller problems, then: Solve the smaller problems by applying this procedure to each of them.)

Here is our solution for triangle numbers:

Triangle( 1 ) = 1

Triangle(n) = n + Triangle(n -1 )

Here is another example, calculating Triangle( 5 ):

triangle( 5 ) = 5 + triangle( 4 )

= 5 + ( 4 + triangle( 3 ) )

= 5 + ( 4 + ( 3 + triangle( 2 ) ))

= 5 + ( 4 + ( 3 + ( 2 + triangle( 1 ) )))

= 5 + ( 4 + ( 3 + ( 2 + 1 )))

= 5 + ( 4 + ( 3 + 3) )

= 5 + ( 4 + 6 )

= 5 + 10

= 15

And here is a Java method that does this calculation:

int triangle( int n )

{

if ( n == 1 )

return 1;

else

returnn + triangle( n-1 );

}

The Java code is similar to our solution of Triangle(). The if statement has been added so that the base case is selected when it is needed. You may want to copy the method into BlueJ and use the debugger to trace through the method calls. Below is a pictorial representation of Triangle(5) and its return.

Recursion is useful because sometimes a problem is naturally recursive. Then all you need to do is match it with Java code. But recursion does not add any fundamental power to Java.

Any method that is written using recursion can be written using iteration. Any method that is written using iteration can be written using recursion.

A computer programming language needs to include only one of iteration or recursion to be as powerful as any other programming language. Some languages (such as early FORTRAN) have only iteration. Other languages (such as early LISP) have only recursion. Most modern languages have both, because both are convenient.

Additional Example:

You have probably seen the factorial function before. It is defined for all integers greater or equal to zero:

factorial( 0 ) = 1

factorial(N ) = n * factorial( n-1 )

For example,

factorial( 5 ) = 5 * factorial( 4 )

= 5 * ( 4 * factorial( 3 ) )

= 5 * ( 4 * (3 * factorial( 2 ) ) )

= 5 * ( 4 * (3 * (2 * factorial( 1 ) ) ) )

= 5 * ( 4 * (3 * (2 * ( 1 * factorial( 0 ) ) ) ) )

= 5 * ( 4 * (3 * (2 * ( 1 * 1 ) ) ) )

= 5 * 4 * 3 * 2 * 1 * 1

= 120

Oftenfactorial(n) is writtenN!

Examine the definition and check that it includes both of the two parts of a recursive definition. Here is the code in Java:

int factorial( int n )

{

if ( n == 0 )

return 1;

else

returnn * factorial( n-1 ) ;

}

When the base case is reached, return values start being passed up the chain. After an activation has returned a value to its caller it is no longer active.

All that you need to do to write a recursive method is to establish the base case(s) and the recursive rule and then translate them into Java.