Adding Fibonacci Numbers With Using Recursion Function

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

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.
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

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 = 2
Output: 1
Explanation: 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;
}
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;}}

--

--

--

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

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

Recommended from Medium

How lazy smartapp team uses Slack to stay productive

“If for each object o1 of type S there is an object o2 of type T such that for all programs P…

Python and Stackdriver Logging

Amazon Web Services (AWS) and Cloud Computing for Beginners — Best and free

Arithmetic & Logical Operators: R Data Types with Example

How to live stream an event from the cloud using Microsoft Teams NDI and OBS.

HackMyVM-Pwned

The Best Product Manager Tools

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

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

More from Medium

New TouchOSC Tutorial #4: Receive Data from TouchDesigner with OSC (CHOP)

CS371p Spring 2022: Week 6

Python API Tutorial: Getting Started with APIs

Use Packer from HashiCorp to create images.