How to solve the recursive functions quickly

Question

function fib (num) {
if(num<=2)
{
return 1;
}
else
return fib(num-1)+fib(num-2);
}
document.write(fib(6))
/*first step
fib(5)+fib(4)
second step
fib(4)+fib(3)+fib(3)+fib(2)
third step
fib(3)+fib(2)+fib(2)+fib(1)+fib(2)+fib(1)+1
fourth step
fib(2)+fib(1)+1+1+1+1+1+1
fivth step
1+1+1+1+1+1+1+1
sixth step 8
*/
I know the solution of this problem but i would like to get a trick or faster solution than 6 steps

Answer 1

Hafsa Hussein Mohammed Technically, each recursive call represents a new call stack, which would likely account for 15 steps at a high level.

That said, I'm not sure I understand your question. Are you asking how to minimize the number of call stacks required within this recursive function?

Or are you asking if there is a more efficient algorithm to implement fibonacci sequence?

Is the goal to remain purely functional where values are always computed or can state be used to store a cache of computed values?

Answer 2

Ipang ok thanks

Answer 3

Another option is you could use the Fibonacci formula in a single stack: 😉

https://code.sololearn.com/WGg96GTxSGJ6/?ref=app

Answer 4

David Carroll thanks sir my question is as you know the output of this code is 8 and to calculate this 8 manually i have to do 6 steps is there shorter way or rule to get the output

Answer 5

David Carroll i viewed it know thanks

Answer 6

David Carroll Gordon

Answer 7

fib = [1, 1, 2, 3, 5, 8, 13, 21,... ]
each number is sum of previous two.
just 1+1 =2, 1+2=3, 2+3=5,...

Answer 8

Hafsa Hussein Mohammed Did you see my earlier post with the link to Fibonacci by Formula?

Answer 9

The most direct and universal approach is to add memoisation:
Create a global array of size maxn (or map) called memo for storing values which have already been calculated Then:
function fib(num){
if(memo[num]!=undefined)
return memo[num]
else if (num<=2){
memo[num]=1
return 1
}
else{
memo[num]=fib(num-1)+fib(num-2)
return memo[num]
}}

Answer 10

The quickest way is get the result directly from a pre-calculated lookup table.

var result = [2, 3, 5, ....];
console.log(result[num]);