r - R中的尾递归

Question

我似乎误解了尾递归；根据 to this stackoverflow question 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))
        }
}

最后是我发现应该是尾调用递归的示例:

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 中了解到的.

如果有人能对此有所了解，我将不胜感激。谢谢!

Answer 1

不同之处在于，对于每个递归，FiboRecur两次调用自己。在 FiboRecurTail 内, fib_help只调用自己一次。

因此，您可以使用前者进行更多的函数调用。在 FiboRecurTail(25) 的情况下您的递归深度约为 25 次调用。 FiboRecur(25)导致 242,785 个函数调用(包括第一个)。

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