I wrote a recursive solution for something today, and as it goes, curiosity led me down a weird path. I wanted to see how an optimized recursive solution compares to an iterative solution so I chose a classic, the Nth Fibonacci to test with.

I was surprised to find that the recursive solution with memoization is much faster than the iterative solution and I would like to know why.

Here is the code (using python3):

import time
import sys
sys.setrecursionlimit(10000)

## recursive:
def fibr(n, memo = {}):
    if n <= 1:
        return n

    if n in memo:
        return memo[n]

    memo[n] = fibr(n-1, memo)   fibr(n-2, memo)

    return memo[n]

## iterative:
def fibi(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a   b
    return a

rstart = time.time()
for n in range(10000):
    fibr(n)
rend = time.time()

istart = time.time()
for n in range(10000):
    fibi(n)
iend = time.time()

print(f"recursive: {rend-rstart}")
print(f"iterative: {iend-istart}")

My results:

recursive: 0.010010004043579102
iterative: 6.274333238601685

Unless I'm mistaken, both the recursive solution and the iterative solution are about as optimized as they can get? If I'm wrong about that, I'd like to know why.

If not, what would cause the iterative solution to be so much slower? It seems to be slower for all values of n, but harder to notice when n is something more reasonable, like <1000. (I'm using 10000 as you can see above)

Some things I've tried:

1. I thought it might be the magic swapping in the iterative solution a, b = b, a b, so I tried replacing it with a more traditional "swap" pattern:

tmp = a   b     
a = b           
b = tmp         
#a, b = b, a   b

But the results are basically the same, so that's not the problem there.

2. Re-arrange the code so that the iterative solution runs first, just to see if there was some weird cache issue at the OS level? It doesn't change the results so that's not it, probably?

My understanding here (and it might be wrong) is that the recursive solution with memoization is O(n). And the iterative solution is also O(n) simply because it iterates from 0..n.

Am I missing something really obvious? I feel like I must be missing something here.

CodePudding user response：

You might expect that def fibr(n, memo = {}): — when called without a supplied memo — turns into something translated a bit like:

def _fibr_without_defaults(n, memo):
   ...

def fibr(n):
    return _fibr_without_defaults(n, {})

That is, if memo is missing it implicitly gets a blank dictionary per your default.

In actuality, it translates into something more like:

def _fibr_without_defaults(n, memo):
   ...

_fibr_memo_default = {}
def fibr(n):
    return _fibr_without_defaults(n, _fibr_memo_default)

That is, a default argument value is not "use this to construct a default value" but instead "use this actual value by default". Every single call to fibr you make (without supplying memo) is sharing a default memo dictionary.

---

That means in:

for n in range(10000):
    fibr(n)

The prior iterations of your loop are filling out memo for the future iterations. When n is 1000, for example, all the work performed by n<=999 is still stored.

By contrast, the iterative version always starts iterating from 0, no matter what work prior iterative calls performed.

---

If you perform the translation above by hand, so that you really do get a fresh empty memo for each call, you'll see the iterative version is faster. (Makes sense; inserting things into a dictionary and retrieving them just to do the same work as simple iteration will be slower.)

CodePudding user response：

They are not the same.

The recursive version uses the Memoization pattern, calculating only once the result of fibr(n) and storing/caching the result for insta-return if needed again. It's an O(n) algorithm.

The iterative version calculates everything from scratch. It's an O(n2) algorithm (I think).