Why is recursion so slow?

[cokofreedom at gmail.com]

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]