functional-programming - 为什么即使我在 OCaml 中使用了尾递归，我仍然得到 stackoverflow？

Question

我在 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

来自core library documentation

val append : 'a list -> 'a list -> 'a list Catenate two lists. Same function as the infix operator @. Not tail-recursive (length of the first argument). The @ operator is not tail-recursive either.

因此导致溢出的不是您的函数，而是 @ 函数。然而，由于您只关心生成一个打乱的列表，因此没有理由将内容附加到列表的末尾。即使 @ 运算符是尾递归的，list 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 []);;