R中的尾递归

我似乎误解了尾递归;根据to this stackoverflow question R不支持尾递归。然而，让我们来看看下面的函数来计算第n个斐波纳契数：R中的尾递归

迭代版本：

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)) 
     } 
}

最后一个例子，我发现，应该是尾调用递归：

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

在Fibo(25)和FiboRecurTail(25)的情况下，瞬间显示的答案，只有一个调用。对于FiboRecur(25)，进行了数千次呼叫，并在显示结果之前运行几秒钟。

我们也可以使用benchmark功能从包装rbenchmark看看运行时间：

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）那样优化一个函数的“天真”递归版本作为尾调用递归呢？这是我从这个post in R's mailing list了解到的。

我非常感谢，如果有人会对此有所了解。谢谢！

来源

2016-08-16 brodrigues

你说得对，我已经纠正了这一点。 – brodrigues

[R统计环境下的尾递归]可能的重复（http://stackoverflow.com/questions/13208963/tail-recursion-on-r-statistical-environment） –

区别在于，对于每次递归，FiboRecur自己调用两次。在FiboRecurTail之内，fib_help只调用一次。

因此，与前者有更多的函数调用。在FiboRecurTail(25)的情况下，您的递归深度为〜25个调用。 FiboRecur(25)导致242,785个函数调用（包括第一个）。

我没有计时的任何例程，但请注意，您显示两个较快的例程0.00。您应该看到一些输入值较高的差异，但请注意Fibo的迭代次数与FiboRecurTail递归的迭代次数完全相同。

来源

2016-08-16 16:12:48

只是好奇，是计数函数调用简单/优雅还是蛮力？ – r2evans

@ r2evans计算“FiboRecur”的调用次数很简单，但更容易在全局环境中复制其功能并增加变量。 –

这就是我以为...只是想知道是否有一个简单的方法与分析或类似的东西。谢谢！ – r2evans

在naive递归方法中，您重复计算了很多值。例如，当您计算FiboRecur(30)时，您将计算出FiboRecur(29)和FiboRecur(28)，并且这两个调用中的每一个都是独立的。并且在FiboRecur(29)中，即使FiboRecur(28)已经在上述其他地方计算过，您也将再次计算出FiboRecur(28)和FiboRecur(27)。这发生在递归的每个阶段。或者简单地说，对于n的每增加，计算工作几乎翻倍，但显然，实际上它应该像将最后两个计算的数字加在一起一样简单。

的FiboRecur(4)一个小总结：FiboRecur(0)计算两次，FiboRecur(1)计算三次，FiboRecur(2)被计算两次，FiboRecur(3)时计算一次。前三者应该真正计算一次并存储在某个地方，以便您可以在需要时提取这些值。这就是为什么你看到这么多的函数调用，即使它不是一个大数字。

但是，在尾递归版本中，每个先前计算的值都会通过a + b参数传递到下一个阶段，这样可以避免无数次重复计算，因此可以更加高效。

来源

2016-08-16 16:46:20 Psidom

R中的尾递归

回答

相关问题