ocaml - 递归函数中大整数的异常 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::... 并且这个函数最终不是 tail -递归。

另一种尾递归方式是这样的:

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])

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