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

回答

相關問題