JavaScript Algorithms - 12 - Recursive Fibonacci Sequence

📱 Follow Codevolution

Recursive Fibonacci Sequence
JavaScript Algorithms
Algorithms with JavaScript

[vaibhavsharma]

To find the nth number of the Fibonacci sequence, you can use the following formula:

Fn = Fn-1 + Fn-2

where F1 = 1 and F2 = 1 are the first two numbers in the sequence.

For the 6th number in the Fibonacci sequence, we can use the formula to calculate it step by step:

F1 = 1
F2 = 1
F3 = F2 + F1 = 1 + 1 = 2
F4 = F3 + F2 = 2 + 1 = 3
F5 = F4 + F3 = 3 + 2 = 5
F6 = F5 + F4 = 5 + 3 = 8

[awaisfiaz]

For the first time in my life i understood recursion in real sense thanks man excellent series

[amazing-ekuo]

Those who didn't understand this, please refer the next video and come back.

And Sir, if you put the video of 'factorial' ahead of this then it will be easier to understand the concept. It is easier to go through nested functions in the ' factorial question'.

[c.]

this version also accounts for the case that the user inputs 0 or a negative number:

function recursiveFibonacci(n) {

if(n<1) return null // if n is 0 or less, there is no sequence
if(n<3) return n-1 // n has to be bigger than 0, so if it is 2 or 1, return 1 or 0
let fib = recursiveFibonacci(n-1) + recursiveFibonacci(n-2)
return fib;
}

[deepaksingh-gjoh]

function fibRec(n){
if(n<2){
return [0, 1]
}
let arr = fibRec(n-1)

return arr
}

[manishrajput]

for n = 3

5 calls => (4+1) calls => ((2^2) + 1) calls => ((2^(n-1)) + 1 calls ~> 2^(n-1) calls => 2^n calls

Hence, time complexity = O(2^n)


For any number n, this function is called (((2^(n-1)) + 1) times. Ignoring other values, O(2^n).

[Buggs]

Given the example function in the video, the time complexity is O(2^n). My solution is a bit different which both time and space complexity's are O(n). I assume this might slightly perform better.

function recursiveFibonacci(n, fib = [0, 1]) {
fib[fib.length] = fib[fib.length - 2] + fib[fib.length - 1];
if (fib.length <= n) recursiveFibonacci(n, fib);
return fib[n];
}

[Ayoubmajid-uuyv]

I implemented recursion function with O(n) 8:16
// o(n) : linear time
function fibonacciOptimized(n, counter = 0, perviousValue = 0, value = 0) {
if (counter == 1) {
value = 1;
perviousValue = 0;
}
//base case :
if (counter == n) return value;

return fibonacciOptimized(n, ++counter, value, perviousValue + value);
}

[theideadude]

function fibonnaci(n, start = 0, end = 1) {
if (n - 2 > 0) return fibonnaci(n - 1, end, start + end)
if (n === 0) return start
return start + end
}

[podcasttakes]

Sure, let's trace each step of the recursiveFibonacci function for n = 7.

Function Definition


function recursiveFibonacci(n) {
if (n < 2) {
return n;
}
return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
}

Tracing for n = 7

recursiveFibonacci(7)

n is not less than 2, so it returns recursiveFibonacci(6) + recursiveFibonacci(5).
recursiveFibonacci(6)
n is not less than 2, so it returns recursiveFibonacci(5) + recursiveFibonacci(4).
recursiveFibonacci(5)
n is not less than 2, so it returns recursiveFibonacci(4) + recursiveFibonacci(3).
recursiveFibonacci(4)
n is not less than 2, so it returns recursiveFibonacci(3) + recursiveFibonacci(2).
recursiveFibonacci(3)
n is not less than 2, so it returns recursiveFibonacci(2) + recursiveFibonacci(1).
recursiveFibonacci(2)
n is not less than 2, so it returns recursiveFibonacci(1) + recursiveFibonacci(0).
recursiveFibonacci(1)

n is less than 2, so it returns 1.

recursiveFibonacci(0)

n is less than 2, so it returns 0.

Now, let's substitute these values back up the chain:

recursiveFibonacci(2):
recursiveFibonacci(1) + recursiveFibonacci(0) = 1 + 0 = 1
recursiveFibonacci(3):
recursiveFibonacci(2) + recursiveFibonacci(1) = 1 + 1 = 2
recursiveFibonacci(4):
recursiveFibonacci(3) + recursiveFibonacci(2) = 2 + 1 = 3
recursiveFibonacci(5):
recursiveFibonacci(4) + recursiveFibonacci(3) = 3 + 2 = 5
recursiveFibonacci(6):
recursiveFibonacci(5) + recursiveFibonacci(4) = 5 + 3 = 8
recursiveFibonacci(7):
recursiveFibonacci(6) + recursiveFibonacci(5) = 8 + 5 = 13

So, recursiveFibonacci(7) returns 13.

Step-by-Step Breakdown:

Initial Call:

recursiveFibonacci(7)

Recursive Calls:

recursiveFibonacci(6) and recursiveFibonacci(5)
recursiveFibonacci(5) and recursiveFibonacci(4)
recursiveFibonacci(4) and recursiveFibonacci(3)
recursiveFibonacci(3) and recursiveFibonacci(2)
recursiveFibonacci(2) and recursiveFibonacci(1)
recursiveFibonacci(1) and recursiveFibonacci(0)
Base Cases:

recursiveFibonacci(1) returns 1
recursiveFibonacci(0) returns 0

Combining Results:

recursiveFibonacci(2) = 1 + 0 = 1
recursiveFibonacci(3) = 1 + 1 = 2
recursiveFibonacci(4) = 2 + 1 = 3
recursiveFibonacci(5) = 3 + 2 = 5
recursiveFibonacci(6) = 5 + 3 = 8
recursiveFibonacci(7) = 8 + 5 = 13

This step-by-step process shows how the recursive function breaks down the problem and combines the results to find the nth Fibonacci number.

[xiaotingshao]

that's a good explanation for time complexity

[kjagan]

Please sir, please start a series on DS and system design as well

[jitendrapatidar]

Hi Vishwas, it's great learning till now but above solution is wrong because it's failed at n=2 that function give output as 2 but required output is 1.

[strbjun]

There is a way to significantly speed up the recursive fibonacci sequence so that it is about as fast as O(n). If you use an array that is passed as a parameter during the recursive routine it dramatically speeds it up. This won't necessarily work in every language but it works in javascript as arrays are stored in a shared memory. This means it really only needs to run it on each value as many times as in the FOR loop. Sort of. But this was my code in typescript:
const fibonacciRecursive = (n: number, fib: number[] = []): number => {
if (n <= 1)
return n;
if (fib[n])
return fib[n];
fib[n] = fibonacciRecursive(n - 1, fib) + fibonacciRecursive(n - 2, fib);
return fib[n];
}
If you try that modified for javascript you'll see it is fast in recursive this way.

[prabhakaranishere]

If I try to find it for 6 in paper according to his rule.

return findFiboRecursive(n - 1) + findFiboRecursive(n - 2);

then

(6-1) + (6-2)
5+4
9

But findFiboRecursive(6) gives 8. How come? Can anyone help me plz?

[calendoscopio]

damn, now i understand this graphic 😅

[muhammadehtesham]

Question !
The Fibonacci Series of Number 6 is 0, 1, 1, 2, 3, 5 but when I make a recursive function for the same number 6 it returns me 8 that is the sum of 3 and 5? It is confusing me. Any explanation please!

[Bloodslunt]

0(2^n)... phew. I can finally stop worrying about trying to understand recursive fibonacci.

[susmitobhattacharyya]

One doubt how can the time complexity be O(2^n)??

For example if we are calling

recursiveFibonacci(3) then it will be called 5 times,
recursiveFibonacci(4) then it will be called 9 times,
recursiveFibonacci(5) then it will be called 15 times.

Please help by clearing the doubt.

[ME-lsde]

here's my solution to solving with recursion:

function fibonacci(num, arr = [0, 1]) {
if (num < arr.length + 1) {
return arr;
}

return fibonacci(num, [...arr, arr[arr.length - 1] + arr[arr.length - 2]]);
}