例外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 :: ...を実行する必要があり、この関数は末尾再帰されていないことで終わります。 （この機能はl1とl2を追加することを知ってList.rev_appendを使用しようとすることができますがl1が逆になり、実際に、

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 [1;2;3] [4;5;6]は[3;2;1;4;5;6]となります）

他の機能をテール再帰的なものに変換して、それが何を提供しているかを確認してください。