The Problem
The Fibonacci sequence is a series of numbers, initialized at 0 and 1. From these two numbers, the sequence proceeds by adding the two numbers in order to create the next number in the series. Due to the relationship between the numbers in this sequence, it is often described as producing a golden ratio, as seen in the graphic below.
From seashells to the branching on trees, this seemingly unrelated mathematical sequence is a prevailing force in nature. This natural phenomenon can be explained in a simple mathematical equation.
This simple mathematical formula can be used as the foundation for building out an algorithm. The formula indicated that the value at n, is equal to the sum of the numbers at n-1(the number directly prior) and n-2(the number 2 before the current). If we were to start at 0 and 1, the numbers would scale up at 0, 1, 1, 2, 3, 5, 8, 13 and so on. First, we will build out an iterative solution in order to understand the translation between the mathematical formula and code.
The Iterative Solution
With an understanding of the basic mathematical concept behind the Fibonacci sequence, we can now translate this to a JavaScript function. In JavaScript, we will be using a function, that takes in an integer as parameter, which indicates the index of the number we want to find. In more plain terms, the parameter indicates how far down the line, we want to go in the sequence. Because the original formula for this sequence starts at the integers, 0 and 1, we can use these values as the initial starting point in our solution.
Because the first two numbers of the sequence are 0 and 1, it is important to identify that if the parameter is less than 2, the function should just return the parameter as the result.
The first if statement in the code snippet above, indicates that a parameter that is less than 2, returns the num. If the parameter is 0, we return 0, and if its 1, we return 1. This is due to the fact that the initial numbers for the sequence are 0 and 1, and they are not obtained through calculations. They are simply the starting values.
The next part is where our iterative solution comes in. An iterative solution is simply something that repeats to produce a certain result. In JavaScript, an iterative solution can be indicated by a for loop. Mathematically, we have to repeat the same (n-1) + (n-2) equation to produce a result. However, in JavaScript, we will be counting up. The expression can then be expressed as A+B=C, then A=B, B= C.
In plain math, this is expressed as (1+2)=3 => (2 + 3) = 5=> (3+5) =8 and so on.
Looking at the code snippet above, we can see that the for loop runs for as long as the counter (i) is less than the parameter value. The counter increments by 1, every time the loop is ran. Within the loop we can see the formula take shape. The lastTwo indicates a pair of numbers that will be added together, and then the values are replaced by the second value and the sum. As there is no equal sign within the for statement, the counter will stop at num-2. When we wrote the initial condition, we stated that if n<2, we return the parameter. By setting i < num-1, we are accounting for the fact, that the mathematical expression is (n-1) + (n-2).
Recursive Solution
However, an iterative solution in programming can often lead to errors. Although this function would be a poor example, there are many situations where recursion will produce a more sleek and ‘elegant’ solution compared to their iterative counterparts. Recursion, at its core, is simply a function that calls itself, until the break condition is met.
On a side note, recursive functions take up more memory due to the nature of how solutions are made. In recursive function, the stack, or the values, must be kept until the solution is reached. Essentially, every time the function calls itself, it must add a stack to the already existing stack.
The above code is the entire solution for the Fibonacci sequence in recursive form. Compared to the iterative solution, we can see that this solution is much shorter. However, a deeper dive is necessary into understanding how this function works. The conditional above is the same conditional we used in the iterative version. This is due to the fact that regardless of the type of solution, if the parameter is less than 2, the answer will always come out to the parameter itself. In a recursive solution, this conditional is often referred to as the break condition. Since a recursive function must call itself until an answer is reached, a break condition is necessary to end the loop and stop the function from calling itself endlessly.
This now leads us to the recursive part of the function. The return statement indicates that we want to call the function with parameter (n -1) + parameter (n-2). This means that we will have two branches from the original, as shown below.
Now for each branch, we will call the function again. This essentially will create two new branches from each function. The next image shows the second call of the function, with a total of 4 branches. However, now we must keep in mind the break condition. If parameter n is less than 2, return n.
The top row, furthest left call has a parameter of 2. This will have cause a third call of the stack. This leads to each branch now being inside of the break condition. We can now return an actual value, rather than calling the function again.
We can now add the sums of each branch where the function splits in order to climb down the tree. This leads to the final result of 3. If we think of the sequence, we know that the numbers go 0,1,1,2,3. Wait, that’s the 5th element in the tree!
When programming, we often think of the Fibonacci sequence as an array. This array would look like [0,1,1,2,3]. The index is the location of an element inside of the array. However, the indexes start at an initial value of 0. Which means the final index in a 5 number array is 4. This is how the function with a parameter of 4, becomes the “5th” value in an array.
Final Thoughts
Although recursive functions may not be the best option for every algorithm, it shows an important concept within programming. Recursive functions can provide quick and easy solutions when a problem calls for breaking it down into smaller pieces. A tree is a good example of how recursive functions can be used to generate a solution. However, this is not to say that there are not tradeoffs. If we were to run tests on how fast the code runs, we would find that iterative solutions will produce results faster. With that in mind, it is important to understand concepts like this to better grasp data structures and algorithms.