Comp 110 Recursive Methods

A recursive method is a method that calls itself. Anything you can do with a loop, you can also do with recursion. It works because every time a method call is encountered a new frame is added to the call stack. So since a frame's local variable values are independent of other frames', we can leave a bookmark in the middle of a method, add a new frame, and jump to the same method!

As with loops, we need to prevent recurring infinitely, so we need a test condition at which point we stop recurring. This is called the base case. Additionally, we need something to change as we recur so eventually this base case can be hit. Typically, what changes is the argument we pass to the following recursive method call. 

*Every recursive method needs a base case. 

Let's look at an example. The Fibonnaci sequence is a super popular example for this concept. We can build a recursive method to compute the numbers in the Fibonacci sequence. This sequence begins with 0 and 1, and each following number is the sum of the first two proceeding Fibonacci numbers. 

0 + 1 = 1 <- the second Fibonacci number

1 + 1 = 2 <- the third

1 + 2 = 3 <- the fourth

2 + 3 = 5 <- the fifth

and so on...

This method fib takes some integer n as a parameter and returns the nth Fibonacci number. So if we plug in 4 as n, it will return 3.

public int fib (int n) {
     if (n <=1) { //This is the base case
          return n;
     } else {
          return fib(n-1) + fib (n-2); //This is the recursive case
     }
}

Do you see how, as long as the argument isn't 1 or 0, it will keep calling itself? So when we plug 4 in as the argument, what we are really doing is getting the Fibonacci value for 3 and 2, both of which we are getting the Fibonacci value for the values in the sequence before it. Here's what the method looks like as a tree:

             4

      3           2

   2    1     1    0

1  0

The numbers at the bottom of the tree depicts cases where there are no recursive calls. So in the case of the Fibonacci sequence when n <= 1.