Can every recursion be converted into iteration?

Question

A reddit thread brought up an apparently interesting question:

Tail recursive functions can trivially be converted into iterative functions. Other ones, can be transformed by using an explicit stack. Can every recursion be transformed into iteration?

The (counter?)example in the post is the pair:

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

Answer 1

Removing recursion is a complex problem and is feasible under well defined circumstances.

The below cases are among the easy:

• tail recursion
• direct linear recursion

Answer 2

All computable functions can be computed by Turing Machines and hence the recursive systems and Turing machines (iterative systems) are equivalent.

Answer 3

Have a look at the following entries on wikipedia, you can use them as a starting point to find a complete answer to your question.

• Recursion in computer science
• Recurrence relation

Follows a paragraph that may give you some hint on where to start:

Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function of n.

Also have a look at the last paragraph of this entry.

Answer 4

Here is an iterative algorithm:

def howmany(x,y)
  a = {}
  for n in (0..x+y)
    for m in (0..n)
      a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
    end
  end
  return a[[x,y]]
end

Answer 5

Appart from the explicit stack, another pattern for converting recursion into iteration is with the use of a trampoline.

Here, the functions either return the final result, or a closure of the function call that it would otherwise have performed. Then, the initiating (trampolining) function keep invoking the closures returned until the final result is reached.

This approach works for mutually recursive functions, but I'm afraid it only works for tail-calls.

http://en.wikipedia.org/wiki/Trampoline_(computers)

Answer 6

Yes, using explicitly a stack (but recursion is far more pleasant to read, IMHO).