Re: Why is recursion so slow?

In case anyone is interested...

# Retrieved from: http://en.literateprograms.org/Fibonacci_numbers_(Python)?oldid=10746

# Recursion with memoization
memo = {0:0, 1:1}
def fib(n):
if not n in memo:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]

# Quick exact computation of large individual Fibonacci numbers

def powLF(n):
if n == 1: return (1, 1)
L, F = powLF(n/2)
L, F = (L**2 + 5*F**2) >> 1, L*F
if n & 1:
return ((L + 5*F)>>1, (L + F) >>1)
else:
return (L, F)

def fib(n):
return powLF(n)[1]
.

Quantcast