If we find higher fibonaci no (like 40) by recursion it takes a long time . why?

Question

code is

def fib(n):
if(n<2):
return 1
else:
return fib(n-1)+fib(n-2)

Answer 1

yeah, that's exactly what i say ;) good luck

Answer 2

@donkeyhot we calculate all of the previous members of the fibonacci sequence, but we just do it once each time, while the reqursive mode of this algorithm calculate some operations more than this dp algorithm that i say

Answer 3

Ok, i get it. I thought python interpreter is smart enough to store previously calculated values.

https://code.sololearn.com/cVvnJBqQ6FNx/#py

Answer 4

http://www.python-course.eu/recursive_functions.php

Answer 5

well, in recursion mode you calculate some fib(x) that actually you don't need them.
hence for example you should use a dp(dynamic programming) mode for compute the fibonacci instead of the divide and conquer mode, that is faster much more!

Answer 6

if we start to calculate the fibs from first member of fibonacci sequence, we just need the fib(n-1) and fib(n-2) to find fib(n)
so we don't need the other fib members

Answer 7

@donkeyhot - I added a comment to your code with a generator function (to store previously generated values; using in-place swapping). It's not recursive (so OT) but may still be useful.

Answer 8

@donkeyhot - open your code and then tap "1 comment" all the way over on the top right.

Answer 9

@Nima, how are you going to calculate fib(n) without knowing all the previous fib(1) ... fib(n-1)?

Answer 10

And how would you know what fib(n-1) and fib(n-2) is without calculating the previous ones?

Answer 11

@Kirk Schafer
Where can I find this comment?
Sorry for being a noob. I saw a notification, but when i tap on it nothing happens.

Answer 12

giving fibonaci as an example for recursion is...well, a really bad example. You should never use recursion for fib