Blog

Just in case you’re curious, there are two types of programmers (at least on Quora):

• Those who imagine recursion to be a ‘black box’ and simply assume it works and don’t worry about the internals and intestines. I have no beef with them, hey, whatever works for you.
• Those who, like me, are curious and not satisfied without getting to the bottom of how it works.

Let’s start with a pedagogically simple example. The Fibonacci definition states that:

It is a series of numbers where each number is the sum of the two preceding numbers, starting from 0 and 1.

We could, for starters, write something like this:

(Simple, inefficient implementation only for illustrative purposes!)

As I said, this is not ideal because its time complexity is $O\left(2^n\right)$. Essentially meaning, the time it takes to compute fib(n) doubles for each increment of n. (and example of this will follow). Later I will also show efficient versions later, but for now, let’s look at this crude version since it’s simple and therefore pedagogically useful.

Base Cases

• If you ask for the 0th Fibonacci number (position 0), it’s simply 0 because 0 + 0 = 0. There’s no other non-negative number before zero.
• If you ask for the 1st Fibonacci number (position 1), it’s 1, because the previous number is 0 and the current number is 1. So 0 + 1 = 1.

This constitutes the point where all of our Fibonacci recursion rests: now calling fib(2) means, first it will have to call fib(1):

Then, fib(1) runs:

And returns its result to fib(2):

Next, fib(2) is not done yet, so it will run again:

During which time, it will call fib(0):

fib(0) in progress:

fib(0) finishes its task by giving its result to fib(2):

Now, fib(2) runs again to finalize itself:

The result of the finalization is adding the values it has received from fib(1) and fib(0):

Similarly, as you can see below, in order to get fib(5), we enlist help from fib(4) and fib(3), and they too respectively keep going back to earlier fibs such as fib(3) and fib(2), which eventually go to the base case:

As I mentioned earlier, this version is not efficient, and therefore not a good example of recursion. Look, just going to 7th Fibonacci already means so much work under the hood:

In other words, it becomes very slow and inefficient for larger values because it recalculates the same values over and over again. In other words, it will result in exponential time complexity.

Let’s see a concrete example:

Then we create a timer:

For fib(20), it seems fine, but look at the difference as we run fib(40), and more importantly, fib(45). I tried fib(60) but that would take much much longer:

So what’s the workaround?

Just because you have a tool, it doesn’t mean you must use it to solve every problem. There’s a simpler, efficient way to do Fibonacci, which you can see in my older answer from 2019. This older solution is in Julia but Julia almost reads like Python:

Of course, that’s not the only way to do it. We could also do this, which is also iterative:

Let’s see how efficient it is:

Nice!

PS::

Suppose someone said they wanted a more efficient recursive one. There are many ways to do this, but listing them all will make this already long answer even longer. I’ll just mention one interesting case, though.

In Python, we can try a form of caching called memoization; basically we would be storing the results of previous function calls in a dictionary or an array, and returning them if they are needed again (instead of recomputing them, hence resulting in linear time complexity.):

This works well for very large values but there’s a small thing to notice:

When I first ran fib(2900) I got an error message. Trying 2600, and then 2900, it worked. Why?

When I called fib(2900), the function tried to compute the result by recursively calling itself until it reached the base case; since the cache was empty at this point, every recursive call was executed and stored in the cache. Consequently, the cache grew very quickly, and eventually exceeded the maximum recursion depth limit of Python (which is 1000 by default). This caused the RecursionError .

Actually this error was caused around fib(900) at first:

But when I gradually computed, the error was fixed:

That is, when I called fib(600), I didn’t run into recursion depth limit but now, the cache was no longer empty, so the next time I tried fib(900), some of the recursive calls were skipped and retrieved from the cache (and because of this, didn’t exceed Python’s maximum recursion depth limit.).

Using this trick, I incremented the argument by 498 each time (499 would result in error), and went all the way up to fib(13215) (and could keep going but this is already a non-trivial number indeed!). The following computation took less than a second on a Mac M1: