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.

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)$

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.

- 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.

Copyright © 2024 Ian Finlayson | Licensed under a Attribution-NonCommercial 4.0 International License.