public
Last active

How to transform the vanilla recursive fib function into the iterative DP version through a series of mechanical steps.

  • Download Gist
gistfile1.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160
# 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()

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.