Tag Info

Computability and Recursion, by Soare. http://www.people.cs.uchicago.edu/~soare/History/compute.pdf This paper is the first of the history of computation papers available here: http://www.people.cs.uchicago.edu/~soare/History/

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

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

Is memory usage for a tail call not constant and can you get a memory overflow? The stack usage for tail-recursive functions is bounded by a constant (i.e., is $O(1)$). However, you may still need to manipulate the stack at each recursive call in order to ensure that arguments are where the procedure expects them to be. Here's an example of such a ...

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

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

For linear recurrences, you may find interesting this recent work: Adrian Nistor, Wei-Ngan Chin, Tiow-Seng Tan, and Nicolae Tapus. 2009. Optimizing the parallel computation of linear recurrences using compact matrix representations. J. Parallel Distrib. Comput. 69, 4 (April 2009), 373-381. DOI=10.1016/j.jpdc.2009.01.004 ...

What Sam said. Also, it's really well under a page. If you're familiar with evaluation contexts, you can specify the call-by-value lambda calculus like this: Terms $$M ::= x \mid (M \, M) \mid (\lambda x . M)$$ Values $$V = (\lambda x . M)$$ Evaluation contexts $$E ::= [\:] \mid ([\:] M) | (V [\:])$$ The (only) reduction rule: $$E[((\lambda x . M) ...

I do not think that the part of Wikipedia you quoted is talking about space complexity. It simply states that unlike non-tail calls, tail calls do not have to store the return addresses in the stack. However, it is not correct to state that tail calls do not touch the stack at all, because you still have to clean up local variables allocated on the stack ...

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