Recursion problem

Question

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.

Answer 1

Check this how recursion work.

https://www.sololearn.com/discuss/1149517/?ref=app

Answer 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.

Answer 3

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.

Answer 4

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!

Answer 5

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)

Answer 6

I understand, YOU (your brain) want to solve it quickly 😂 well done Russ

Answer 7

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?

Answer 8

Pulkit Kamboj Sorry, I don't know if there is any method to do this mentally quickly.

Answer 9

thanks Maninder Singh

Answer 10

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.

Answer 11

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

Answer 12

Ok, thanks