The first occurrences of Fibonacci numbers were found in Indian mathematic transcripts in 700AD. Outside India, the Fibonacci sequence first appears in the book Liber Abaci (1202) by Leonardo Bonacci. Fibonacci considers the growth of an idealized (biologically unrealistic) rabbit population, assuming that: a newly born pair of rabbits, one male, one female, are put in a field; rabbits are able to mate at the age of one month so that at the end of its second month a female can produce another pair of rabbits; rabbits never die and a mating pair always produces one new pair (one male, one female) every month from the second month on. The puzzle that Fibonacci posed was: how many pairs will there be in one year?

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 sample Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144

Note that the second number 1 is the sum of its predecessors 0 + 1, the third number, the sum of its predecessors 1 + 1, the fourth number is again the sum of its predecessors 1 + 2, and so on and so forth. Following this pattern we can create a limitless sequence of ever-growing numbers.

Now you are probably wondering why you should care about these numbers. The truth is that while most relevance of Fibonacci numbers lies in the area of applied mathematics, the Fibonacci algorithm is a popular algorithm for both developer interviews and university courses. This is probably due to the fact that a Fibonacci sequence can be created by writing a simple recursive function.

Recursive Functions

A recursive function is a function that calls itseft repeatedly within itself. To illustrate this concept, let’s consider a simple recursive factorial function. A quick flashback to grade school mathematics. In mathematics factorials are written like 4!. That means 1 * 2 * 3 * 4. Another example: 8 is 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8. A recursive solution to calculate factorials would be the following:

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

factorial(4); // logs 24

Now, what exactly did happen here? Lets run the function step by step. The initial value of the argument is 4 which is greater than 1 so the if statement evaluates to false. Then the return statement multiplies the value 4 with the following statement factorial(3). Since our function does not know the output of factorial(3) it will dive into the function to determine what it will return.

After reaching the final statement the function realizes that the return value of the function is 3 * factorial(2). There is yet another factorial function to determine the outcome of. After proceeding to another function call (this time with initial value of 2), 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 to the rescue. 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 Function

Now that we have an understanding of recursive functions lets create our fibonacci calculator. We want to make a function that will calculate the n-th Fibonacci number. fibonacci(4) should return 3(1,1,2,3).fibonacci(8) should return 21(1, 1, 2, 3, 5, 8, 13, 21) and so on.

var fibonacci = function(n){
    if(n == 0){
        return 0;
    }else if(n === 1){
        return 1;
    }else{
        fibonacci(n-1) + fibonacci(n-2);
    }
};

fibonacci(8);

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 fibonacci will cause two more calls of fibonacci with values of int-1 and int-2. In our example of int = 8 it would look like this:

fibonacci(8) returns fibonacci(7) + fibonacci(6)
fibonacci(7) returns fibonacci(6) + fibonacci(5)
fibonacci(6) returns fibonacci(5) + fibonacci(4)
fibonacci(5) returns fibonacci(4) + fibonacci(3)
fibonacci(4) returns fibonacci(3) + fibonacci(2)
fibonacci(3) returns fibonacci(2) + fibonacci(1)
fibonacci(2) returns fibonacci(1) + fibonacci(0)
fibonacci(1) returns 1
fibonacci(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.

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

And there we have our result: 21. 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.

Advertisements