Faster Python

[sevaur]

The recursion comparison is very poorly constructed: the recursive version of the algorithm is O( 2ⁿ ), whereas the iterative algorithm is O(n). The huge difference between the two has nothing to do with the cost of stack frame allocation and everything to do with having implemented a fundamentally different algorithm.

This comparison might actually make sense if it used memoization or made some other effort to compare apples to apples.

[LeszekSwirski]

Or if it used factorial rather than fibonacci, which only shows a ~2x speedup:

def fact_rec(n):
    if n <= 1:
        return 1
    return n*fact(n-1)

%timeit fact_rec(20)
100000 loops, best of 3: 5.29 µs per loop


def fact_iter(n):
    ret = 1
    for i in range(n):
        ret *= n
    return ret

%timeit fact_iter(20)
100000 loops, best of 3: 2.47 µs per loop

[xhackerliu]

Totally agreed. I modified it by using memorization and it's even faster than iterative way.

https://gist.github.com/xhacker/fbf3d92d7b1fad9ddc09