10
$\begingroup$

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)

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ like the word iteratizing :) $\endgroup$ – Akash Kumar Feb 16 '12 at 6:39
  • $\begingroup$ i am not sure if i fully understand, but if the recursion does end somewhere then you can actually simulate a system stack using your own stack. For part (2), the problems are not different in terms of computational complexity. $\endgroup$ – singhsumit Feb 16 '12 at 6:57
  • $\begingroup$ I think this question would have been best suited for the Computer Science site which is not yet live. As for your second question, can you elaborate why you think it is harder? The process should be almost identical. $\endgroup$ – Raphael Feb 16 '12 at 14:11
  • $\begingroup$ thanks everyone for your comments - guess i have got quite some reading to do. $\endgroup$ – Itachi Uchiha Feb 16 '12 at 18:00
  • $\begingroup$ @Raphael - One comment about why i think iteratizing postorder is hard (besides me not being able to do it). I was reading up a few articles on removing recursion and ran into something called tail recursive functions. Turns out they are easier to iteratize. I still do not formally understand why is this true; but there is another thing i should add. I have heard that iteratizing postorder requires two stacks and not one but do not know the details. And now I am lost - why this difference between these two traversal modes? And why is tail recursion easy to handle? $\endgroup$ – Itachi Uchiha Feb 16 '12 at 18:13
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Glad I could help. Please remember to accept your favorite answer by clicking on the checkmark next to it. $\endgroup$ – Raphael Feb 16 '12 at 19:44
  • 1
    $\begingroup$ Raphel, your trick works only when both recursive function accept arguments of the same type. If f and g accept different kinds of types, a more general trick is needed. $\endgroup$ – Andrej Bauer Feb 16 '12 at 21:46
  • $\begingroup$ @AndrejBauer good observation, i totally missed that. i really liked raphael's approach, but like you observed in general cases, we probably need some different idea. Can you make any other suggestions? $\endgroup$ – Itachi Uchiha Feb 16 '12 at 23:09
  • $\begingroup$ @AndrejBauer True. I was thinking from a recursion theoretic viewpoint; here we only have natural numbers. This is sufficient because we can encode everything in a suitable way. But your point is very valid for practice. I guess we would have to rewrite f and g until they share a common input encoding and recursion scheme (we can't have one using the $n-1$ and the other $n-2$). $\endgroup$ – Raphael Feb 17 '12 at 14:07
  • $\begingroup$ Well, see my answer on how to do it. $\endgroup$ – Andrej Bauer Feb 17 '12 at 22:08
8
$\begingroup$

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,$$

Improve this answer
$\endgroup$
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ i will be honest here. I really want to understand why (and how) can you iteratize every recursive program. But i find it tough to read through a paper - they are usually not accessible to me. i mean i want a deeper reason than the "handwavy" description i talked about in the question. but i am also happy with something which gives me some new insight - it does not have to be the whole proof in its nitty gritty details $\endgroup$ – Itachi Uchiha Feb 16 '12 at 23:13
  • $\begingroup$ [cntd] I mean i will like the proof, if there is one, to tell me why is iteratizing one program easier than the other. But in some sense, the recursive to iterative converter should work no matter what recursive program it takes as input. Nt sure, but i guess making such a converter might be sth as tough as the halting problem? I am just guessing here - but i would love a recursive to iterative converter to exist and if it does i would like it to explain the inherent complexity of iteratizing different recursive programs. am not sure, but should i edit the question? Is my question clear? $\endgroup$ – Itachi Uchiha Feb 16 '12 at 23:17
  • $\begingroup$ @ItachiUchiha - I do not think that your problem is undecidable. Look at the answer by Andrej Bauer. He notes that every compiler does it when it translates source code to machine language. Also he adds you can see the actual code that converts recursive to non-recursive in the MiniM(a)l language. This clearly indicates that there is a decision procedure to "iteratize" recursion. I am not sure about inherent (conceptual) difficulty/complexity of removing recursion. I do not understand this question very clearly but it looks interesting. Maybe you can edit your question to get better reply $\endgroup$ – Akash Kumar Feb 17 '12 at 5:03
  • $\begingroup$ 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. $\endgroup$ – Dave Clarke Feb 17 '12 at 15:32
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The Turing/lambda equivalence proof is in the appendix of this paper: www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf $\endgroup$ – Radu GRIGore Feb 20 '12 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.