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?).

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

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

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

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

"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']         |
+----------------------------------+

Answer 2

loop

函数不是尾递归的。您可以看到它对递归调用的返回值应用了一个操作 (

::

)。这可以防止它成为尾递归。即，递归调用不在尾部。

更新

这里是一个尾递归函数，用于将字符串更改为字符列表。我希望我不是在为你做作业。

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

正如我在评论中所说，这是您进行函数式编程绝对必须熟悉的内容。但是一旦你看到窍门就不难了。

通常有必要以相反的顺序积累一个列表，然后在最后反转它。添加到列表的末尾太慢了（它往往会产生二次复杂度）。

更新 2

这是一个更高效的尾递归版本，它不需要 List.rev 和 String.length 调用：

let string_to_list str =
    let rec loop accum i =
        if i < 0 then
            accum
        else
            loop (str.[i] :: accum) (i - 1)
    in
    loop [] (String.length str - 1)

（事实上这是一个非常好的获取字符列表的方法，但是它没有教最重要的向后累加结果并在最后反转的技术。:-)