Introduction to Recrusion: Four Versions of Fibonacci

When I was taking my first steps in computer science, recursion was one of the first topics I encountered that was a bit difficult to get my mind around. Intro CS courses differ in terms of when they introduce recursion, but it almost always comes up and when it does the Fibonacci sequence usually rears its head.

At its most basic, a recursive structure is something made up of other, generally smaller versions of itself. For example, as a tree grows, the trunk grows branches and as time goes on, those branches sprout branches of their own. An old tree might have 10 layers of branches between the trunk and leaves. Structures with multiple levels that comprise a whole are often referred to as "nested" structures, since each new level is contained within another. Think Matryoshka Dolls or the "dream levels" in the movie Inception.

In programming, recursion refers to self-referential functions or data structures. In other words, functions and data structures that are defined in terms of smaller, nested versions of themselves. The Fibonacci sequence is perhaps the most common example used to illustrate recursive functions: the nth Fibonacci number is defined as the sum of two Fibonacci numbers before it in the sequence, with Fibonacci of 0 being equal to 0 and the Fibonacci of 1 set equal to 1. To find, say, the the 10th Fibonacci number, you first have to know the 8th and 9th Fibonacci numbers. But since you don't know those, you have find the 6th and 7th Fibonacci numbers and so on. Any problem that can be defined in terms of smaller versions of itself is potential candidate for a recursive solution. The main caveat is that the recursion needs to stop eventually: a recursive function needs to reach a base case that causes it to exit without referring to itself. If the branches don't eventually come to an end, the function will repeat forever.



Naive Fibonacci

When you first encounter the Fibonacci sequence, you'll probably see a naive recursive solution that looks something like this:

 def naive_fib(n):  
   if n == 0:  
     return 0  
   if n ==1:  
     return 1  
   return naive_fib(n-1) + naive_fib(n-2)  

The final line of naive_fib calls naive_fib twice with different values for n, making this a recursive function. If called with n greater than 1, naive_fib creates 2 new copies of itself to figure out the Fibonacci number of n-1 and n-2 and piece together the final solution. The problem with this naive solution is every call to naive_fib has creates new copies unless it reaches the base case. If the first call makes 2 copies and those copies also make 2 copies a piece and so on, it ends up creating a number of copies that is exponential in n before each branch reaches the base case. Exponential running time is bad. Even with a small input like n=35, the naive solution makes over 18 million function calls. A tree with 18 million branches would collapse under its own weight. Computers can handle a few more branches than trees, but if you go much higher than n=35, it will take hours, years or longer for naive fib to return a solution. Woe to the intro CS student that tries to run naive_fib(100).



Iterative Fibonacci

Although naive_fib serves as a simple example to introduce recursion, such introductions usually leave Fibonacci in its naive form and move on. But what if we want to find the 100th Fibonacci number? An insightful students might ask "can't I make an iterative solution to with the loops I already learned?" The answer is yes. Any recursive function can be rewritten as an iterative function and it can pay dividends to use an iterative solution, since it avoids the pitfall of creating an exponential number copies of the a function. This simple iterative Fibonacci function can easily return fib of 100 or even 100,000 in a fraction of a second:

 def iter_fib(n):  
   if n == 0:  
     return 0  
   n1 = 0  
   n2 = 1  
   for i in range(n-1):  
     new = n1+n2  
     n1 = n2  
     n2 = new  
   return n2  

Since the iterative solution runs much faster than the naive recursive solution, why would we use recursion at all? In the case of the something as simple as the Fibonacci, there's really no need to use recursion, but with more complex problems, recursion can simplify the solution. With recursion, all you need to do is specify a base case and make the correct recursive calls, which can be much easier to express than keeping track of all sorts of different counter variables and making sure iterate over the correct ranges. Additionally, recursion doesn't have to be slower than iteration: if we can find a way to trim off most of the branches, the tree will be able to stand.



Dynamic Programming Fibonacci

One way to avoid excessive branching and is a method known as "dynamic programming." With dynamic programming, you store intermediate solutions you find that are a part of larger problem and check your list of stored solutions before attempting to solve new sub-problems. For instance, with Fibonacci the data store, often called the memo, would store the result of Fibonacci of 3 = 2 the first time the function calculates fib of  3 and any further calls to the function would look up fib of 3 in the memo instead of making a recursive call to find the solution. This method essentially cuts off all the branches except for one long branch that reaches the base case and stores all the values for fib between 0 and n:

 memo = {0:0, 1:1}  
 def dynamic_fib(n):  
   if n not in memo:  
     memo[n] = dynamic_fib(n-1) + dynamic_fib(n-2)  
   return memo[n]  

Since the dynamic programming approach stores all values of fib between 0 and n, it makes it easy to check any intermediate values. On the other hand, this approach requires some extra memory to store intermediate results as well as the stack of recursive calls it makes to reach the base case. Depending on the problem, it might not be desirable to store a memo or create a stack of recursive calls in memory. So even with this more sophisticated approach, we end up behind iteration. Is recursion doomed to perform worse iteration? No!



Tail Recursive Fibonacci

Recursion can achieve the same processing and memory efficiency as iteration using a method called tail recursion. The main drawback of the dynamic programming approach is that it needs to drill down from n to the base case and then piece the solution back together, while keeping the long branch of recursive calls in memory. You can avoid making a long branch in memory by accumulating a solution in a variable that you pass down the tree as an argument to each successive recursive call. This method is known as tail recursion, because the function exits at the bottom of the recursive tree when it hits the base case instead of building the solution up from the bottom and returning it from the original call. In the case of Fibonacci we can build up the solution in two accumulator variables passed down the tree as arguments:

 def tail_fib(n, acc1, acc2):  
   if n == 0:  
     return 0  
   if n ==1:  
     return acc1+acc2  
   return tail_fib(n-1, acc2, acc1+acc2)  

The end result is a recursive function that behaves like an iterative function. It can be a bit tricky to figure out how to accumulate a result for a tail recursive function, which involves using an technique known as invariant programming. If you want to learn more about tail recursion and invariant programming, consider checking out Paradigms of Computer Programming – Fundamentals on edX which is currently running.