在R中的尾递归
我似乎误解了尾递归; 根据这个stackoverflow问题R不支持尾递归。 但是，让我们考虑以下函数来计算第n个斐波纳契数：
迭代版本：
Fibo <- function(n){
a <- 0
b <- 1
for (i in 1:n){
temp <- b
b <- a
a <- a + temp
}
return(a)
}
“天真”递归版本：
FiboRecur <- function(n){
if (n == 0 || n == 1){
return(n)
} else {
return(FiboRecur(n-1) + FiboRecur(n-2))
}
}
最后我发现一个例子应该是tail call递归：
FiboRecurTail <- function(n){
fib_help <- function(a, b, n){
if(n > 0){
return(fib_help(b, a+b, n-1))
} else {
return(a)
}
}
return(fib_help(0, 1, n))
}
现在，如果我们在调用这些函数时看一下这些轨迹，下面是我们得到的结果：
Fibo(25)
trace: Fibo(25)
[1] 75025
trace(FiboRecur)
FiboRecur(25)
Thousands of calls to FiboRecur and takes a lot of time to run
FiboRecurTail(25)
trace: FiboRecurTail(25)
[1] 75025
在FiboRecurTail(25) Fibo(25)和FiboRecurTail(25) ，答案会立即显示，只有一个呼叫。 对于FiboRecur(25) ，成千上万的电话会在显示结果之前运行几秒钟。
我们还可以使用rbenchmark软件包中的benchmark函数来查看运行时间：
benchmark(Fibo(30), FiboRecur(30), FiboRecurTail(30), replications = 5)
test replications elapsed relative user.self sys.self user.child sys.child
1 Fibo(30) 5 0.00 NA 0.000 0 0 0
2 FiboRecur(30) 5 13.79 NA 13.792 0 0 0
3 FiboRecurTail(30) 5 0.00 NA 0.000 0 0 0
因此，如果R不支持尾递归，那么FiboRecurTail(25)中发生了什么，使其运行速度与迭代版本一样快，而“天真”递归函数像糖蜜一样运行？ 相反，R支持尾递归，但没有像其他编程语言（例如Haskell）那样优化一个函数的“天真”递归版本作为尾调用递归呢？ 这是我从R邮件列表的这篇文章中了解到的。
如果有人会对此有所了解，我将不胜感激。 谢谢！
区别在于，对于每次递归， FiboRecur调用两次。 在FiboRecurTail ， fib_help只调用一次。
因此，与前者有更多的函数调用。 在FiboRecurTail(25)的情况下，您的递归深度为FiboRecurTail(25)个调用。 FiboRecur(25)产生242,785次函数调用（包括第一次）。
我没有计算任何例程，但请注意，对于这两个更快的例程，您都显示为0.00 。 您应该看到更高的输入值差一些，但要注意Fibo迭代正是不亚于FiboRecurTail递归。
在naive递归方法中，您重复计算了很多值。 例如，当您计算FiboRecur(30)您将计算FiboRecur(29)和FiboRecur(28) ，并且这两个调用中的每一个都是独立的。 而在FiboRecur(29) ，即使FiboRecur(28)已经在上述其他地方计算FiboRecur(28)您FiboRecur(28)再次计算FiboRecur(28)和FiboRecur(27) 。 这发生在递归的每个阶段。 或者简单地说，对于n的每增加，计算工作几乎翻倍，但显然，实际上它应该像将最后两个计算的数字加在一起一样简单。
FiboRecur(4)一个小结： FiboRecur(0)计算两次， FiboRecur(1)计算三次， FiboRecur(2)计算两次， FiboRecur(3)计算一次。 前三者应该真正计算一次并存储在某个地方，以便您可以在需要时提取这些值。 这就是为什么你看到这么多的函数调用，即使它不是一个大数字。
然而，在尾递归版本中，每个先前计算的值都通过a + b参数传递到下一个阶段，这样可以避免无数次重复计算，因为它在天真的递归版本中更为高效。
上一篇: Tail recursion in R