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?
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