Exponential Recursion with Fibonacci

I recently had to solve a problem that called for a recursive solution to find the nth spot in the Fibonacci sequence.

As a refresher, the Fibonacci sequence is a series of numbers that start with two 1s and continues by adding a number to the end of the series equal to the sum of the last two numbers currently in the series.

E.g., 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …, 55 being the 10th spot in the Fibonacci sequence starting from the beginning.

Calculating Fibonacci sequence. Relative places in parenthesis.

Conceptually, I’ve come to understand pointers pretty well. Recursion, I thought I had a pretty good handle on how function calls are added to the stack. Then in the case of this recursive solution, I had a hard time grasping the order in which calls would be added to the stack. I tried stepping out how I thought this solution worked on my whiteboard, sketching it out as I would with a basic recursion problem, and quickly realized from the disorder and arrows all over that there was a gap in how I was thinking about the solution. It didn’t occur to me that this solution was of exponential time complexity or what the stack calls looked like for recursion of exponential time complexity.

So simple.

I think I wrongly assumed that there would be some sort of state kept and that the initial stack would be computed in a linear fashion, from (in this case) fib(3) to fib(nth). To see what is actually occurring I observed the call stack with a debugger.

All hail the debugger.

As a refresher, here is how I accessed the javascript debugger within my VSCode:

1. Place a breakpoint on the line that is returning your function by clicking to the left of the line number.
2. Click this button to open the debug panel.
3. Click ‘Run and Debug’ to open a drop-down menu presenting options to debug with.
4. I have Node installed for running my Javascript code so I can debug with Node.js.

Step over or F10 will work here also and shed some additional insight.

We are just observing so we will only need to step through to get see the call stack:

1. By the time the breakpoint stops the function, the first call is already on the stack. Nth at this point is 10 which is the same as the value we passed as the argument and since it is first, the call will be at the bottom of the stack. It will be the last thing that needs to be resolved before our desired value is returned.
2. This button continues the function until it hits another breakpoint. Since the function is recursive and it calls itself. The function is read again from the top and hits the same breakpoint we made on line 18.
3. After pressing the ‘continue’ button or F5, we hit our breakpoint again. Notice we see another function call added to the call stack.
4. At this point, we see that nth is now 9 indicating the function call that just got added to the call stack was passed 9 as the nth parameter.

The debugger might be fibbing.

The initial calls added to the stack are made and include fib(10) through fib(3). You’ll notice that fib(1) and fib(2) aren’t added and that’s because they can be immediately evaluated to 1 just as the first two nth places in the Fibonacci sequence are.

At this point, the first two numbers of the Fibonacci sequence are accounted for(1,1,…). Stepping through, we see that both fib(3) (fib(2) + fib(1)) is evaluated to 2 and fib(4)(fib(3)(fib(1) + fib(2)) + fib(2)) is evaluated 3 immediately thanks to ‘(nth <= 3) return 1’.

So far we have the first four places of our Fibonacci sequence evaluated (1,1,2,3,…).

From fib(5) to fib(10), additional calls need to be added to the stack. Just because fib(4) has been evaluated once doesn’t mean that evaluation is ‘remembered’ for each additional fib(4) call added to the stack for the lifespan of the function. For this reason, the complexity of this algorithm is exponential.

Notice nth: 5 then nth: 3 then return value: 5

The number of calls added to the stack increases exponentially in relation to the parameter passed to the function.

1. call fib(1) -> return 1
   // fib(1) = 1
2. call fib(2) -> return 1
   // fib(2) = 1
3. call fib(3) -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 // fib(3) = 2
4. call fib(4) -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) ->
   call fib(1) -> return 1 -> return 1 -> return 2 -> return 3
   // fib(4) = 3
5. call fib(5) -> call fib(4) -> call fib(3) -> call fib(2) -> call fib(1) ->
   return 1 -> return 1 -> return 2 -> call fib(3) -> call fib(2) -> return 1
   -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5
   // fib(5) = 5
6. call fib(6) -> call fib(5) -> call fib(4) -> call fib(3) -> call fib(2) ->
   return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> call fib(4) -> call fib(3) -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3) -> call fib(2) -> return 1 ->
   call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> return 8
   // fib(6) = 8
7. call fib(7) -> call fib(6) -> call fib(5) -> call fib(4) -> call fib(3) ->
   call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3)
   -> call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 ->
   return 1 -> return 2 -> return 3 -> return 5 -> call fib(5) -> call fib(4) -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> call fib(4) -> call fib(3) ->
   call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3)
   -> call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> return 8 -> return 13
   // fib(7) = 13
8. call fib(8) -> call fib(7) -> call fib(6) -> call fib(5) -> call fib(4) ->
   call fib(3) -> call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> call fib(4) -> call fib(3) ->
   call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3)
   -> call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> return 8 -> call fib(6) -> call fib(5) -> call fib(4) -> call fib(3) -> call fib(2) -> call fib(1) ->
   return 1 -> return 1 -> return 2 -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> call fib(5) -> call fib(4) -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> call fib(4) -> call fib(3) -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3) -> call fib(2) -> return 1 -> call fib(2)
   -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5
   -> return 8 -> return 13 -> return 21
   // fib(8) = 21
9. call fib(9) -> call fib(8) -> call fib(7) -> call fib(6) -> call fib(5) ->
   call fib(4) -> call fib(3) -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) ->
   call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> call fib(5) -> call fib(4) -> call fib(3) -> call fib(2) -> return 1 ->
   call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> call fib(4) -> call fib(3) -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) ->
   call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> return 8 -> return 13 -> call fib(7) -> call fib(6) -> call fib(5) ->
   call fib(4) -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) ->
   call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> call fib(4) -> call fib(3) -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2
   -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> return 8 ->
   call fib(6) -> call fib(5) -> call fib(4) -> call fib(3) -> call fib(2) ->
   call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3) -> call fib(2)
   -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> call fib(5) -> call fib(4) -> call fib(3) ->
   call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1
   -> return 2 -> return 3 -> call fib(4) -> call fib(3) -> call fib(2) ->
   call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3) -> call fib(2)
   -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> return 8 -> return 13 -> return 21 -> return 34 // fib(9) = 34
10. call fib(10) -> call fib(9) -> call fib(8) -> call fib(7) -> call fib(6) ->
    call fib(5) -> call fib(4) -> call fib(3) -> call fib(2) -> return 1 ->
    call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> call fib(4) -> call fib(3) -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) ->
    call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> return 8 -> call fib(6) -> call fib(5) -> call fib(4) -> call fib(3) ->
    call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3)
    -> call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> call fib(5) -> call fib(4) -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> call fib(4) -> call fib(3) ->
    call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3)
    -> call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 ->
    return 1 -> return 2 -> return 3 -> return 5 -> return 8 -> return 13 -> return 21 -> call fib(8) -> call fib(7) -> call fib(6) -> call fib(5) ->
    call fib(4) -> call fib(3) -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) ->
    call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> call fib(5) -> call fib(4) -> call fib(3) -> call fib(2) -> return 1 ->
    call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> call fib(4) -> call fib(3) -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) ->
    call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> return 8 -> return 13 -> call fib(7) -> call fib(6) -> call fib(5) ->
    call fib(4) -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) ->
    call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> call fib(4) -> call fib(3) -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2
    -> call fib(3) -> call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> return 8 ->
    call fib(6) -> call fib(5) -> call fib(4) -> call fib(3) -> call fib(2) ->
    call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3) -> call fib(2)
    -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> call fib(5) -> call fib(4) -> call fib(3) ->
    call fib(2) -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1
    -> return 2 -> return 3 -> call fib(4) -> call fib(3) -> call fib(2) ->
    call fib(1) -> return 1 -> return 1 -> return 2 -> call fib(3) -> call fib(2)
    -> return 1 -> call fib(2) -> call fib(1) -> return 1 -> return 1 -> return 2 -> return 3 -> return 5 -> return 8 -> return 13 -> return 21 -> return 34 -> return 55
    // fib(10) = 55

So not only is the next place in the Fibonacci sequence a combination of the previous two places but so to is the next total callstack size a combination of the complete callstacks from the previous two places (nths).

This brings me to the point of me writing all of this out in the first place and it’s not because this is the most efficient way to calculate the nth place in the Fibonacci sequence. There is a break between understanding exponential recursion conceptually and how it is calculated computationally and I feel it’s important to think about that distinction in any kind of recursive consideration. Especially if you need a visual representation of the recursive output.

Visually, this would be known as a recursion tree, in that fib(9) and fib(8) are initially added to the call stack after fib(10), not because fib(n-1) is being calculated first before moving onto (n-2) in the initial call.

Rather because (10–1=9) and (10–2=8) and so on.

Left, n-1=9. Right n-2=8. Then to 9 and 8 respectively, n-1 and n-2 are applied, and so on.

All my conclusions here were drawn from my own observations using a debugger. I have no formal computer science training and so if you do and you see that I am logically off base I would be extremely grateful to be set upon the correct path. If that’s the case or you enjoyed the article please feel free to leave a comment or to dm me.

Thanks for your time!