In Mathematics, the Fibonacci sequence is basically the sum of the previous two numbers, starting from 0 and 1. In the image shown above, we can tell right the way the third number is 1, which is also added from its previous two number 0 and 1. From then on, it is a matter of using this pattern to find out what is Fn is assuming n is the number of the sequence. The pattern can be summed up with a equation of Fn = Fn-1 + Fn-2 . Knowing what Fibonacci Sequence is, how do we translate this pattern using programming language into codes.
For demonstration purpose, we will be using JavaScript and solve this problem with recursion. What is recursion? Recursion is a way of solving a problem by having a function to call itself. Basically we are creating a function that will call the function itself repeatedly until certain criteria is met, and therefore solving the problem by the end of it. It is in a way similar to a while loop, itself is being called again and again until the loop is ended / broken out of the loop. Let us take a look at the code snippet shown below.
For simplicity purpose, we are going to start with F(1)= 1, and F(2)= 1, we are basically omitting the part where 0 starts. First we are creating a function called fib and with a given number i. If the number i is smaller than 3, we are simply returning 1 because the first two numbers in Fibonacci Sequence is given to us 1, 1. If the number i is greater or equal to 3, we are going to return the fib function itself with its previous two fib numbers, i-1 & i-2. It is not hard to understand fib(3) is fib(3–1) + fib(3–2), which is 1 + 1=2. But as the number i increases, the function will call itself more than once. For example, fib(4) = fib(4–1) + fib(4–2) which is fib(3) + fib(2), fib(3) = fib(2) + fib(1). fib(2) =1 and fib(1)=1, add them up we have 2, therefore fib(3)=2, while fib(2)=1, add them up we have 3. The example continues on as the number gets bigger, and the fib function will call itself repeatedly until it gets to fib(i < 3)
Recursion itself is not an easy concept to understand, but once comprehended, it can do a lot of wonderful things and help us solve a lot of problems in an unique way. I hope we all learned something new from this article and happy coding!
