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

Question

创建一个简单的递归函数,如下所示.

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

当n设置为1e4时,它显示错误infinite recursion.正如错误消息所示,我更新了option参数,在这种情况下,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提供对完整调用堆栈的访问.来自卢克蒂尔尼:

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

评论有些陈旧(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

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