Removing recursion - a look into theory behind the scenes

Question

I am new to this site and this question is certainly not research level - but oh well. I have a little background in software engineering and almost none in CSTheory, but I find it attractive. To make a long story short, I would like a more detailed answer to the following if this question is acceptable on this site.

So, I know that every recursive program has an iterative analog and I kind of understand the popular explanation that is offered for it by maintaining something similar to the "system stack" and pushing environment settings like return address etc. I find this kind of handwavy.

Being a little more concrete, I would like to (formally) see how does one prove this statement in cases where you have a function invoking chain $F_0 \rightarrow F_1 \ldots F_i \rightarrow F_{i+1} \ldots F_n \rightarrow F_0$. Further, what if there are some conditional statements which might lead an $F_i$ make a call to some $F_j$? That is, the potential function call graph has some strongly connected components.

I would like to know how can these situations be handled by let us say some recursive to iterative converter. And is the handwavy description I referred to earlier, really enough for this problem? I mean then why is it that I find removing recursion in some cases easy. In particular removing recursion from pre-order traversal of a Binary tree is really easy - its a standard interview question but removing recursion in case of post order has always been a nightmare for me.

What I am really asking is $2$ questions

(1) Is there really a more formal (convincing?) proof that recursion can be converted to iteration?

(2) If this theory is really out there, then why is it that I find, for eg, iteratizing preorder easier and postorder so hard? (other than my limited intelligence)

Answer 1

If I understand correctly, you are clear about converting functions that contain no other function calls but to themselves.

So assume we have a "call chain" $F \to F_1 \to \dots \to F_n \to F$. If we furthermore assume that $F_1, \dots, F_n$ are not recursive themselves (because we have converted them already), we can inline all those calls into the definition of $F$ which thusly becomes a directly recursive function we can already deal with.

This fails if some $F_j$ has itself a recursive call chain in which $F$ occurs, i.e. $F_j \to \dots \to F \to \dots \to F_j$. In this case, we have mutual recursion which requires another trick to get rid off. The idea is to compute both functions simultaneously. For example, in the trivial case:

f(0) = a
f(n) = f'(g(n-1))

g(0) = b
g(n) = g'(f(n-1))

with f' and g' non-recursive functions (or at least independent of f and g) becomes

h(0) = (a,b)
h(n) = let (f,g) = h(n-1) in (f'(g), g'(f)) end

f(n) = let (f, _) = h(n) in f end
g(n) = let (_, g) = h(n) in g end

This naturally extends to more functions involved and more complicated functions.

Answer 2

Yes, there are convincing reasons to believe that recursion can be turned into iteration. This is what every compiler does when it translates source code to machine language. For theory you should follow Dave Clarke's suggestions. If you would like to see actual code that converts recursion to non-recursive code, have a look at machine.ml in the MiniML language in my PL Zoo (notice that the loop function at the bottom, which actually runs code, is tail recursive and so it can be trivially converted to an actual loop).

One more thing. MiniML does not support mutually recursive functions. But this is not a problem. If you have mutual recursion between functions

$$f_1 : A_1 \to B_1$$ $$f_2 : A_2 \to B_2$$ $$\vdots$$ $$f_n : A_n \to B_n$$

the recursion can be expressed in terms of a single recursive map

$$f : A_1 + \cdots + A_n \to B_1 + \cdots + B_n,$$

Answer 3

You might want to look at the SECD machine. A functional language (though it could be any language) is translated into a series of instructions that manage things such as putting arguments of stacks, "invoking" new functions and so forth, all managed by a simple loop.
Recursive calls are never actually invoked. Instead, the instructions of the body of the function being called is placed on the stack to run.

A related approach is the CEK machine.

These have both been around for a long time, so there's plenty of work out there on them. And of course there are proofs that they work and the procedure for "compiling" a program into SECD instructions is linear in the size of the program (it doesn't have to think about the program).

The point of my answer is that there is an automatic procedure for doing what you want. Unfortunately, the transformation won't necessarily be in terms of things that are immediately easy for a programmer to interpret. I think the key is that when you want to iterize a program, you need to store on the stack what the program needs to do when you return from an iterized function call (this is called a continuation). For some functions (such as tail-recursive functions) the continuation is trivial. For others the continuation maybe very complex, especially if you have to encode it yourself.

Answer 4

Q: "Is there really a more formal (convincing?) proof that recursion can be converted to iteration?"

A: The Turing completeness of a Turing Machine :-)

Jokes apart, the Turing equivalent Random Access stored program (RASP) machine model is close to how real microprocessors work and its instruction set contains only a conditional jump (no recursion). The possibility of dinamically self-modifying the code makes the task of implementing subroutines and recursive calls easier.

I think that you can find many papers/articles on the "recursive to iterative conversion" (see Dave's answer or just Google the keywords), but perhaps a less known (and practical) approach is the latest research on hardware implementation of recursive algorithms (using the VHDL language that is "compiled" directly into a piece of hardware). For example see V.Sklyarov's paper "FPGA-based implementation of recursive algorithms" (The paper suggests a novel method for implementing recursive algorithms in hardware. .... Two practical applications of recursive algorithms in the data sorting and compression area have been studied in detail....). Worth a look.

Answer 5

If you're familiar with languages that support lambdas then one avenue is to look into the CPS transformation. Removing use of the call stack (and recursion in particular) is exactly what the CPS transformation does. It transforms a program containing procedure calls into a program with only tail calls (you can think of these as gotos, which is an iterative construct).

The CPS transformation is closely related to explicitly keeping a call stack in a traditional array based stack, but instead of in an array the call stack is represented with linked closures.

Answer 6

in my opinion this question goes back to the very origins of definitions of computation and was long ago proven rigorously around that time when the church lambda calculus (which highly captures the concept of recursion) was shown to be equivalent to Turing machines, and is contained in the still used terminology "recursive languages/functions". also apparently a later key ref along these lines is as follows

As pointed out by Peter Landin's 1965 paper A Correspondence between ALGOL 60 and Church's Lambda-notation, sequential procedural programming languages can be understood in terms of the lambda calculus, which provides the basic mechanisms for procedural abstraction and procedure (subprogram) application.

much of the bkd on this is in this wikipedia page church-turing thesis. am not sure of the exact specifics but the wikipedia article seems to indicate it was Rosser(1939) who 1st proved this equivalence between lambda calculus and turing machines. maybe/presumably his paper has a stack-like mechanism for converting the (possibly recursive) lambda calls to the tm construction?

Rosser, J. B. (1939). "An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem". The Journal of Symbolic Logic (The Journal of Symbolic Logic, Vol. 4, No. 2) 4 (2): 53–60. doi:10.2307/2269059. JSTOR 2269059.

note of course for anyone interested in the principles the modern Lisp language and the variant Scheme intentionally have a strong resemblance to the lambda calculus. studying the interpreter code for expression evaluation leads to ideas that were originally contained in papers for lambda calculus' turing completeness.