尾遞歸與前向遞歸

Question

有人可以給我這兩種遞歸和示例（特別是在OCaml）之間的差異？

Answer 1

尾遞歸函數是一個函數，其中唯一的遞歸調用是函數中的最後一個。非尾遞歸函數是一種不是這種情況的函數。

向後遞歸是一個遞歸，其中在每次遞歸調用中參數的值小於上一步中的值。前向遞歸是遞歸，每一步都會遞增。

這些是兩個正交的概念，即前向遞歸可能是也可能不是尾遞歸，同樣適用於後向遞歸。

例如階乘函數通常這樣寫的命令式語言：

fac = 1 
for i from 1 to n: 
    fac := fac * i 

向後階乘計數的共同遞歸版本（即它與n-1自稱爲參數），如果你願意，但是直接翻譯上面的強制性解決方案，你會想出一個遞歸的版本。這將是這個樣子：

let fac n = 
    let rec loop i = 
    if i >= n 
    then i 
    else i * loop (i+1) 
    in 
    loop 1 

這是向前遞推，正如你可以看到它比落後的遞歸variant稍微繁瑣，因爲它需要輔助功能。現在這不是尾遞歸，因爲最後一次調用loop是乘法，而不是遞歸。因此，爲了使尾遞歸，你會做這樣的事情：

let fac n = 
    let rec loop acc i = 
    if i >= n 
    then acc 
    else loop (i*acc) (i+1) 
    in 
    loop 1 1 

現在，這既是前向遞歸和尾遞歸，因爲遞歸調用是）一個尾調用和b）調用自身具有更大的價值（i+1）。

Answer 2

這裏的一個尾遞歸階乘函數的一個例子：

let fac n = 
let rec f n a = 
    match n with 
    0 -> a 
    | _ -> f (n-1) (n*a) 
in 
f n 1 

這裏是它的非尾遞歸對應物：

let rec non_tail_fac n = 
match n with 
0 -> 1 
| _ -> (non_tail_fac n-1) * n 

尾部遞歸函數使用的儲液器，一個，以存儲前一次調用結果的值。這允許OCaml執行尾部呼叫優化，從而導致堆棧不會溢出。通常，尾遞歸函數將使用累加器值來允許尾部調用優化發生。

Answer 3

例如，遞歸函數build_word需要char list並將它們組合成一個字符串，即['f'; 'o'; 'o']到字符串"foo"。感應過程可以用這種方式顯示：

build_word ['f'; 'o'; 'o'] 
"f"^(build_word ['o'; 'o']) 
"f"^("o"^(build_word ['o']) // base case! return "o" and fold back 
"f"^("o"^("o")) 
"f"^("oo") 
"foo" 

這是一個正常的遞歸。請注意，每對括號代表一個新的堆棧幀或遞歸調用。這個問題的解決方案（即「f」，「fo」或「foo」）不能在遞歸結束之前（滿足基本情況）派生。只有這樣，最後一幀纔會在「彈出」之前將最後一個結果返回到前一個結果，反之亦然。

從理論上講，每次調用都會創建一個新的堆棧框架（或範圍，如果您願意的話）來保存碎片解決方案的「地點」以便返回並收集到開始處。這可能導致stackoverflow（這個鏈接是一個遞歸順便說一句）。

尾調用的版本將是這個樣子：

build_word ['f'; 'o'; 'o'] "" 
build_word ['o'; 'o'], "f" 
build_word ['o'] ("f"^"o") 
build_word [] ("f"^"o"^"o") 
"foo" 

這裏，累積的結果（通常存儲在被稱爲accumulator變量）正在向前傳遞。通過優化，尾部調用不需要創建新的堆棧幀，因爲它不必保留前一個。解決方案正在解決「前進」而不是「後退」。

下面是build_word功能有兩個版本：

非尾

let build_word chars = 
    match chars with 
    | [] -> None 
    | [c] -> Some Char.to_string c 
    | hd :: tl -> build_word tl 
;; 

尾

let build_word ?(acc = "") chars = 
    match chars with 
    | [] -> None 
    | [c] -> Some Char.to_string c 
    | hd::tl -> build_word ~acc:(acc^Char.to_string hd) tl 
;; 

向前遞推是公認的答案很好解釋由@ sepp2k。