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

Solution 1

Can you always turn a recursive function into an iterative one? Yes, absolutely, and the Church-Turing thesis proves it if memory serves. In lay terms, it states that what is computable by recursive functions is computable by an iterative model (such as the Turing machine) and vice versa. The thesis does not tell you precisely how to do the conversion, but it does say that it's definitely possible.

In many cases, converting a recursive function is easy. Knuth offers several techniques in "The Art of Computer Programming". And often, a thing computed recursively can be computed by a completely different approach in less time and space. The classic example of this is Fibonacci numbers or sequences thereof. You've surely met this problem in your degree plan.

On the flip side of this coin, we can certainly imagine a programming system so advanced as to treat a recursive definition of a formula as an invitation to memoize prior results, thus offering the speed benefit without the hassle of telling the computer exactly which steps to follow in the computation of a formula with a recursive definition. Dijkstra almost certainly did imagine such a system. He spent a long time trying to separate the implementation from the semantics of a programming language. Then again, his non-deterministic and multiprocessing programming languages are in a league above the practicing professional programmer.

In the final analysis, many functions are just plain easier to understand, read, and write in recursive form. Unless there's a compelling reason, you probably shouldn't (manually) convert these functions to an explicitly iterative algorithm. Your computer will handle that job correctly.

I can see one compelling reason. Suppose you've a prototype system in a super-high level language like [donning asbestos underwear] Scheme, Lisp, Haskell, OCaml, Perl, or Pascal. Suppose conditions are such that you need an implementation in C or Java. (Perhaps it's politics.) Then you could certainly have some functions written recursively but which, translated literally, would explode your runtime system. For example, infinite tail recursion is possible in Scheme, but the same idiom causes a problem for existing C environments. Another example is the use of lexically nested functions and static scope, which Pascal supports but C doesn't.

In these circumstances, you might try to overcome political resistance to the original language. You might find yourself reimplementing Lisp badly, as in Greenspun's (tongue-in-cheek) tenth law. Or you might just find a completely different approach to solution. But in any event, there is surely a way.

Solution 2

Is it always possible to write a non-recursive form for every recursive function?

Yes. A simple formal proof is to show that both µ recursion and a non-recursive calculus such as GOTO are both Turing complete. Since all Turing complete calculi are strictly equivalent in their expressive power, all recursive functions can be implemented by the non-recursive Turing-complete calculus.

Unfortunately, I’m unable to find a good, formal definition of GOTO online so here’s one:

A GOTO program is a sequence of commands P executed on a register machine such that P is one of the following:

• HALT, which halts execution
• r = r + 1 where r is any register
• r = r – 1 where r is any register
• GOTO x where x is a label
• IF r ≠ 0 GOTO x where r is any register and x is a label
• A label, followed by any of the above commands.

However, the conversions between recursive and non-recursive functions isn’t always trivial (except by mindless manual re-implementation of the call stack).

For further information see this answer.

Solution 3

Recursion is implemented as stacks or similar constructs in the actual interpreters or compilers. So you certainly can convert a recursive function to an iterative counterpart because that's how it's always done (if automatically). You'll just be duplicating the compiler's work in an ad-hoc and probably in a very ugly and inefficient manner.

Solution 4

Basically yes, in essence what you end up having to do is replace method calls (which implicitly push state onto the stack) into explicit stack pushes to remember where the 'previous call' had gotten up to, and then execute the 'called method' instead.

I'd imagine that the combination of a loop, a stack and a state-machine could be used for all scenarios by basically simulating the method calls. Whether or not this is going to be 'better' (either faster, or more efficient in some sense) is not really possible to say in general.

Solution 5

• Recursive function execution flow can be represented as a tree.

• The same logic can be done by a loop, which uses a data-structure to traverse that tree.

• Depth-first traversal can be done using a stack, breadth-first traversal can be done using a queue.

So, the answer is: yes. Why: https://stackoverflow.com/a/531721/2128327.

Can any recursion be done in a single loop? Yes, because

a Turing machine does everything it does by executing a single loop:

1. fetch an instruction,
2. evaluate it,
3. goto 1.

View more solutions

Comments

[Matthew Flaschen]

I don't see how this is a counter-example. The stack technique will work. It won't be pretty, and I'm not going to write it, but it is doable. It appears akdas acknowledges that in your link.

[Henk Holterman]

Duplicate of: stackoverflow.com/questions/531668

[Déjà vu]

I would say that recursion is merely a convenience.

[arghtype]

Possible duplicate of Which recursive functions cannot be rewritten using loops?

[Khaled.K]

The other thing I might ask is.. wouldn't the compiler be able to turn recursion into iteration?

[Matthew Flaschen]

I wouldn't say it's always more pleasant to read. Both iteration and recursion have their place.

[Liran Orevi]

Isn't Church-Turing yet to be proven?

[Ian]

Here's a really short outline: pick two models of computation A and B. Prove that A is at least as powerful as B by writing an interpreter of B using A. Do this in both directions, and you have shown that A and B have equivalent power. Consider that machine code is almost the Turing-machine model, and that lisp interpreters/compilers exist. The debate should be over. But for more information, see: alanturing.net/turing_archive/pages/Reference%20Articles/…

[Tim]

I think the OP is looking for a proof or something else substantive

[eyelidlessness]

Ian, I'm not sure that proves each has equivalent power, only that each uses equivalent power. Use demonstrates certain capabilities, but not necessarily the extent of them.

[Tordek]

@eyelidlessness: If you can implement A in B, it means B has at least as much power as A. If you cannot execute some statement of A in the A-implementation-of-B, then it's not an implementation. If A can be implemented in B and B can be implemented in A, power(A) >= power(B), and power(B) >= power(A). The only solution is power(A) == power(B).

[Nils]

Great answer! However in practice I have great difficulty turing recursive algos into iterative ones. For example I was unable so far to turn the monomorphic typer presented here community.topcoder.com/… into an iterative algorithm

[T. Webster]

Would this answer depend on how restrictive the (iterative) language is? What if the language has very limited use of GOTO statements? How is it possible for the program to "remember" the instruction at which the recursion/iteration was last called from without some kind of return address?

[Voo]

@T.Webster You can't get much more limited than a Turing Machine - gotos? ha waaay too advanced feature. You can look at the informal definition to see what you need to get the same power as any modern iterative programming language.

[sdcvvc]

re: 1st paragraph: You are speaking about equivalence of models of computation, not the Church-Turing thesis. The equivalence was AFAIR proved by Church and/or Turing, but it is not the thesis. The thesis is an experimental fact that everything intuitively computable is computable in strict mathematical sense (by Turing machines/recursive functions etc.). It could be disproven if using laws of physics we could build some nonclassical computers computing something Turing machines cannot do (e.g. halting problem). Whereas the equivalence is a mathematical theorem, and it will not be disproven.

[ex0du5]

How the heck did this answer get any positive votes? First it mixes up Turing completeness with the Church-Turing thesis, then it makes a bunch of incorrect handwaving, mentioning "advanced" systems and dropping lazy infinite tail recursion (which you can do in C or any Turing complete language because.. uh.. does anyone know what Turing complete means?). Then a hopeful hand-holding conclusion, like this was a question on Oprah and all you need is to be positive and uplifting? Horrid answer!

[ex0du5]

And the bs about semantics??? Really? This is a question on syntactic transformations, and somehow it's became a great way to name drop Dijkstra and imply you know something about the pi-calculus? Let me make this clear: whether one looks at the denotational semantics of a language or some other model will have no bearing on the answer to this question. Whether the language is assembly or a generative domain modeling language means nothing. Its only about Turing completeness and transforming "stack variables" to "a stack of variables".

[morpheus]

If any recursive function can be transformed into a non-recursive version, then why don't compilers do this? It is common advice to write non-recursive methods if possible because of performance overhead and SO issues with a recursive method.

[Ian]

@morpheus, in fact compilers for functional languages (and many lisps) routinely apply several techniques to automatically convert a large category of recursive-looking definitions into object code that doesn't overuse stack space. But in any event, object code can be considered as iterative by considering the CPU to run a fetch-execute iteration.

[conradkleinespel]

Which either defeats the purpose if your stack data structure is allocated on the stack, or takes way longer if it's allocated on the heap, no? That sounds trivial but inefficient to me.

[Wheezil]

Some other practical reasons for converting recursive functions to other implementations: (1) You want to write an iterator class over a complex data structure, but you don't have the equivalent of C#'s yield. (2) You have many executing co-processes, and you do not want to (or cannot) implement them as separate threads. This is seen in algorithms for executing data-flow graphs, where assigning a thread to each vertex may be impractical.

[8bittree]

@morpheus Iteration isn't magic. If a recursive function calls itself more than once during a single call (e.g. merge sort), then it requires unbounded memory space, and implementing it via iteration won't change that, you'll just be manually managing a stack. But, many naturally recursive algorithms only call themselves once per call and can be written as a tail call. Tail calls can work in fixed memory space, but require special treatment from the compiler. Telling users to manually convert to iteration means compiler writers can do other stuff.

[jamesdlin]

@conradk In some cases, it's the practical thing to do if you must perform some tree-recursive operation on a problem that is sufficiently large to exhaust the call stack; heap memory is typically much more plentiful.

[user1870400]

How about the inverse? Can you always turn a iterative function into an recursive one?

[Ian]

@user1870400 ,yes, you can. By one definition, iterative functions are primitive-recursive to begin with. But if your goal is to write it without explicit looping constructs, then a correspondingly-designed recursive call stands in for the construct. The details are part of any course on functional programming.

[user721025]

[donning asbestos underwear] deserves 50 points in itself. :-)

[Ian]

@user1870400 an iterative function is already a (primitive-)recursive function. The operation is vacuous.

[ImBatman]

@Ian Knuth offers several techniques in "The Art of Computer Programming". Could You please tell which volume of the book you are talking about? Also, could you please tell any other source which tells a general techniques to avoid recursion?

[Ron Inbar]

The Church-Turing thesis is an informal hypothesis that anything that can be computed by any kind of algorithm, including kinds that haven't been discovered or invented yet, can be computed by a Turing machine. Since there is no formal definition of "any kind of algorithm", the C-T thesis is not a mathematical theorem. What is a theorem (proven by Church and Turing) is the equivalence between Turing machines and Church's lambda calculus.

[Milos]

@Ian I'd also like to know which TAOCP volume you were referring to.