# Adding Fibonacci Numbers With Using Recursion Function

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

# 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) = 1F(n) = F(n - 1) + F(n - 2), for n > 1.`
`Input: n = 2Output: 1Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.`
`Input: n = 3Output: 2Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.`
`Input: n = 4Output: 3Explanation: 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`
`var fib = function(n) {     if(n === 0 || n ===1){       return n;     }`
`F(n) = F(n - 1) + F(n - 2), for n > 1.`

## We just need to return

`return fib(n-1) + fib(n-2);`
`     //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 = 2Output: 1Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.`

## 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....,?`
`fib = 0,1,2,3,4,5....,N.   (2)=  0+1,1,2,3,5....,?   fib(1) + fib(0)`
` var fib = function(n) {     if(n === 0 || n ===1){       return n;     }              `
`fib = 0,1,2,3,4,5....,N   (2)=  0,1+1,2,3,5....,?   fib(1) + fib(2)`
`return fib(n-1) + fib(n-2);    //  1       +  1       = 2`

## Time and Space Complexity

`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;}}`

--

--

--

## More from Soner Mezgitci

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

Love podcasts or audiobooks? Learn on the go with our new app.

## Soner Mezgitci

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