異常STACK_OVERFLOW用於遞歸函數大整數

Question

我的快速排序代碼適用於的N（列表的大小）的一些值，但對於大的值（例如，N = 82031）由OCaml的返回的錯誤是：

Fatal error: exception Stack_overflow.

我做錯了什麼？
由於OCaml不支持大值的遞歸函數，我應該創建一個迭代版本嗎？

let rec append l1 l2 = 
    match l1 with 
    | [] -> l2 
    | x::xs -> x::(append xs l2) 


let rec partition p l = 
    match l with 
    | [] -> ([],[]) 
    | x::xs -> 
     let (cs,bs) = partition p xs in 
     if p < x then 
     (cs,x::bs) 
     else 
     (x::cs,bs) 


let rec quicksort l = 
    match l with 
    | [] -> [] 
    | x::xs -> 
     let (ys, zs) = partition x xs in 
     append (quicksort ys) (x :: (quicksort zs));; 

Answer 1

問題是你的遞歸函數都不是尾遞歸的。

尾遞歸意味着主叫方不應該採取進一步行動（請參閱here）。在這種情況下，不需要保持調用者函數的環境，並且堆棧沒有充滿遞歸調用的環境。像OCaml這樣的語言可以以最佳方式編譯，但爲此您需要提供尾遞歸函數。

例如，你的第一個功能，append：

let rec append l1 l2 = 
    match l1 with 
    | [] -> l2 
    | x::xs -> x::(append xs l2) 

正如你所看到的，append xs l2被稱爲後，主叫方需要執行x :: ...而這個函數因爲不是尾遞歸結束。

在尾遞歸的方式做這件事的另一種方法是這樣的：

let append l1 l2 = 
    let rec aux l1 l2 = 
    match l1 with 
     | [] -> l2 
     | x::xs -> append xs (x :: l2) 
    in aux (List.rev l1) l2 

但是，實際上，你可以嘗試使用List.rev_append知道這個功能將追加l1和l2但l1將得到扭轉（ List.rev_append [1;2;3] [4;5;6]給出[3;2;1;4;5;6]）

嘗試轉換你的其他函數在尾遞歸的，看看它給你什麼。