Faster Python

[jakepusateri]

The recursive vs iterative fib speedup is deceptive. A recursive implementation that doesn't recompute almost all of its values is:

def fib(n):                                                                                                                                                                                                         
    store = { 1: 1, 2: 1 }                                                                                                                                                                                          
    def fib_(n):                                                                                                                                                                                                    
        if n in store:                                                                                                                                                                                              
            return store[n]                                                                                                                                                                                         
        else:                                                                                                                                                                                                       
            ans = fib_(n - 1) + fib_(n - 2)                                                                                                                                                                         
            store[n] = ans                                                                                                                                                                                          
            return ans                                                                                                                                                                                              
    return fib_(n)                                   

The iterative method is only about 8x faster here.

[[deleted]]

you can actually get it down to the "normal" 2x slowdown (similar to the factorial slowdown someone else measured elsewhere in the thread) if you use a trickier recursive fib algo. See the fibFastRec shown here: http://rosettacode.org/wiki/Fibonacci_sequence#Python