functional-programming - 评估期间的堆栈溢出（循环递归？）。OCaml

Question

我正在尝试编写一个接受 int n 并返回从 n 到 0 的列表的函数。

这就是我所拥有的

let rec downFrom n =
let m = n+1 in
if m = 0 then                                                                                  
  []                                                                                           
else                                                                                            
  (m-1) :: downFrom (m - 1);;

该函数编译正常，但是当我使用任何 int 对其进行测试时，它会在评估期间给我错误堆栈溢出（循环递归？）。

我知道这是阻碍的本地变量，但我不知道另一种声明它的方式。谢谢！！！

Answer 1

首先，你的程序真正的问题是你有一个无限循环。为什么，因为你的归纳基本情况是 0，但你总是停留在n！这是因为你递归m - 1哪个是真的n + 1 - 1

我对为什么会编译感到惊讶，因为它不包含rec递归函数所必需的关键字。为了避免 OCaml 中的堆栈溢出，您通常会切换到尾递归样式，如下所示：

let downFrom n =
  let rec h n acc = 
    if n = 0 then List.rev acc else h (n-1) (n::acc)
  in
  h n []

---

有人建议进行以下编辑：

let downFrom n =
    let rec h m acc =
        if m > n then acc else h (m + 1) (m::acc)
    in
    h 0 [];

我同意，这节省了对 List.rev 的调用。

Answer 2

递归的关键是递归调用必须是问题的较小版本。您的递归调用不会创建较小版本的问题。它只是重复同样的问题。

Answer 3

您可以尝试使用过滤参数语法：

let f = function
   p1 -> expr1
 | p2 -> expr2
 | p3 -> ...;;

---

let rec n_to_one =function
  0->[]
  |n->n::n_to_one (n-1);;

# n_to_one 3;;
- : int list = [3; 2; 1]