python - Fibonacci Computing Time Difference

Question

I wrote the following two codes for computing an element of the Fibonacci Sequence.

def fib(n):
    zero, one = 0, 1
    k = 1
    while k < n:
        zero, one = one, zero + one
        k = k + 1
    return one, ls

def fib2(n, memo=None):
    if memo is None:
        memo = {}
    if n == 1 or n == 2:
        return 1
    if n in memo:
        return memo[n]
    else:
        memo[n-1] = fib2(n-1, memo)
        memo[n-2] = fib2(n-2, memo)
        return memo[n-1] + memo[n-2]


##import timeit
##
##print('Fibonacci 1:', timeit.timeit('fib(10000)', '''def fib(n):
##    zero, one = 0, 1
##    k = 1
##    while k < n:
##        zero, one = one, zero + one
##        k = k + 1
##    return one''', number=100))
##
##print('Fibonacci 2:', timeit.timeit('fib2(10000)', '''import sys; sys.setrecursionlimit(10001);
##def fib2(n, memo=None):
##    if memo is None:
##        memo = {}
##    if n == 0 or n == 1:
##        return 1
##    if n in memo:
##        return memo[n]
##    else:
##        memo[n-1] = fib2(n-1, memo)
##        memo[n-2] = fib2(n-2, memo)
##        return memo[n-1] + memo[n-2]''', number=100))

I am using a simple while loop in fib and fib2 is a recursive implementation of the same. But it turns out that fib2 is exceptionally slower. I want to know why it is. Is it because fib2 creates a whole lot of frames? Have I implemented fib2 correctly?

Thanks.

This is basically a duplicate of http://stackoverflow.com/questions/21710756/recursion-vs-iteration-fibonacci-sequence — ChatterOne, Apr 13 '16 at 11:35
It doesn't matter, the difference is between recursion and iteration. Read the accepted answer carefully and you'll see that the programming language doesn't matter. — ChatterOne, Apr 13 '16 at 11:36
Recursion is slower in general because of the stack frames as you've figured out. It's harder to say by how much in higher level languages such as python, but slower nevertheless. Something that may be slowing your program down is the way you memoize `fib2`. Take a look at the `lru_cache` decorator from `functools` instead of doing your own memoization (I didn't take the time to look at how you memoize, but if you're doing it wrong, it's sure to have an impact on speed). — Pavlin, Apr 13 '16 at 11:37
@ChatterOne His question is not specifically about recursion vs iteration, but more of iteration vs memoized recursion. The question you have linked to talks generally about recursion vs iteration but has no mention of memoization. — Pavlin, Apr 13 '16 at 11:39
@ChatterOne the one from your link does not use dynamic programming — timgeb, Apr 13 '16 at 11:44

cdlane · Accepted Answer · 2016-04-13T22:12:25.083

Time this streamlined recursive version against your original iterative solution -- first up the recursion limit by ~ 1% to 10%:

def fib2(n, memo={0: None, 1: 1, 2: 1}):
    if n in memo:
        return memo[n]

    previous = fib2(n - 1)  # implicitly computes fib2(n - 2)

    result = memo[n] = previous + memo[n - 2]

    return result

I'm not passing memo as an argument on the recursion as I'm taking advantage of the "problem" when default arguments are set to structures that can be modified.

The above solution is ~ 4.5x slower than the original iterative one on my machine on the first invocation -- after that, memoization takes over. We can improve on this a little bit, in both space & time, by changing our "memory" from a dictionary to a list since all the keys are sequential integers:

def fib3(n, memo=[None, 1, 1]):
    if n < len(memo):
        return memo[n]

    previous = fib3(n - 1)  # implicitly computes fib3(n - 2)

    result = previous + memo[-2]

    memo.append(result)

    return result

This one times out at ~ 3x slower than the iterative solution, on my machine, for the first invocation. However, we can do better speed-wise using recursion:

def fib4(n, res=0, nxt=1):
    if n == 0:
        return res
    return fib4(n - 1, nxt, res + nxt)

This is only ~ 2x slower than the iterative solution and/but has no memoization. In a language with tail call optimization (i.e. not Python), this would likely become/tie iteration.

python - Fibonacci Computing Time Difference

1 Answers1