Algorithm Sundays: Fibonacci Number Sequence and Recursive Functions

Welcome back to our weekly algorithm challenge. After having previously discussed Roman Numerals and the Caesar Cipher, today's post will travel even further back in time. The first occurrences of Fibonacci numbers were found in Indian mathematic transcripts in 700AD. However, their first appearance in the western civilization was much later. It was an Italian mathematician and merchant named Leonardo Bonacci, who introduced the western world to these foreign arithmetics. Consequently, the Fibonacci Pattern was named after him and not after Indian mathematicians such as Virahanka.

The idea of Fibonacci numbers is simple. It's a sequence in which the sum of the two previous numbers will define the next upcoming number. Let's take a look at a set of Fibonacci Numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34  

the second number 1 is the sum of its predecessors (0) + 1. the third number 2 is the sum of its two predecessors 1 + 1. The 4th number 3 is the sum of 1+2. The 5th number 5 is the sum of 2 + 3. Following this pattern, we could potentially construct a limitless sequence of quickly growing numbers. Now, looking at some ancient Indian arithmetics is pretty neat but you're probably wondering why you should care about these numbers. To be honest, the chance that you actually need to work with them in your everyday life as a developer is pretty small. Most of the relevance of Fibonacci numbers lies in the area of applied mathematics.

However, it is a popular algorithm for both developer interviews and university courses. It was one of the first algorithms that were presented to me in one of my programming classes in university. This is probably due to the fact that a Fibonacci sequence can be created by writing a simple recursive function. While knowing Fibonacci numbers might not save your life, recursion is an important concept in programming and should become a part of your vocabulary.

Writing Recursive Functions

Remember that movie Inception? A dream within a dream? That's the Hollywood version of recursion. A recursive function is calling itself repeatedly within itself. To illustrate this, let's have a look at a short recursive factorial function. A quick flashback to 10th-grade math: In mathematics factorials are written like this: 4!. What this means is 1*2*3*4. Another example: 6! = 1*2*3*4*5*6. A recursive solution to this could look like this:

factorial(4); //returns 24

function factorial(int) {  
  if (int <= 1) {
    return 1;
  }
  return int * factorial(int-1); // factorial is being called again
}

Now, what exactly is happening here? Let's focus on the return statement. It's receiving the initial integer 4 from our function call and we ask our function to return 4 * factorial(3). Since our program doesn't exactly know yet, what the outcome of factorial(3) will be, it will now first dive into this nested function to determine what will be returned.

After reaching the bottom of the second function, our program realized that the return value of this function is 3 * factorial(2). If this would be added to our initial equation, it would now look something like this: 4 * 3 * factorial(2). Our program has yet to enter another factorial function to determine the outcome. After proceeding to another function call (this time with 2 as int value), our main function would look like this: 4 * 3 * 2 * factorial(1).

Now for the final function call, we have to make sure our function doesn't end up calling itself forever. So just like when using a while-loop, we need a termination condition. This is where our if statement comes in. If our recursive function calls reach the number 1, we only pass a simple number back to our main equation. This way we stop our calls and our main function can finally return the correct result: 4 * 3 * 2 * 1.

The Fibonacci Sequence

Armed with this knowledge we can now come back to our initial problem. We want to create a function that will return the n-th Fibonacci number. fibo(4) should return 3 (1, 1, 2, 3). fibo(8) should return 21 (1, 1, 2, 3, 5, 8, 13, 21) and so forth. We want to follow the pattern by adding the previous number to our current number so we can find the next number in the sequence. Let's put these thoughts into writing:

fibo(8); //returns 21

function fibo(int) {  
  if (int === 0){
    return 0;
  }
  else if (int === 1) {
    return 1;
  }
  else {
    return fibo(int-1) + fibo(int-2);
  }
}

Once again we have added an if statement to make sure we don't end up in an infinite recursion. We know that the Fibonacci number at the first position is 1 and the number before that is 0. To understand the recursive pattern behind this algorithm, we should look at the return statement. Each call of fibo will cause two more calls of fibo with values of int-1 and int-2. In our example of int = 8 it would look like this:

fibo(8) returns fibo(7) + fibo(6)  
fibo(7) returns fibo(6) + fibo(5)  
fibo(6) returns fibo(5) + fibo(4)  
fibo(5) returns fibo(4) + fibo(3)  
fibo(4) returns fibo(3) + fibo(2)  
fibo(3) returns fibo(2) + fibo(1)  
fibo(2) returns fibo(1) + fibo(0)  
fibo(1) returns 1  
fibo(0) returns 0  

Now that we have reached the bottom, we can start filling in the function values from the bottom up. We are replacing each function call with the resulting value until we reach the top.

fibo(8) returns 13 + 8 // returns 21  
fibo(7) returns 8 + 5  // returns 13  
fibo(6) returns 5 + 3  // returns 8  
fibo(5) returns 3 + 2  // returns 5  
fibo(4) returns 2 + 1  // returns 3  
fibo(3) returns 1 + 1  // returns 2  
fibo(2) returns 1 - 0  // returns 1  
fibo(1) returns 1  
fibo(0) returns 0  

And there we have our result: 21. Don't worry if this makes your head spin a little. For most situations you are able to solve your problems using loops instead of recursions. Unlike some other programming languages, Javascript is not optimized for recursive programming and has a very limited stack size (the maximum number of function calls you can create recursively). That means you might even want to avoid using recursion in your algorithms.

However, in some cases a recursive approach is not only more elegant but the only way to solve a given problem. You will know when you need recursions, since traditional loops and conditional statements won't get you anywhere. In this moment, before you despair and throw your laptop out of the window, you should remember that once upon a time we briefly spoke about recursive functions. They might save your day.

Further down the rabbit hole