r - 防止递归 R 函数中的无限递归/堆栈溢出错误

Question

创建一个简单的递归函数，如下所示。

power <- function(x, n) {
  if(n >= 1) x * power(x, n-1)
  else 1
}

当n设置为1e4时，显示 infinite recursion的错误.正如错误消息所暗示的那样，我更新了选项参数，在本例中为 stack overflow遇到错误。

## error to run power 10000 times with defalult option
options()$expressions
#[1] 5000

power(2, 1e3)
#[1] 1.071509e+301

power(2, 1e4)
#Error: evaluation nested too deeply: infinite recursion / options(expressions=)?
#Error during wrapup: evaluation nested too deeply: infinite recursion / options(expressions=)?

## expressions parameter updated and results in stack overflow
options(expressions = 100000)
power(2, 1e4)
#Error: protect(): protection stack overflow

Scala 支持尾递归，因此 stack overflow可以处理错误，我对功能进行了如下更改。

## tail recursion supported in Scala
power.rec <- function(x, n, t = 1) {
  if(n < 1) t
  else power.rec(x, n-1, x*t)
}

然而，随着更新的函数抛出 infinite recursion，情况似乎变得更糟。当 n 设置为 1e3 时出错。这在选项参数增加但 stack overflow 时处理。当 n 变为 1e4 时遇到错误。

# turn to default and even worse
options(expressions = 5000)
power.rec(2, 1e3)
#Error: evaluation nested too deeply: infinite recursion / options(expressions=)?
#Error during wrapup: evaluation nested too deeply: infinite recursion / options(expressions=)?

# works in updated parameter
options(expressions = 100000)
power.rec(2, 1e3)
#[1] 1.071509e+301

# stack overflow error again
power.rec(2, 1e4)
#Error: protect(): protection stack overflow

现在我的问题是

怎么可能在没有错误的情况下运行这种功能？

提前致谢。

Answer 1

R 中未实现尾调用优化，因为 R 提供对完整调用堆栈的访问。来自 Luke Tierney :

As to the question: tail call optimization cannot be applied in R, at least not in a simple way, because the semantics of R provide access to the call stack via the sys.xyz functions and parent.frame and such. It might be possible to make some semantic changes, such as only guaranteeing access to the immediate caller, but there isn't much point unless/until the performance of the function calling mechanism is improved.

评论有点旧(2011)，我希望 compiler包将解决这种类型的事情，但我无法让它工作。所以你需要将你的函数变成一个循环:

power.rec2 <- function(x, n, t = 1) {
  while(n > 0) {
    t <- x * t
    n <- n - 1
  }
  t
}
identical(power.rec(2, 10), power.rec2(2, 10))
# [1] TRUE
identical(power.rec(2, 1e2), power.rec2(2, 1e2))
# [1] TRUE
power.rec2(2, 1e3)
# [1] 1.071509e+301
power.rec2(2, 1e6)
# [1] Inf

请注意，尾递归优化正是这样做的:将递归转换为循环。不幸的是，您只能手动执行此操作。