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

<p>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 <em>inline</em> all those calls into the definition of $F$ which thusly becomes a directly recursive function we can already deal with.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Mutual_recursion" rel="nofollow">mutual recursion</a> which requires another trick to get rid off. The idea is to compute both functions simultaneously. For example, in the trivial case:</p>

<pre><code>f(0) = a
f(n) = f'(g(n-1))

g(0) = b
g(n) = g'(f(n-1))
</code></pre>

<p>with <code>f'</code> and <code>g'</code> non-recursive functions (or at least independent of <code>f</code> and <code>g</code>) becomes</p>

<pre><code>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
</code></pre>

<p>This naturally extends to more functions involved and more complicated functions.</p>

CC BY-SA 3.0
2012-02-16T19:44:15.820Z
Glad I could help. Please remember to accept your favorite answer by clicking on the checkmark next to it.
Raphael
CC BY-SA 3.0
2012-02-16T21:46:58.360Z
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.
Andrej Bauer
CC BY-SA 3.0
2012-02-16T23:09:06.513Z
@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?
Itachi Uchiha
CC BY-SA 3.0
2012-02-17T14:07:13.033Z
@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$).
Raphael
CC BY-SA 3.0
2012-02-17T22:08:58.603Z
Well, see my answer on how to do it.
Andrej Bauer
CC BY-SA 3.0
2012-02-16T14:08:52.750Z
2012-02-16T19:43:37.460Z
2012-02-16T19:43:37.460Z
Raphael
<p>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 <code>machine.ml</code> in the MiniML language in my <a href="http://andrej.com/plzoo/">PL Zoo</a> (notice that the <code>loop</code> function at the bottom, which actually runs code, is tail recursive and so it can be trivially converted to an actual loop).</p>

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

<p>$$f_1 : A_1 \to B_1$$
$$f_2 : A_2 \to B_2$$
$$\vdots$$
$$f_n : A_n \to B_n$$</p>

<p>the recursion can be expressed in terms of a single recursive map</p>

<p>$$f : A_1 + \cdots + A_n \to B_1 + \cdots + B_n,$$</p>

CC BY-SA 3.0
2012-02-16T14:25:16.470Z
2012-02-16T14:25:16.470Z
Andrej Bauer
<p>You might want to look at the <a href="http://www.brics.dk/RS/03/33/BRICS-RS-03-33.pdf" rel="nofollow">SECD machine</a>. 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.<br>
Recursive calls are never actually invoked. Instead, the instructions of the body of the function being called is placed on the stack to run.</p>

<p>A related approach is the <a href="http://matt.might.net/articles/cek-machines/" rel="nofollow">CEK machine</a>.</p>

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

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

CC BY-SA 3.0
2012-02-16T23:13:15.073Z
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
Itachi Uchiha
CC BY-SA 3.0
2012-02-16T23:17:19.373Z
[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?
Itachi Uchiha
CC BY-SA 3.0
2012-02-17T05:03:14.260Z
@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
Akash Kumar
CC BY-SA 3.0
2012-02-17T15:32:15.170Z
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.
Dave Clarke
CC BY-SA 3.0
2012-02-16T07:49:40.067Z
2012-02-18T16:14:48.730Z
2012-02-18T16:14:48.730Z
Dave Clarke
<p><strong>Q</strong>: <em>"Is there really a more formal (convincing?) proof that recursion can be converted to iteration?"</em></p>

<p><strong>A</strong>: The Turing completeness of a Turing Machine :-)</p>

<p>Jokes apart, the Turing equivalent <a href="http://en.wikipedia.org/wiki/Random_access_machine">Random Access stored program (RASP) machine model</a> 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 <em>implementing</em> subroutines and recursive calls easier.</p>

<p>I think that you can find many papers/articles on the "<em>recursive to iterative conversion</em>" (see Dave's answer or just Google the keywords), but perhaps a <em>less known</em> (and <em>practical</em>) approach is the latest research on <em>hardware implementation of recursive algorithms</em> (using the <a href="http://en.wikipedia.org/wiki/VHDL">VHDL language</a> that is "compiled" directly into a piece of hardware). For example see  V.Sklyarov's paper "<a href="http://www.ieeta.pt/~skl/research/Papers/Recursive2004.pdf">FPGA-based implementation of recursive algorithms</a>"  (<em>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....</em>). Worth a look.</p>

CC BY-SA 3.0
2012-02-16T10:55:13.917Z
2012-02-16T10:55:13.917Z
Marzio De Biasi
<p>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).</p>

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

CC BY-SA 3.0
2012-02-18T17:56:03.717Z
2012-02-18T17:56:03.717Z
Jules
<p>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 <a href="http://en.wikipedia.org/wiki/Lambda_calculus" rel="nofollow">lambda calculus</a> (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</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>much of the bkd on this is in this wikipedia page <a href="http://en.wikipedia.org/wiki/Church-Turing_Thesis" rel="nofollow">church-turing thesis</a>. 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?</p>

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

<p>note of course for anyone interested in the principles the modern <a href="http://en.wikipedia.org/wiki/Lisp" rel="nofollow">Lisp language</a> and the variant <a href="http://en.wikipedia.org/wiki/Scheme_language" rel="nofollow">Scheme</a> 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.</p>

CC BY-SA 3.0
2012-02-20T18:55:57.150Z
The Turing/lambda equivalence proof is in the appendix of this paper: www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Radu GRIGore
CC BY-SA 3.0
2012-02-16T16:25:34.680Z
2012-02-16T16:32:40.067Z
2012-02-16T16:32:40.067Z
vzn
<p>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.</p>

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

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

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

<p>What I am really asking is $2$ questions</p>

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

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

CC BY-SA 3.0
2012-02-16T06:39:51.713Z
like the word iteratizing :)
Akash Kumar
CC BY-SA 3.0
2012-02-16T06:57:19.283Z
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.
singhsumit
CC BY-SA 3.0
2012-02-16T14:11:14.447Z
I think this question would have been best suited for the [Computer Science](http://area51.stackexchange.com/proposals/35636/computer-science?referrer=pdx8p7tVWqozXN85c5ibxQ2) 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.
Raphael
CC BY-SA 3.0
2012-02-16T18:00:29.497Z
thanks everyone for your comments - guess i have got quite some reading to do.
Itachi Uchiha
CC BY-SA 3.0
2012-02-16T18:13:29.637Z
@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?
Itachi Uchiha
CC BY-SA 3.0
2012-02-16T19:42:01.143Z
Tail recursion is easy to "iteratize" because it is trivial; you can throw away your stack frame before the recursive call because you *know* you won't need it afterwards. As for post-/preorder; I get it now. You will have to touch each inner node twice; once to out its children on the stack and once, later, to print it. While natural using recursion, it is a bit messier using iteration, true. The details of this would be best suited to Stackoverflow, I guess (as cs.SE is not there yet). If you are in no hurry, please consider holding your question until cs.SE is live. We will need questions!
Raphael
<pl.programming-languages><recursion><recursive>
Removing recursion - a look into theory behind the scenes
Itachi Uchiha
# Removing recursion - a look into theory behind the scenes

(Asked by: username_0 on 2012-02-16)

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)

**Tags:** pl.programming-languages, recursion, recursive

> **Comments:**
> **username_1**: like the word iteratizing :)  
> **username_2**: 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.  
> **username_3**: I think this question would have been best suited for the [Computer Science](http://area51.stackexchange.com/proposals/35636/computer-science?referrer=pdx8p7tVWqozXN85c5ibxQ2) 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.  
> **username_0**: thanks everyone for your comments - guess i have got quite some reading to do.  
> **username_0**: @username_3 - 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?  
> **username_3**: Tail recursion is easy to "iteratize" because it is trivial; you can throw away your stack frame before the recursive call because you *know* you won't need it afterwards. As for post-/preorder; I get it now. You will have to touch each inner node twice; once to out its children on the stack and once, later, to print it. While natural using recursion, it is a bit messier using iteration, true. The details of this would be best suited to Stackoverflow, I guess (as cs.SE is not there yet). If you are in no hurry, please consider holding your question until cs.SE is live. We will need questions!  

---

## 6 answers

### Answer by username_3 on 2012-02-16. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_3**: Glad I could help. Please remember to accept your favorite answer by clicking on the checkmark next to it.  
> **username_4**: 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.  
> **username_0**: @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?  
> **username_3**: @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$).  
> **username_4**: Well, see my answer on how to do it.  

---

### Answer by username_4 on 2012-02-16. Score: 8

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 username_5'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](http://andrej.com/plzoo/) (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 by username_5 on 2012-02-16. Score: 8

You might want to look at the [SECD machine](http://www.brics.dk/RS/03/33/BRICS-RS-03-33.pdf). 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](http://matt.might.net/articles/cek-machines/).

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.

> **Comments:**
> **username_0**: 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  
> **username_0**: [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?  
> **username_1**: @ItachiUchiha - I do not think that your problem is undecidable. Look at the answer by username_4. 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  
> **username_5**: 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 by username_6 on 2012-02-16. Score: 6

**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](http://en.wikipedia.org/wiki/Random_access_machine) 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](http://en.wikipedia.org/wiki/VHDL) that is "compiled" directly into a piece of hardware). For example see V.Sklyarov's paper "[FPGA-based implementation of recursive algorithms](http://www.ieeta.pt/~skl/research/Papers/Recursive2004.pdf)" (*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 by username_7 on 2012-02-18. Score: 1

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 by username_8 on 2012-02-16. Score: 0

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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Lisp) and the variant [Scheme](http://en.wikipedia.org/wiki/Scheme_language) 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.

> **Comments:**
> **username_9**: The Turing/lambda equivalence proof is in the appendix of this paper: www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf  

---

