3

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?

Improve this question
3
  • Remove the memo and check the difference then... Commented Jan 13, 2021 at 7:38
  • 1
    If you do not provide any number to timeit, the code will be averaged over number=1000000 executions (see here). 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. Commented Jan 13, 2021 at 7:46
  • stackoverflow.com/q/1132941/3929826 Commented Jan 13, 2021 at 8:35

1 Answer 1

Reset to default
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
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

I didn't knew that the timeit function reuses the memo variable again. Isn't it a local variable?
@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?
Wow that is really surprising. I didn't knew that the default value is shared and reused every time...
@GulimProject see 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)
@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.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.