Adding Fibonacci Numbers With Using Recursion Function

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

Fibonacci Numbers With Recursion

The Problem:

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

My Solution

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

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

First step

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Soner Mezgitci

Soner Mezgitci

31 Followers

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