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 stackoverflow.com/questions/21710756/… — ChatterOne
– ChatterOne, Commented Apr 13, 2016 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
– ChatterOne, Commented Apr 13, 2016 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
– Pavlin, Commented Apr 13, 2016 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
– Pavlin, Commented Apr 13, 2016 at 11:39

cdlane · Accepted Answer · 2016-04-13 22:12:25Z

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.

Collectives™ on Stack Overflow

python - Fibonacci Computing Time Difference

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related