tmoertel / gist:5798134

Last active October 06, 2013

# Transforming the vanilla recursive fib into the iterative DP version
# through a series of mechanical steps.
#
# For more on converting recursive algorithms into iterative ones, see:
# http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html
 
 
# original function
 
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
 
 
# partition the function into base-case logic and incremental logic
 
def fib(n):
    if n < 2:
        return n
    return step(n)
 
def step(n):
    return fib(n - 1) + fib(n - 2)
 
 
# expand step logic into its fundamental operations
 
def step(n):
    fibn1 = fib(n - 1)
    fibn2 = fib(n - 2)
    result = fibn1 + fibn2
    return result
 
 
# extend step logic with optional arg that eliminates recursion if provided
 
def step(n, fibn1n2=None):
    if fibn1n2 is not None:
        fibn1, fibn2 = fibn1n2
    else:
        fibn1 = fib(n - 1)
        fibn2 = fib(n - 2)
    result = fibn1 + fibn2
    return result
 
 
# make step logic also return its arguments
 
def fib(n):
    if n < 2:
        return n
    return step(n)[0]  # <-- note [0]
 
def step(n, fibn1n2=None):
    if fibn1n2 is not None:
        fibn1, fibn2 = fibn1n2
    else:
        fibn1 = fib(n - 1)
        fibn2 = fib(n - 2)
    result = fibn1 + fibn2
    return result, n, fibn1n2  # <-- and, correspondingly, here
 
 
# now apply to those returned arguments the *opposite* of the
# transformation that was applied to them in the recursive calls
 
def fib(n):
    if n < 2:
        return n
    return step(n)[0]
 
def step(n, fibn1n2=None):
    if fibn1n2 is not None:
        fibn1, fibn2 = fibn1n2
    else:
        fibn1 = fib(n - 1)
        fibn2 = fib(n - 2)
    result = fibn1 + fibn2
    return result, n + 1, (result, fibn1)  # <-- look here
 
 
# now the step logic can be run in the *opposite* direction,
# building from the initial conditions upward via iteration;
# we modify the base logic to do this instead of using the
# step logic recursively
 
def fib(n):
    if n < 2:
        return n
    # initial conditions
    N = n
    n = 2
    fibn1n2 = (1, 0)
    # iterate upward from initial conditions
    while n <= N:
        result, n, fibn1n2 = step(n, fibn1n2)
    return result
 
 
# since the step logic is always called with the fibn1n2 argument now,
# make that argument required to simplify the step logic
 
def step(n, fibn1n2):
    fibn1, fibn2 = fibn1n2
    result = fibn1 + fibn2
    return result, n + 1, (result, fibn1)
 
 
# inline the step logic back into the original function
 
def fib(n):
    if n < 2:
        return n
    # initial conditions
    N = n
    n = 2
    fibn1n2 = (1, 0)
    # iterate upward from initial conditions
    while n <= N:
        fibn1, fibn2 = fibn1n2
        result = fibn1 + fibn2
        result, n, fibn1n2 = result, n + 1, (result, fibn1)
    return result
 
 
# simplify
 
def fib(n):
    if n < 2:
        return n
    fibn1, fibn2 = (1, 0)
    for _ in xrange(2, n + 1):
        result = fibn1 + fibn2
        fibn1, fibn2 = result, fibn1
    return result
 
 
# simplify more
 
def fib(n):
    fibn1, fibn2 = (1, 0)
    for _ in xrange(n):
        fibn1, fibn2 = fibn1 + fibn2, fibn1
    return fibn2
 
 
# and we're done!
 
 
# tests
 
def test():
    fns = dict(globals())
    for fname, f in sorted(fns.iteritems()):
        if fname.startswith('fib'):
            print('testing {}'.format(fname))
            assert map(f, range(10)) == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
if __name__ == '__main__':
    test()