Recursion Part 3

Fibonacci Numbers

The Fibonacci numbers are a sequence of numbers starting with {1, 1}. Each subsequent number is then the sum of the two previous. We can find Fibonacci numbers with a loop, but we can also use recursion.

A recursive definition of the Fibonacci sequence is as follows:

$fib(1) = 1$

$fib(2) = 1$

$fib(x) = fib(x - 1) + fib(x - 2)$

We can use this definition to get the following method:


public static int fib(number) {
    if(number < 3) {
        return 1;
    } else {
        return fib(number - 1) + fib(number - 2);
    }
}

This method is also $O(2^n)$. As you can see every call to the method expands into two more, so the number of calls explodes exponentially.

This is a case where the most natural recursive solution is not very efficient. Just because this particular algorithm is $O(2^n)$ doesn't mean that this problem is hard to solve. Remember that Big-O complexities are for algorithms, not problems. Some problems don't have efficient solutions, but this one happens to. There is a $O(n)$ solution, which we can write with a loop like this:


int fib(int number) {
    int a = 1;
    int b = 1;
    int n = 1;
    for(int i = 2; i < number; i++) {
        n = a + b;
        a = b;
        b = n;
    }

    return n;
}

This Fibonacci method runs far faster. This algorithm is $O(n)$, which you can see from the fact that there is one loop which runs up to the number given.

Faster Recursive Fibonacci Numbers

In this case, the slow solution is easiest implemented with recursion and the fast solution is easiest implemented with iteration. But we can write fast recursive solutions as well. We could also write the slow algorithm with a loop (but why would we want to?).

There are at least two fast recursive solutions to this problem. The simplest is to employ a technique called memoization which is basically to cache solutions to the problem in an array. When we call the recursive method, it first checks if the array holds the answer. If so, it returns it directly. If not, then it computes it from scratch (saving the result in the array for later). This reduces the repetitious work the original recursive solution does.

The Fib_Memoized.java code can be seen here:


// recursive fibonacci sequence w/ memoization
public static long recursive_fib(int number) {
    // if we've already calculated this, use the saved result
    if (results[number] != 0) {
        return results[number];
    }

    // the base case of 0 or 1
    if (number < 2) {
        results[number] = 1;
        return 1;
    } else {
        // figure it out, then save it in the array
        long answer = recursive_fib(number - 1) + recursive_fib(number - 2);
        results[number] = answer;
        return answer;
    }
}

This program runs far faster because it only computes each unique Fibonacci number one time. Memoization is nice because you can use it as an optimization to an existing solution without needing to rewrite the algorithm. Like the iterative solution, this runs in $O(n)$

Using Recursion as a Stack

Because method calls cause a push onto the stack, and method returns cause a pop from the stack, we can use recursion to write any algorithm using a stack using recursion. For example, the depth first search algorithm was given as follows:

Set current to the start position.
While current is not the end position:

Mark current as visited.
If we haven't gone left, push left.
If we haven't gone right, push right.
If we haven't gone up, push up.
If we haven't gone down, push down.
If the stack is empty, there is no path!
Set current to pop().

We made it!

We can write this using recursion by replacing the pushes with recursive calls. DFS_Recursive.java demonstrates a recursive depth first search.

Designing Recursive Functions

Break big problems into smaller ones.
Make sure there is a base case.
Make sure the general case gets us closer to the base case.