CSE 130 Lab notes

Recursion

Goals:

Understand that recursion means "self referencing"
- A recursive method can call itself
Recognize problems that are suited to being solved recursively:
- Problems that have subproblems similar to the original one
- Example: factorial, power, definition of an expression
Know how to write a recursive method:
1. Consider the base case(s)
2. For other cases, make a recursive call ("leap of faith")
  which must make progress towards the base case.
Know how to rewrite a recursive method non-recursively by using a loop and vice versa
Visualize the recursive process in terms of a "call stack"

A recursive method: factorial(n)

Recall the factorial function, which is defined for nonnegative integers (0, 1, 2, ...):

        n! = n * (n - 1) * (n - 2) *   ... * 1 
        6! = 6 *    5    *    4    * 3 * 2 * 1

Note that the solution to the main problem (6!) contains a subproblem with a similar form (5!).

         6! = 6 * 5!
         5! = 5 * 4!
         4! = 4 * 3!
         3! = 3 * 2!
         2! = 2 * 1!
         1! = 1 * 0!
         0! = 1

We will write a recursive Java method for factorial. We'll assume that the input is always valid (a nonnegative integer). Our first attempt to write a recursive Java method might look like this:

        int fact(int n){
            return (n * fact(n-1));
        }

If we try it, we get this:

Welcome to DrJava.
> Recursion.fact(6)
java.lang.StackOverflowError:       
>

Here we get an error because we have a situation similar to an infinte loop - the method keeps calling itself indefinitely. Just like we have to make sure that our loops don't loop infinitely, we need to make sure that our recursive methods don't call themselves infinitely.

We need to consider the base case. This is the case that causes the recursion to stop.

For factorial, we reach the base case when n has what value?

This brings up one of the tricky aspects of writing recursive functions:

When writing a recursive method we typically write the code for the base case first, at the top of the method.
However in a series of recursive calls, the code pertaining to the base case is executed last.

Here's a correct version of the factorial method:

   int fact(int n) {
      if (n == 0)         // base case
         return 1;
      else
         return n * fact(n - 1); // recursive "leap of faith" that
                                 // makes progress towards the base case
      }

When correct code for the base case is added, we get the following:

 
   > R.fact(0)
   1
   > R.fact(3)
   6
   > fact(6)
   720

Exercises

For the following exercises, rewrite each method in the R.java that is written using a loop as a recursive method which behaves the same way.

Method Name	Description	Recursive Method Name	Hints
R.pow()	raises a number to a power	R.powR()	Remember that the result of raising any number to the power of 0 is 1.
R.fib()	returns the nth number in the Fibonacci sequence.	R.fibR()	The recursive method is much shorter and simpler than the supplied one. See the comments in the fib() method header which describe the fibonacci sequence, and "suggests" that the next number in the series can be computed by doing two recursive calls.
R.sumNums()	sums the integers in an array	R.sumNumsR()	Write an additional private "helper method" that does the bulk of the work. Hint: pass the array and an array index to the helper method. Two arguments to the helper method are sufficient. But for practice with using an "accumulator", try writing another version of the helper method that takes 3 arguments, with the additional one that keeps a running total.
R.binarySearch()	Searches for an integer in a sorted array of integers using "divide & conquer".	R.binarySearchR()	Write a helper method for passing the low and high indices in the recursive call.