即使我在OCaml中使用尾递归,为什么我仍然得到stackoverflow？

Question

我写了一个函数,生成一个randomized intsin 的列表OCaml.

---

let create_shuffled_int_list n = 
  Random.self_init;
  let rec create n' acc =
    if n' = 0 then acc
    else 
      create (n'-1) (acc @ [Random.int (n/2)])
  in 
  create n [];;

---

当我试图生成10000整数时,它会给出Exception: RangeError: Maximum call stack size exceeded.错误.

但是,我相信函数,我已经使用了tail-recursion它不应该给出stackoverflow错误,对吧？

任何的想法？

Answer 1

来自核心库文档

val append:'列表 - >'列表 - >'列表Catenate两个列表.与中缀运算符@功能相同.不是尾递归(第一个参数的长度).@运算符也不是尾递归的.

所以这不是你的功能造成溢出,而是@功能.然而,看起来你只关心生成一个混洗列表,没有理由将内容添加到列表的末尾.即使@运算符是尾递归的,列表追加仍然是O(n).然而,列表前置是O(1).因此,如果您将新的随机数添加到列表的前面,则可以避免溢出(并使您的功能更快):

let create_shuffled_int_list n = 
  Random.self_init;
  let rec create n' acc =
    if n' = 0 then acc
    else 
      create (n'-1) (Random.int (n/2) :: acc)
  in 
  create n [];;

如果您关心订单(不确定原因),那么只需在最后贴上List.rev:

List.rev (create n []);;