functional-programming - 即使我在OCaml中使用了尾递归，为什么仍会出现stackoverflow？

我写了一个在randomized ints中生成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错误，对吗？

任何想法？

最佳答案

从core library documentation


val append：'一个列表->'一个列表->'一个列表
列出两个列表。与中缀运算符@的功能相同。不是尾递归的（第一个参数的长度）。 @运算符也不是尾递归的。


因此，导致溢出的不是您的函数，而是@函数。但是，由于您只关心生成随机列表，因此没有理由在列表末尾附加内容。即使@运算符是尾递归的，列表附加仍为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 []);;

关于functional-programming - 即使我在OCaml中使用了尾递归，为什么仍会出现stackoverflow？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15065998/