recursion vs iteration

[Isaac To]

>>>>> "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.