OCaml：如何执行使用尾递归的程序？

Question

我正在使用尾递归编写一个函数，但我不知道如何执行。正常情况下，我使用ocaml QuicksortTail.ml Qsort，但是当我对一个有70000个元素的列表执行时，出现错误：

Fatal error: exception Stack_overflow"

let rec trev l r = 
    match l with
        | [] -> r
        | x::xs -> trev xs (x::r);;
let rev l = trev l [];;

List.iter (fun x->print_int x) (rev[5;4;3;2;1])

我的 oCaml 是 4.01。

Answer 1

据我所知，@RichouHunter 是正确的。

为了完整起见，这里是一个顶层会话，显示您的代码工作正常：

$ rlwrap ocaml
        OCaml version 4.03.0

# let rec trev l r =
    match l with
        | [] -> r
        | x::xs -> trev xs (x::r);;
val trev : 'a list -> 'a list -> 'a list = <fun>
# let rev l = trev l [];;
val rev : 'a list -> 'a list = <fun>

# let rec range accum m n = if m > n then accum else range (n :: accum) m (n - 1);;
val range : int list -> int -> int -> int list = <fun>

# let big = range [] 1 70000;;
val big : int list =
  [1; 2; 3; ...]
# let revbig = rev big;;
val revbig : int list =
  [70000; 69999; 69998; ...]

正如@RichouHunter 所说，运行尾递归代码没有什么特别的。

Answer 2

尾递归是一种特殊的递归，其中递归调用是函数中的最后一次调用。它不是一种执行模式，因此您无需将任何特定标志传递给解释器或编译器来启用或禁用尾递归。它是您程序的静态属性。

当调用处于尾部位置时，（是否是递归调用并不重要），OCaml 编译器将发出不使用堆栈的代码 space.口译员也是如此。调用不会消耗堆栈 space，因此您可以执行几乎无限次尾调用而不会出现堆栈溢出。

由于您遇到堆栈溢出，这意味着某些东西不是尾递归的。您刚刚展示的代码很好，并且完全是尾递归的，因此实际上是其他代码引发了异常。不是你的 rev。

OCaml：如何执行使用尾递归的程序？

OCaml: How Can I execute a program that uses Tail Recursion?

ocaml

tail-recursion