Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# tmoertel/gist:5798134

Last active Jun 4, 2020
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) # <-- note  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) 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()
to join this conversation on GitHub. Already have an account? Sign in to comment