Can every recursion be converted into iteration?

0 votes
asked May 31, 2009 by tordek

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

19 Answers

0 votes
answered Jan 2, 2009 by sfussenegger

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

0 votes
answered Jan 2, 2009 by heinzi

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.

0 votes
answered Jan 2, 2009 by gabriel-magana

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

As to justifying your answer, you gotta do that, it's your homework assignment ;-)

0 votes
answered Jan 2, 2009 by alberto-zaccagni

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.

0 votes
answered Jan 8, 2009 by zayenz

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.

0 votes
answered Jan 31, 2009 by dfa

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

0 votes
answered Jan 31, 2009 by nick-dandoulakis

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

The below cases are among the easy:

0 votes
answered Jan 31, 2009 by chris-vest

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)

0 votes
answered Jan 31, 2009 by jules

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
0 votes
answered Jan 31, 2009 by matthias-wandel

Sometimes replacing recursion is much easier than that. Recursion used to be the fashionable thing taught in CS in the 1990's, and so a lot of average developers from that time figured if you solved something with recursion, it was a better solution. So they would use recursion instead of looping backwards to reverse order, or silly things like that. So sometimes removing recursion is a simple "duh, that was obvious" type of exercise.

This is less of a problem now, as the fashion has shifted towards other technologies.

Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter

...