递归函数中大整数的异常 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

问题是 none 你的递归函数是尾递归的。

尾递归意味着调用者不应执行进一步的操作（参见 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])

尝试将您的其他函数转换为尾递归函数，看看它能给您带来什么。

Answer 2

最好解决上面提到的根本问题，但如果你真的需要大筹码，设置ulimit -s。另见：

递归函数中大整数的异常 Stack_overflow

Exception Stack_overflow for big integer in recursive functions

stack-overflow

ocaml

fatal-error