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 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!