R编程:在调用本地助手函数时，允许递归深度的级别不同

Question

这纯粹是一个学术问题：

最近我一直在使用使用尾递归优化的语言。在实践中，我在R中编写了两种和函数的递归实现，其中一种是尾递归。我很快意识到在R中没有尾部递归优化，我可以接受这一点。但是，在使用本地助手函数进行尾递归时，我也注意到了允许深度的不同级别。

以下是代码：

## Recursive
sum <- function (i, end, fun){
  if (i>=end) 0
  else fun(i) + sum(i+1, end, fun)
}


## Tail recursive

sum_tail <- function (i, end, fun){
  sum_helper<- function(i, acc){
    if (i>=end) acc
    else sum_helper(i+1, acc+fun(i))
  }

  sum_helper(i, 0)
}




## Simple example

harmonic <- function(k){
  return(1/(k))
}


print(sum(1, 1200, harmonic)) # <- This works fine, but is close to the limit
# print(sum_tail(1, 1200, harmonic)) <- This will crash
print(sum_tail(1, 996, harmonic)) # <- This is the deepest allowed

我很感兴趣。有人能解释一下这种行为吗?或者向文档指出如何计算允许的递归深度？

Answer 1

我不确定R的调用堆栈的内部实现，但是很明显，从这里开始，堆栈深度是最大的。(许多语言有这样的原因，主要是与内存和检测无限递归有关。)您可以使用options()来设置它，默认设置似乎取决于平台--在我的机器上，我可以毫不费力地完成print(sum_tail(1, 996, harmonic))。

侧边栏:你真的不应该命名你天真的实现sum()，因为你最终会隐藏一个内置的东西。我知道你只是在玩递归，但是你也应该避免使用你自己的sum()实现--它不仅仅是一个方便的函数，还因为用浮点实现一个数字正确的sum()版本是非常重要的。

在您的简单实现中，对fun()的调用在递归调用之前返回--这意味着每个递归调用都会使调用堆栈的深度增加1。在另一种情况下，您有一个等待评估的额外函数调用。有关更多细节，您应该了解R是如何处理闭包的，以及如何处理R中的懒惰/急切的计算。如果我没记错的话，R使用环境(大致上是R的范围概念，并且与闭包有很深的关联)在某些情况下包装参数并延迟它们的计算，从而有效地使用延迟计算。网上有很多关于R内部设备的信息，请参阅这里对论证评价的快速概述。我不知道我在细节上有多准确，但似乎尾部调用的参数本身正在被放置在调用堆栈上，从而使调用堆栈的深度增加了1以上。

第二个侧边栏:我不太记得R是如何实现这一功能的，我知道在主体中放置助手函数是常见的做法，但是在递归调用中放置助手函数定义可能会导致每个递归调用重新定义助手函数。这可以以各种方式与处理环境和闭包的方式进行交互，但我不确定。

如果您对更多的细节感兴趣，traceback()和trace()函数在探索调用行为方面可能很有用。