Adding Fibonacci Numbers With Using Recursion Function

What is Fibonacci Sequence ?

The math was intended to be called “nature” and it’s where you look. In fact, There are specific numbers that we see in nature all the time. Together they called “The Fibonacci Sequence ‘’. It’s something like this(1,1,2,3,5,8,13,21,34,55). You may know this pattern; The first and second add up to the third, the second and third add up to the fourth and the fourth and fifth add up to the sixth and so on. The Fibonacci Sequence was first described by mathematicians in India about 1300 ago and it was introduced to the west in 1202 by Leonardo Of Pisa (AKA Fibonacci) who is also responsible for introducing Arabic numerals to Europe. When you divide almost any Fibonacci number by the one before it in sequence, especially the larger ones, You get the same number.

144/89, 1597/987
You get the same number:1.618

Today, We will see a recursion method for adding up Fibonacci Numbers.

Fibonacci Numbers With Recursion

The Problem:

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

My Solution

Actually we have a great tip from the question which is mentioning we should use recursion to solve this problem. If you look up the problem description you will see the part which includes as following.

F(0) = 0, F(1) = 1

It’s basically given us our base condition in the problem description. It means we can get the smallest input if the (n 0) or (n 1) then we return 0. That’s how we will start to implement our function first.

var fib = function(n) {
if(n === 0 || n ===1){
return n;
}

If n(0) We will return 0 or || If n(1) we will just return 1,

But we also need an edge case if n is not 0 or n is not 1; That’s where the calculation to answer came up in the game. In the question also included that how we will calculate the edge case. They also told us how to implement it in the question description.

F(n) = F(n - 1) + F(n - 2), for n > 1.

It says to get of F(n) You just need to do F(n-1) and add up F(n-2). And as you see this line of code is recursive.

Because on the left side you see function F(n) and right side function F(n) |function F(n) again. To solve the F(n), You should call again the function F(n) and again and sum the answers after summing the function the answer(function F(n) + function F(n) ) is on the left side. It’s obviously a Recursion Function.

We just need to return

return fib(n-1) + fib(n-2);

Full Solution


//fib = 0,1,2,3,4,5....,N
//Ans = 0,1,1,2,3,5....,?
var fib = function(n) {
if(n === 0 || n ===1){
return n;
}

return fib(n-1) + fib(n-2);
}

Let’s take a closer look for deep understanding

Example 2:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

This example actually asking us;

if the input is n =2 ;

We should get the Output : 1;

What it is actually mean?

First step

fib(2) = fib(1) + fib(0) which means how we calculate to get the number fib(2) based on Fibonacci Sequence.

 fib = 0,1,2,3,4,5....,N
Ans = 0,1,1,2,3,5....,?

But in the function which we created fib(2) = fib(2–1) + fib(2–2)

If we see input is n(2)

We know the answer is calculation of fib(2–1) + fib(2–2)

If we breakdown one more level its actually look like this;

fib = 0,1,2,3,4,5....,N.   
(2)= 0+1,1,2,3,5....,? fib(1) + fib(0)

fib (2) = fib(1) + fib(0)

We already got the answer in our base case solution as following code;

 var fib = function(n) {
if(n === 0 || n ===1){
return n;
}

If n(0) We will return 0 or || If n(1) we will just return 1,

0 + 1 = 1

if (n) = fib(0) + fib(1) = 1

If we just point of how this function works we can think like visual below explain like if input as fib(3)

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
fib = 0,1,2,3,4,5....,N   
(2)= 0,1+1,2,3,5....,? fib(1) + fib(2)

When n(3 ) We basically calling this part of function.

return fib(n-1) + fib(n-2);
// 1 + 1 = 2

I know it’s a little bit tricky because when you go fib(3) You also have to go one level down and get the result of fib(2) then fib(1) and sum. After summing them. You will get the fib(3).

Time and Space Complexity

When we asked about time and space complexity for our function.

Time Complexity : 0(2^N)

Space Complexity: 0(N)

Actually Time complexity of the function is really large 0(2^N)

If n= 4 -> 2 ^ 4 = 16

If we do 16 operations it’s really too much. It’s actually not the best solution for time complexity. What we could do, we can store the result. To avoid time complexity problem we can implement Dictionary.

class Solution {// fib = 0, 1, 2, 3, 4, 5, ..., N// ans = 0, 1, 1, 2, 3, 5, ..., ?// fib(2) = fib(2-1) + fib(2-2)// fib(2) = fib(1) + fib(0)//        =   1 + 0 = 1/*fib(4) = fib(3) + fib(2)/          \fib(3)=2 done     fib(2)/   \            2 is in cache!fib(2)=1 + fib(1)=1/    \fib(1)=1 + fib(0)=0time: O(N), n=4 -> 2^4 = 16space: O(N)*/Map<Integer, Integer> cache = new HashMap<>();// key: N, value: fib(N) answerpublic int fib(int n) {// base case: we already know the answer for nif (n == 0 || n == 1)return n;// base case: already solved answer for nif (cache.containsKey(n))return cache.get(n);// we need to calculate the answerint answer = fib(n - 1) + fib(n - 2);// store this answer for ncache.put(n, answer);return answer;}}

Software Engineer | Ruby on Rails | JavaScript | HTML5 | CSS | PostgreSQL | React | Redux