爲什麼OCaml中的遞歸比C++或Java更高效？

在caml.inria.fr網站說，這篇文章A C++/Java programmer's introduction to Objective Caml ...爲什麼OCaml中的遞歸比C++或Java更高效？

由於相對於C++和Java，遞歸在O'Caml [原文]只是儘可能高效的迭代

對於類似於factorial的東西，似乎具有可變變量的循環比遞歸調用涉及的棧操作更有效。

OCaml確實有一種機制使遞歸比C++和Java更高效嗎？

2014-03-03 Jim Fred

一些「良好」的遞歸調用被編譯成OCaml和其他函數式語言中的單純跳轉，因此它與循環等效。技術上更「好」的意思是在尾部位置，但在我看來，該文件故意跳過這一點，因爲它只是介紹性的目的。 – camlspotter

適當使用「[sic]」，但「OCaml」不是按照你寫的方式寫的。 http://yquem.inria.fr/pipermail/caml-announce/2012-July/000000.html（「OCaml」已經是它應該在2001年左右編寫博士的時候編寫的方式，但它那時不是官方的）。 –

是的，在某些情況下。這叫做尾部呼叫優化。舉個例子來說，下面的C-ISH階乘函數：

int factorial(int n) 
{ 
     if (n < = 1) 
       return 1; 
     else 
       return n * factorial(n – 1); 
}

此功能去n級深入到調用堆棧「展開」備份到取得結果之前。下面是OCaml的等價：

let factorial n = if n <= 1 then 1 else n * factorial (n - 1)

現在實際上，上面的代碼也將走N個級別深入到調用堆棧，就像上面的C-ISH代碼。下面是完成相同的，但有一個循環的C-ISH功能：

int factorial(int n) 
{ 
     int ret = 1; 
     for (; n > 1; n--) 
       ret *= n; 
     return ret; 
}

這個功能，當然，可以調用次數任何量也不會溢出堆棧（即使你很快就會溢出32-位int）。實際上可以在OCaml中編寫同義函數。現在，OCaml的版本將再次使用遞歸。但是，如果我們添加一個「蓄電池」的說法在第一個功能，它可以重新寫爲：

let factorial acc n = if n <= 1 then acc else factorial (acc * n) (n – 1)

的ACC參數可以被認爲是「累計」以前所有的遞歸調用的結果階乘。關鍵效果是，上面的表達式「n * factorial（n-1）」變成下面的表達式「factorial（acc * n）（n-1）」。在第二個表達式中，對factorial的遞歸調用是表達式的頂層，這意味着不需要執行額外的操作來獲取函數的返回值。第一個表達式不適用，其中頂層操作是n - 1階乘結果與n的乘積。當遞歸函數調用是頂級表達式時，它被認爲是「尾調用」，並且編譯器可以並且將它優化成實際上是循環的內容。在第一個函數上調用「factorial 2000000」將（可能）導致堆棧溢出，但在第二個函數上調用「factorial 1 2000000」不會。此外，您可能會發現第二個OCaml函數在性能上與C等價物相當（可能稍微慢一點，但不是數量級或其他）。順便說一句，你可能會問自己，「但是當tail-recursive函數有一個不必要的額外的'acc'參數，當用戶初始調用時應該始終爲1是不是很難處理？」是的，是的它是。這個問題很容易通過嵌套尾遞歸函數成「包裝」功能，以正確的初始累積值的話來說，像這樣的工作周圍：

let factorial n = 
    let loop acc n' = if n' <= 1 then acc else loop (acc * n') (n' – 1) in 
    loop 1 n

在這裏，我已經改名爲尾遞歸階乘函數將其嵌入到函數中，然後用正確的初始累加器1調用它。

通常情況下，這些尾遞歸模式可以使用高階函數在標準庫中，例如List.fold，但並非總是如此。

來源

2014-03-03 05:39:17 bam365

該語言的函數式編程結構可能使編譯器更容易識別和優化遞歸。

參見：http://ocaml.org/learn/tutorials/if_statements_loops_and_recursion.html

If you write your code recursively instead of iteratively then you necessarily run out of stack space on large inputs, right?

In fact, wrong. Compilers can perform a simple optimisation on certain types of recursive functions to turn them into while loops

我建議：

OCaml中的編譯器優化尾遞歸成迭代結構;並可能
所有其他遞歸類型優化迭代和堆棧對象來模擬遞歸調用（我沒有找到任何文檔來支持這一點）。

我知道至少.Net/C＃不可能跨越功能邊界進行優化。例如，必須使用屬性明確請求函數的內聯，甚至可能不會。 JIT可能內聯，並可能潛在地優化遞歸，但似乎沒有。這可能適用於Java。

我不確定C++，並取決於您使用的編譯器。

來源

2014-03-03 05:17:41 Todd

爲什麼OCaml中的遞歸比C++或Java更高效？

回答

相關問題