R编程: Level of allowed recursion depth differs when calling a local helper function

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() - 它不仅仅是作为一个方便的函数提供的，还因为它的实现并不简单带有 float 的 sum() 的数字正确版本。

在您的原始实现中，对 fun() 的调用在递归调用之前返回——这意味着每次递归调用都会将调用堆栈的深度恰好增加 1。在另一种情况下，您有一个额外的函数调用正在等待评估。有关更多详细信息，您应该查看 R 如何处理闭包以及 R 中的惰性/急切评估是如何处理的。如果我没记错的话，R 使用环境(大致上，R 的范围概念，并且与闭包密切相关)在某些情况下包装参数并延迟它们的评估，从而有效地使用惰性评估。网上有很多关于 R 内部结构的信息，请参阅此处以快速了解 argument evaluation .我不确定我在细节上有多准确，但似乎尾调用的参数本身被放置在调用堆栈中，从而将调用堆栈的深度增加了 1 以上。

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

函数traceback()和 trace()如果您对更多细节感到好奇，可能有助于探索调用行为。