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

Question

我的Quicksort代码适用于N的某些值(列表大小),但对于较大的值(例如,N = 82031),OCaml返回的错误是:

致命错误:异常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

问题是没有一个递归函数是尾递归的.

尾递归意味着调用者不应该进行进一步的操作(参见这里).在这种情况下,不需要保持调用函数的环境,并且堆栈没有填充递归调用的环境.像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])

尝试用尾递归方式转换其他函数,看看它给你的东西.