How to transform the vanilla recursive fib function into the iterative DP version through a series of mechanical steps.
# 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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment