+ 9
How to solve the recursive functions quickly
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
10 Answers
+ 6
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?
+ 5
Ipang ok thanks
+ 5
Another option is you could use the Fibonacci formula in a single stack: đ
https://code.sololearn.com/WGg96GTxSGJ6/?ref=app
+ 5
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
+ 5
David Carroll i viewed it know thanks
+ 3
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,...
+ 3
Hafsa Hussein Mohammed Did you see my earlier post with the link to Fibonacci by Formula?
+ 3
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]
}}
+ 1
The quickest way is get the result directly from a pre-calculated lookup table.
var result = [2, 3, 5, ....];
console.log(result[num]);