recursion vs iteration
Isaac To
kkto at csis.hku.hk
Mon Nov 10 07:48:22 CET 2003
>>>>> "David" == David Eppstein <eppstein at ics.uci.edu> writes:
David> Perhaps, for Fibonacci, they are almost the same. For the
David> recursive vs iterative versions of 0-1 knapsack which I posted
David> earlier in this thread, the same values are computed in the same
David> places by the same formula, it's not tail-recursive because there
David> are two subproblem values used in each instance of the formula
David> (anyway we're in a Python group and Python doesn't optimize out
David> tail recursions), and the recursive version computes them in a
David> different order than the iterative one and doesn't compute as
David> many of them.
Hmm... don't keep your eye closed. I mean an *iterative* version can always
be turned into a tail recursion, while you are not talking about the
iterative version. You are talking about the recursive version, which can
be turned into an iteration using a stack. This is what I said exactly:
Isaac> since every iteration can be turned into a tail recursion without
Isaac> losing efficiency (given the appropriate compiler optimization),
Isaac> and every recursion can be turned into an iteration using a
Isaac> stack
To do this basically you turn your program into an interpretor performing
the instruction cycle as a loop; and the stack needed is for the low-level
implementation of the recursion. So instead of
def f(n):
if n == 0: # statement 1
return 1 # statement 2
else
return f(n-1)*n # statement 3/4, recursion
You'd write (untested code, depend on a stack with push and pop
operations...)
def f(n):
s = Stack()
state = [1,n,0] # [statement nr, value of n, return value slot]
s.push(state)
while true: # the loop implementing the instruction cycle
state = s.pop()
if state[0] == 1: # "if n == 0"
if state[1] == 0: # if n == 0
state[0] = 2 # then goto statement 2
else:
state[0] = 3 # else goto statement 3
s.push(state)
else if state[0] == 2: # "return 1"
if s.empty(): # if no more recursion
return 1 # then return 1
laststate=s.pop()
laststate[2] = 1 # else write 1 to return value slot
s.push(laststate)
else if state[0] == 3: # "f(n-1)"
s.push([4, state[1], 0]) # prepare for return
s.push([1, state[1]-1, 0]) # restart execution, n=n-1
else: # "return retval*n"
if s.empty(): # if no more recursion
return state[2]*state[1] # then return retval*n
laststate=s.pop()
laststate[2] = state[2]*state[1] # else write that to return value slot
s.push(laststate)
You can see it involves no recursion, and is completely mechanical. It
works basically for all recursions, including the one you mentioned.
Basically one go back to the principle in which a computer works. Of
course, depending on circumstances it can be optimized a bit. The above
only shows that recursion is not absolutely necessary.
Regards,
Isaac.
More information about the Python-list
mailing list