# Can every recursion be converted into iteration?

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))
``````

I'd say yes - a function call is nothing but a goto and a stack operation (roughly speaking). All you need to do is imitate the stack that's built while invoking functions and do something similar as a goto (you may imitate gotos with languages that don't explicitly have this keyword too).

Yes, it's always possible to write a non-recursive version. The trivial solution is to use a stack data structure and simulate the recursive execution.

Homework question, huh?

What I remember from CS coursework was that tail-end recursion is always writeable as non-recursive, other types of recursion may be, but it's not an absolute rule...

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.

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.

In principle it is always possible to remove recursion and replace it with iteration in a language that has infinite state both for data structures and for the call stack. This is a basic consequence of the Church-Turing thesis.

Given an actual programming language, the answer is not as obvious. The problem is that it is quite possible to have a language where the amount of memory that can be allocated in the program is limited but where the amount of call stack that can be used is unbounded (32-bit C where the address of stack variables is not accessible). In this case, recursion is more powerful simply because it has more memory it can use; there is not enough explicitly allocatable memory to emulate the call stack. For a detailed discussion on this, see this discussion.

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

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

The below cases are among the easy:

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)

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
``````