ocaml - ocaml 尾递归函数

Question

当我在很长的输入上运行以下函数时，我正在使用 utop 运行 Ocaml：

let string_to_list str =
  let rec loop i limit =
    if i = limit then []
    else (String.get str i) :: (loop (i + 1) limit)
  in
  loop 0 (String.length str);;

它返回以下错误：

Stack overflow during evaluation (looping recursion?).

该函数的尾递归版本是什么？

标签： ocamlstack-overflowtail-recursion

Answer 1

正如 Jeffrey Scofield 所指出的，您的函数不是尾递归的。将其转换为使用尾递归将涉及向您的函数引入累加器参数loop。

let string_to_list str =
  let rec loop i limit acc =
    if i = limit then acc
    else 
      let ch = String.get str i in
      loop (i + 1) limit (ch :: acc)
  in
  loop 0 (String.length str) [] |> List.rev

这样，评估函数所需的所有信息都包含在一个堆栈帧中，编译器可以优化掉所有先前的堆栈帧。

为了在纯文本中提供一点视觉效果，我们看一下函数的非尾递归版本，称为 on "hello"。

+-----------------------+
| string_to_list "hello"|->
+-----------------------+ |
^      v------------------+
| +--------+
<-|loop 0 5|->
  +--------+ |
  ^      v---+
  | +--------+
  <-|loop 1 5|->
    +--------+ |
    ^      v---+
    | +--------+
    <-|loop 2 5|->
      +--------+ |
      ^      v---+
      | +--------+
      <-|loop 3 5|->
        +--------+ |
        ^      v---+
        | +--------+
        <-|loop 4 5|->
          +--------+ |
          ^      v---+
          | +--------+
          <-|loop 5 5|
            +--------+

随着我们的进行，每个呼叫都需要前一个呼叫中的信息。但是，如果loop通过参数传递所有必要的信息（累积的结果列表），则不需要loop任何先前调用的迭代来完全评估。

     +-----------------------+
     | string_to_list "hello"|
     +-----------------------+
                |
                v
+----------------------------------+
|loop 0 5 []                       |
+----------------------------------+
                |
                v
+----------------------------------+
|loop 1 5 ['h']                    |
+----------------------------------+
                |
                v
+----------------------------------+
|loop 2 5 ['e'; 'h']               |
+----------------------------------+
                |
                v
+----------------------------------+
|loop 3 5 ['l'; 'e'; 'h'].         |
+----------------------------------+
                |
                v
+----------------------------------+
|loop 4 5 ['l'; 'l'; 'e'; 'h']     |
+----------------------------------+
                |
                v
+----------------------------------+
|loop 5 5 ['o'; 'l'; 'l'; 'e'; 'h']|
+----------------------------------+
                |
                v
+----------------------------------+
|List.rev ['o'; 'l'; 'l'; 'e'; 'h']|
+----------------------------------+
                |
                v
+----------------------------------+
|['h'; 'e'; 'l'; 'l'; 'o']         |
+----------------------------------+