有没有使用尾recursion不能写的问题？

尾recursion是function语言中一个重要的性能优化策略，因为它允许recursion调用消耗常量栈（而不是O（n））。

是否有任何问题不能用尾recursion的方式来编写，还是总是可以把一个简单recursion函数转换成尾recursion函数？

如果是这样的话，有一天function编译器和解释器可以足够聪明地自动执行转换？

是的，实际上你可以拿一些代码，把每个函数调用和每个返回转换成一个尾部调用。你最后的结果是所谓的延续传球风格，或者说CPS。

例如，这是一个包含两个recursion调用的函数：

(define (count-tree t) (if (pair? t) (+ (count-tree (car t)) (count-tree (cdr t))) 1))

如果你把这个函数转换成continuation-passing的风格，下面是它的样子：

 (define (count-tree-cps t ctn) (if (pair? t) (count-tree-cps (car t) (lambda (L) (count-tree-cps (cdr t) (lambda (R) (ctn (+ LR)))))) (ctn 1)))

额外的参数ctn是count-tree-cps tail-calls 而不是返回的过程 。（sdcvvc的回答说，你不能在O（1）空间里做所有事情，这是正确的;这里每个延续都是一个闭包，占用一些内存。）

我没有把电话转换成car或者cdr或者+进入cdr 。也可以这样做，但我认为那些叶子的调用实际上是内联的。

现在是有趣的部分。鸡计划实际上做这个转换所有代码编译。鸡编写的程序永远不会返回 。有一个经典的文章解释了为什么鸡计划这样做，1994年之前写的鸡实施： CONS不应该支持它的论点，第二部分：切尼在MTA

令人惊讶的是，继续传递风格在JavaScript中相当普遍。您可以使用它来执行长时间运行的计算，避免浏览器的“慢脚本”popup。 asynchronousAPI也很有吸引力。 jQuery.get （一个简单的XMLHttpRequest封装）显然是延续式的; 最后一个参数是一个函数。

观察到任何相互recursion函数的集合都可以变成尾recursion函数，这是真的，但没有用处。这个观察与上世纪60年代的老栗子相类似，控制stream构造可以被消除，因为每个程序都可以被编写成嵌套在内部的case语句的循环。

有用的知识是，许多不明显的尾recursion函数可以通过累加参数来转换为尾recursionforms。（这种转换的一个极端版本是对继续传递样式（CPS）的转换，但是大多数程序员发现CPS转换的输出难以阅读。）

下面是一个“recursion”函数的例子（实际上它只是迭代）而不是尾recursion：

 factorial n = if n == 0 then 1 else n * factorial (n-1)

在这种情况下，乘法发生在recursion调用之后。我们可以通过将产品放入累积参数来创build一个尾recursion的版本：

 factorial n = fn 1 where fn product = if n == 0 then product else f (n-1) (n * product)

内函数f是尾recursion的并且编译成紧密的循环。

我发现以下区别有用：

在迭代或recursion程序中，通过首先解决一个大小为n-1子问题，可以解决大小为n的问题。计算阶乘函数属于这个类别，它可以迭代地或recursion地完成。（这个想法概括，例如，斐波那契函数，你需要n-1和n-2来解决n 。
在recursion程序中，通过首先解决大小为n/2 两个子问题来解决大小为n的问题。或者更一般地说，通过首先解决大小为k的子问题和大小为nk的子问题（其中1 < k < n ，可以解决大小为n的问题。 Quicksort和mergesort是这类问题的两个例子，可以很容易地recursion编程，但是迭代编程或者仅使用尾recursion并不那么容易。（你基本上必须使用显式堆栈来模拟recursion。）
在dynamic规划中，通过首先解决所有大小为k 所有子问题，其中k<n ，解决了规模为n的问题。在伦敦地铁上find最短的路线是这类问题的一个例子。（伦敦地铁是一个多元连接图，你首先find最短path为1站，最短path为2站等等的所有点来解决问题）

只有第一种程序有一个简单的向尾recursionforms的转换。

任何recursionalgorithm都可以重写为迭代algorithm（可能需要一个栈或列表），迭代algorithm总是可以重写为尾recursionalgorithm，所以我认为任何recursion解决scheme都可以转换为尾recursion解决scheme。

（在评论中，Pascal Cuoq指出，任何algorithm都可以转换为延续传递风格。）

请注意，仅仅因为某些事情是尾recursion的，并不意味着它的内存使用是不变的。这只是意味着callback堆栈不会增长。

你不能在O（1）空间（空间等级定理）中做任何事情。如果你坚持使用尾recursion，那么你可以将调用栈作为参数之一存储。显然这不会改变任何东西; 在内部的某个地方，有一个调用堆栈，只是简单地使其可见。

如果是这样的话，有一天function编译器和解释器可以足够聪明地自动执行转换？

这种转换不会减less空间的复杂性。

正如帕斯卡·库克（Pascal Cuoq）评论的，另一种方法是使用CPS ; 所有的调用都是尾recursion的。

我不认为像tak这样的东西可以只使用tail调用来实现。（不允许延续）