异常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]）

尝试转换你的其他函数在尾递归的，看看它给你什么。