I'm rather confused by the recursion theory.

From the link, the recursion theory was formed by Dedekind, Gödel and some other famous mathematicians. There are the following types of recursion. But where is tail recursion? can this concept parallel to these concepts? what else concept goes parallel to tail recursion?

 1.1 The Initial Functions
 1.2 Iteration
 1.3 Primitive recursion
 1.4 Primitive recursion with parameters
 1.5 Course-of-value recursion
 1.6 Double recursion
 1.7 Minimization (least search)
  • 6
    $\begingroup$ Recursion theory is not about recursion. $\endgroup$ – Yuval Filmus Jun 22 '16 at 6:40
  • 3
    $\begingroup$ While recursion theory started its life as studying computability, very quickly it started studying problems which aren't computable. Tail recursion is a concept from function programming languages, and considers implementation of recursion of stack-based machines. The two belong to different areas. $\endgroup$ – Yuval Filmus Jun 22 '16 at 6:47
  • 2
    $\begingroup$ Recursion theory studies classes of mathematical functions (maps from numbers to numbers, such as $f(x)=x^2)$) and has no particular connection to the recursion techniques in programming, such as tail recursion. $\endgroup$ – David Richerby Jun 22 '16 at 7:28
  • 3
    $\begingroup$ I'm voting to close this question as off-topic because its premise is a misunderstanding. $\endgroup$ – David Richerby Jun 22 '16 at 7:28
  • 1
    $\begingroup$ @DavidRicherby I think resolving the misunderstanding would make fine answers. $\endgroup$ – Raphael Jun 22 '16 at 8:11

We need to distinguish two things:

  • Tail-calls are calls to functions that are made in tail position. Tail-recursion is a recursive tail-call.
  • Tail-call optimization is the process by which tail-calls are turned into loops or GOTOs in compilers.

The second, as others have stated, is an implementation detail that falls in the theory of compilers, and isn't really recursion theory.

However, it is absolutely possible to study tail calls in the context of computability. In particular, there is something called Continuation Passing Style.

There exist CPS-transformations which can turn any lambda-function into one in continuation passing style. So the set of languages computed using only tail-calls is equivalent to the set of recursively-enumerable languages.

CPS has many applications in the theory of programming languages, and the concept of tail recursion is useful for more than just the tail-call optimization.

  • $\begingroup$ "So the set of languages computed using only tail-calls is equivalent to the set of recursively-enumerable languages." -- isn't that a direct consequence resp. the equivalent of the fact that we need only one while loop resp. one $\mu$-operator? $\endgroup$ – Raphael Jun 22 '16 at 8:13
  • $\begingroup$ @Raphael It follows from that, combined with a proof that all primitive-recursive functions can be written in tail-form. But not every primitive-recursive program uses only tail calls. I don't know if such a proof exists, since you'd need to pass functions as arguments, and interpreting those might require you to go beyond primitive recursion. Presumably there is no self-interpreter for primitive recursion. $\endgroup$ – jmite Jun 22 '16 at 8:19
  • $\begingroup$ 1) I was thinking of unbounded $\mu$; I don't recall if a similar theorem holds for primititive recursion at all. 2) I thought replacing while-loops with recursion would naturally lead to tail-recursion. I did not think it through completely, though. $\endgroup$ – Raphael Jun 22 '16 at 12:34

Tail recursion is a specific implementation detail. Mathematical functions are not algorithmic implementations, so the concept does not make sense.

To be precise, tail recursion is a specific optimization in which the epilogue of the caller and the prologue of the callee are ignored, by virtue of a direct transfer of execution. This is possible because the two deal with the management of the internal state of the function, and in a recursive call the caller and callee are the same function so their state will be similar. If the final state of the caller and the initial state of the callee can be linked by a relatively simple transform, such a direct transfer of execution may be more efficient than a regular function call. This is of course dependent on the execution architecture, but it is a common occurrence.


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.