为什么即使我在OCaml中使用尾递归，也仍然会出现堆栈溢出？

Question

我编写了一个函数，在OCaml中生成一个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附加：'a list -> 'a list ->‘一个list Catenate两个列表。函数与infix运算符@.非尾递归(第一个参数的长度)相同。@运算符也不是尾递归的。

所以造成溢出的不是您的函数，而是@函数。然而，由于您只关心产生一个杂乱的列表，所以没有理由在列表的末尾添加内容。即使@操作符是尾递归的，列表追加仍然是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 []);;

Answer 2

另外，您不应该在函数中调用Random.self_init，因为：

• 函数的用户可能希望控制种子以获得可复制的结果(测试、共享结果.)
• 这可能会用一个不那么随机的熵源来重置种子，你可能只想做一次。