R 统计环境上的尾递归

Question

R 是否支持正确的尾递归？在哪里可以找到相关文档？

Answer 1

很容易发现R不支持尾递归优化：

f <- function(n) {
if (n != 0) f(n-1)
}
f(100000)
# Error: evaluation nested too deeply: infinite recursion / options(expressions=)?

如果尾部调用被优化为跳转，那么这个函数将毫无问题地终止。

Answer 2

不，R 不支持尾递归。

Answer 3

这个参考资料，很容易通过 Google 找到，表明 R 不支持尾递归。 Luke Tierney（R 核心成员和 R 内部专家）解释了原因：

尾部调用优化不能应用在 R 中，在 至少不是以简单的方式，因为 R 的语义提供了访问 通过sys.xyz函数和parent.frame等调用堆栈。 可能可以进行一些语义更改，例如仅 保证对直接调用者的访问，但没有太多 点除非/直到函数调用机制的性能是 改善了。

Answer 4

R 的开发版本（截至 2023 年 10 月）有新功能，允许 R 使用

Tailcall()

帮助器支持尾递归中的调用消除：

来自帮助页面：

使用

Tailcall

可以定义不增加计算堆栈的尾递归函数...这种尾调用优化的优点是不增加调用堆栈并允许任意深度的尾递归。

帮助页面中的示例，计算 log(10)-阶乘：

lfact <- function(n) {
    lfact_iter <- function(val, n) {
        if (n <= 0)
            val
        else {
            val <- val + log10(n) # forces val
            Tailcall(lfact_iter, val, n - 1)
        }
    }
    lfact_iter(0, n)
}
suppressWarnings(10 ^ lfact(3)) # first Tailcall in a session warns
lfact(100000)