# 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 ourbasecondition in the problem description. It means we can get the smallest input if the(n 0)or(n 1)then wereturn0. 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 willreturn 0or||Ifn(1)we willjust 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;

}

Ifn(0)We willreturn 0or||Ifn(1)we willjust 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)*

`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 large0(2^N)

If n= 4 -> 2 ^ 4 = 16

If we do16operations it’s really too much. It’s actually not the best solution fortime 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)returnn;// base case: already solved answer for nif (cache.containsKey(n))returncache.get(n);// we need to calculate the answerint answer = fib(n - 1) + fib(n - 2);// store this answer for ncache.put(n, answer);returnanswer;}}