Recursion…???

Every week I meet with a group of developers to do algorithm problems and go over problem solving strategies to prepare for technical interviews. This past week, I encountered my first Fibonacci sequence problem: Nth Fibonacci Number, one of the most common coding interview problems that you might find. The problem is stated as this:

The Fibonacci sequence goes like this: 1, 1, 2, 3, 5, 8, 13, 21, 34, …

The next number can be found by adding up the two numbers before it, and the first two numbers are always 1.

Write a function that takes an integer n and returns the nth Fibonacci number in the sequence.

After struggling with the problem for ten minutes, someone recommended that a recursive approach to the question might be the best path forward. Though I had heard of recursion, I had no idea how to implement it into my solution. The name alone was associated in my mind with an infinite loop or a stack overflow error, where a program or block of code loops endlessly with no terminating condition to exit the loop.

It turns out I wasn’t too far off the mark. Recursion, simply, is a process, or a function in the case of JavaScript, that calls itself. Suppose we had a function called hello and inside of the function we called the same function, hello. Like the infinite loop problem above, recursive functions require some endpoint or terminating condition in order exit this loop of function calls. The biggest initial hurdles for me in understanding how recursion works and why it’s a helpful approach were what’s happening behind the scenes when a function calls itself, and how do I exit this loop.

In JavaScript, the structure that manages what happens when functions are called is the call stack. Any time a function is invoked it’s placed on the top of the call stack. When JavaScript sees the return keyword or when the function ends, the compiler will remove the function from the top of the call stack.

At this point, everything I learned in my introduction to recursion made basic sense to me, but I couldn’t really see how I would apply it to the problem I had: Nth Fibonacci Number. The key to understanding the problem, as I understood it, was to use the mathematical formula that is its basis, each number is the sum of the two numbers preceding it, and implement it in a recursive function. The basic formula is this: n-1 + n-2. First, however, we want to implement a conditional statement, which will end up being our terminating condition, that if n is less than or equal to 2 we want to return 1. As we know, the first two numbers of the Fibonacci sequence are 1 and 1; if we have to solve for the second or first Fibonacci number, we can simply return 1 from our function.

At this point we have the basic outline of our solution, we just need to implement it recursively:

We are going to call our function fib on both n-1 and n-2 and return the value from both of those functions, which looks like the below function.

Because recursive trees can get really big, really quickly, I’m going to implement this function for the 5th number of fibonacci sequence. If we set n equal to 5 we can see how the tree will look below:

Because the return value of every fib(2) is 1, we can simply count up all the leaves of the tree, which add up to five. Our recursive fibonacci algorithm works by calling itself on the nth number until our base case is met, until n is less than or equal to 2, which will expand our tree depending on how large n is. Recursion is everywhere in JavaScript and we don’t even really think about it most of the time. But once it really clicks for you, it can be a really powerful approach to difficult algorithm problems that are often deceptively simple until you dive in.