Why python fibonacci sequence loop is slower than recursion?

Question

Below is the well-known example of fibonacci sequence

# test.py
import sys
sys.setrecursionlimit(20000)

def fib_loop(n):
    if n <= 1:
        return n
    fn, fnm1 = 1, 0
    for _ in range(2, n+1):
        fn, fnm1 = fn + fnm1, fn
    return fn

def fib_recursion(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_recursion(n-1, memo) + fib_recursion(n-2, memo)
    return memo[n]

As everybody does, I used to think that the loop variant will be much faster than the recursive one. However, the actual result is quite surprising.

$ python3 -m timeit "import test; test.fib_loop(10000)"
100 loops, best of 5: 1.93 msec per loop
$ python3 -m timeit "import test; test.fib_recursion(10000)"
500000 loops, best of 5: 471 nsec per loop

I have no idea why. Could anybody help me?

If you do not provide any number to timeit, the code will be averaged over `number=1000000` executions ([see here](https://docs.python.org/3/library/timeit.html#timeit.timeit)). You memoize the results so for 999999 trys it is simply an O(1) lookup into the (once) generated dict whereas the loop has to recalculate the numbers 1000000 times. — Patrick Artner, Jan 13 '21 at 07:46

juanpa.arrivillaga · Accepted Answer · 2021-01-13T07:54:18.260

3

Because you are memoizing your result. And you are re-using that memo dict on every iteration. So the first time it runs it is slow. On every other invoctation, it is a simple dict-lookup.

If you use number=1 so it only runs just once, you'll see the first call is actually slower

>>> import sys
>>> sys.setrecursionlimit(20000)
>>>
>>> def fib_loop(n):
...     if n <= 1:
...         return n
...     fn, fnm1 = 1, 0
...     for _ in range(2, n+1):
...         fn, fnm1 = fn + fnm1, fn
...     return fn
...
>>> def fib_recursion(n, memo={}):
...     if n <= 1:
...         return n
...     if n not in memo:
...         memo[n] = fib_recursion(n-1, memo) + fib_recursion(n-2, memo)
...     return memo[n]
...
>>> import timeit
>>> timeit.timeit("fib_loop(1000)", setup="from __main__ import fib_loop", number=1)
9.027599999456015e-05
>>> timeit.timeit("fib_recursion(1000)", setup="from __main__ import fib_recursion", number=1)
0.0016194200000114733

Alternatively, if you pass a new memo dict for each outer call, you get the same behavior:

>>> timeit.timeit("fib_recursion(1000, {})", setup="from __main__ import fib_recursion", number=1000)
0.38679519899999093
>>> timeit.timeit("fib_loop(1000)", setup="from __main__ import fib_loop", number=1000)
0.07079556799999409

edited Jan 13 '21 at 07:54

answered Jan 13 '21 at 07:36

juanpa.arrivillaga

88,713
10
131
172

I didn't knew that the timeit function reuses the `memo` variable again. Isn't it a local variable? – jnooree Jan 13 '21 at 07:45
1

@GulimProject the scope of the *variable* is irrelevant, it is re-using the *same object* every time. That is normally how memoization would work anyway, how else would it work? – juanpa.arrivillaga Jan 13 '21 at 07:46
Wow that is really surprising. I didn't knew that the default value is shared and reused every time... – jnooree Jan 13 '21 at 07:48
1

@GulimProject see [why-are-default-arguments-evaluated-at-definition-time](https://stackoverflow.com/questions/1651154/why-are-default-arguments-evaluated-at-definition-time) - the dict is created once on function definition and persists until you restart the file with python. It is a common error when providing functions with list or dict "defaults" hence you normally provide a None as default and do a "defaultlist = defaultlist or []" inside the function if you do not want this behaviour (unless you want it,then you are fine using it as is) – Patrick Artner Jan 13 '21 at 07:48
@juanpa.arrivillaga No it would work even if does not, because I'm passing `memo` as argument in the recursive call. The interesting part is that even if I don't pass it, the function still **memorizes** the result. – jnooree Jan 13 '21 at 07:51
@GulimProject ahhh yes. OK, so if you actually manually pass it then you might get the behavior you expect – juanpa.arrivillaga Jan 13 '21 at 07:51
@PatrickArtner Thanks for explanation. This is the part I've missed. – jnooree Jan 13 '21 at 07:51

Why python fibonacci sequence loop is slower than recursion?

1 Answers1