+ 1

Recursion problem

I have attempted a problem of sololearn quiz but i was not able to answer it. Here is the problem: def fb(n): if n==0: return 0 if n==1: return 1 else: return(fb(n-1)+fb(n-2)) print(fb(5)) I want to solve it quickly as the time given for answering a sololearn question is very less.

22nd Jul 2018, 5:54 PM
Pulkit Kamboj
Pulkit Kamboj - avatar
12 odpowiedzi
+ 4
23rd Jul 2018, 1:20 PM
Maninder $ingh
Maninder $ingh - avatar
+ 2
The problem with what you have is that, for every number that gets calculated, it has to re-calculated to work out any numbers higher than it, rather than the number just being remembered. I'm not sure if this is what you wanted, but the following will work: def fb(n): nums = [0,1] for x in range(2, n+1): nums.append(nums[x-2] + nums[x-1]) return nums[n] print(fb(5)) *edited to return 5th fb number.
22nd Jul 2018, 6:22 PM
Russ
Russ - avatar
+ 2
I think I understand your question now - sorry. So fb(5) is equal to fb(4) + fb(3), fb(4) is equal to fb(3) + fb(2) and so on. fb(0) returns 0; fb(1) returns 1; so fb(2) = 0 + 1 = 1; fb(3) = 1 + 1 = 2; fb(4) = 1 + 2 = 3, and fb(5) = 3 + 2 = 5. If you're looking for a shortcut to compute this mentally, I don't know of one, sorry.
22nd Jul 2018, 6:48 PM
Russ
Russ - avatar
+ 2
Pulkit Kamboj I think you may be better off asking in a maths-based forum (reddit for example), or by googling yourself. This code is based on the Fibonacci series and returns the nth element of the series. Good luck in finding it!
22nd Jul 2018, 6:56 PM
Russ
Russ - avatar
+ 1
This is a code a did a while back https://code.sololearn.com/cJx2F7FN6NKW/?ref=app The second one (CleverFibonacci) might be what you're looking for (it's in Java but you can do something similar in Python with a dict)
22nd Jul 2018, 6:37 PM
Dan Walker
Dan Walker - avatar
+ 1
I understand, YOU (your brain) want to solve it quickly 😂 well done Russ
22nd Jul 2018, 6:51 PM
Dan Walker
Dan Walker - avatar
+ 1
thank you so much Russ , no need to say sorry that was exactly what i was saying,Dan Walker is there a short cut to this?
22nd Jul 2018, 6:51 PM
Pulkit Kamboj
Pulkit Kamboj - avatar
+ 1
Pulkit Kamboj Sorry, I don't know if there is any method to do this mentally quickly.
22nd Jul 2018, 6:55 PM
Dan Walker
Dan Walker - avatar
+ 1
23rd Jul 2018, 5:46 PM
Pulkit Kamboj
Pulkit Kamboj - avatar
0
Dan Walker and Russ I think you have not understood my question, i want to know how to get the output of the code(5 in this case) in a quick time.
22nd Jul 2018, 6:40 PM
Pulkit Kamboj
Pulkit Kamboj - avatar
0
Pulkit Kamboj That's what my code does, if you compare the first method (which is exactly what you have) you won't be able to get past fb(40) easily due to the time the computation takes. The second method is much faster, and on a computer you can compute really big Fibonacci numbers almost instantly due to the optimized code
22nd Jul 2018, 6:46 PM
Dan Walker
Dan Walker - avatar
0
Ok, thanks
23rd Jul 2018, 4:33 AM
Pulkit Kamboj
Pulkit Kamboj - avatar