+ 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

16th May 2019, 8:48 AM
Hafsa Mohamed
Hafsa Mohamed - avatar
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?
16th May 2019, 8:23 PM
David Carroll
David Carroll - avatar
+ 5
Ipang ok thanks
16th May 2019, 8:55 AM
Hafsa Mohamed
Hafsa Mohamed - avatar
+ 5
Another option is you could use the Fibonacci formula in a single stack: 😉 https://code.sololearn.com/WGg96GTxSGJ6/?ref=app
16th May 2019, 11:01 PM
David Carroll
David Carroll - avatar
+ 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
17th May 2019, 4:03 AM
Hafsa Mohamed
Hafsa Mohamed - avatar
+ 5
David Carroll i viewed it know thanks
17th May 2019, 4:38 AM
Hafsa Mohamed
Hafsa Mohamed - avatar
16th May 2019, 12:28 PM
Hafsa Mohamed
Hafsa Mohamed - avatar
+ 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,...
16th May 2019, 3:59 PM
Gordon
Gordon - avatar
+ 3
Hafsa Hussein Mohammed Did you see my earlier post with the link to Fibonacci by Formula?
17th May 2019, 4:30 AM
David Carroll
David Carroll - avatar
+ 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] }}
28th May 2019, 11:39 AM
michal
+ 1
The quickest way is get the result directly from a pre-calculated lookup table. var result = [2, 3, 5, ....]; console.log(result[num]);
17th May 2019, 12:29 AM
CalviŐ˛
CalviŐ˛ - avatar