fibo.py

#!/usr/bin/env python

import sys

# Basic recursion
def fibonacci (n):
    def imp (n):
        if n == 0: return 0
        if n == 1: return 1
        return imp(n-1) + imp(n-2)
    return imp(n)

# recursion + memoize
def fibonacci_memoize (n):
    memoize = [0, 1]
    def imp (n):
        if len(memoize) <= n:
            memoize.append(imp(n-1) + imp(n-2))
        return memoize[n] 
    return imp(n)

# Recursion + two slots memoize. already close to loop
def fibonacci_eff_memoize (n):
    memoize = [0, 1, 0]
    def imp (n):
        if memoize[2] + 2 <= n:
            val = imp(n-1) + imp(n-2)
            memoize[:] = [memoize[1], val, n-1]
        return memoize[n-memoize[2]] 
    return imp(n)

# Python recursion depth is limitted. half loop + half recursion
def fibonacci_eff_memoize_recusion_limit (n):
    memoize = [0, 1, 0]
    def imp (n):
        if memoize[2] + 2 <= n:
            val = imp(n-1) + imp(n-2)
            memoize[:] = [memoize[1], val, n-1]
        return memoize[n-memoize[2]] 
    recursion_limit = 500
    for i in range(1, int(n / recursion_limit)):
        imp(i * recursion_limit)
    return imp(n)


n = 99
if len(sys.argv) > 1:
    n = int(sys.argv[1])

print(fibonacci_eff_memoize_recusion_limit(n))
#print(fibonacci_eff_memoize(n))
#print(fibonacci_memoize(n))
#print(fibonacci(n))