# Adding Fibonacci Numbers With Using Recursion Function

**What is Fibonacci Sequence?**

The concept of mathematics, in its essence, is closely linked with the patterns and structures of nature. One such pattern that is ubiquitous in nature is the Fibonacci sequence. This sequence, consisting of numbers such as 1, 1, 2, 3, 5, 8, 13, 21, 34, and 55, is generated by adding the two preceding numbers to obtain the next number in the sequence. For instance, 1+1=2, 1+2=3, 2+3=5, and so on.

The Fibonacci sequence was first described by mathematicians in India about 1300 years ago. Still, it gained prominence in the West when Leonardo of Pisa, also known as Fibonacci, introduced it in his book Liber Abaci in 1202. Fibonacci is also responsible for introducing Arabic numerals to Europe.

Interestingly, when you divide any Fibonacci number by the one preceding it in the sequence, especially the larger ones, the result is approximately the same number, known as the golden ratio. This ratio has been observed in many natural phenomena, such as the spiral patterns of shells, the arrangement of leaves on a stem, and the proportions of the human body.

`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 follows.*

**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 **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 proper 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;}}