为什么我的递归在 OCaml 中永远不会终止？

Question

let qrec=Queue.create ()

let rec queueaddrec1 n=
 if n==1 then
  Queue.add 1 qrec
 else
  Queue.add n qrec;
  queueaddrec1 (n-1)

let ()=
 queueaddrec1 5;
 Queue.iter print_int qrec;

VScode 告诉我以下行永远不会返回。我不明白为什么。当我运行它时，我陷入了无限循环。

queueaddrec1 5

如果我写这个：

let rec queueaddrec2 n=
 if n>1 then
  Queue.add n qrec;
  queueaddrec (n-1)
 else
  Queue.add 1 qrec

我收到另一个错误：

This expression has type 'a but an expression was expected of type 
('b->'b Queue.t->unit)->int->int Queue.t->'a
The type variable 'a occurs inside
('a->'a Queue.t->unit)->int->int Queue.t->'b

Answer 1

您应该使用代码格式化工具：您的缩进在欺骗您。 正确缩进并删除

==

的使用（这不是您想要的等式），函数的第一个版本如下：

let rec queueaddrec1 n=
 if n=1 then
  Queue.add 1 qrec
 else
  Queue.add n qrec;
 queueaddrec1 (n-1)

您需要括号来组成整个序列

Queue.add n qrec; queueaddrec1 (n-1)

else

分支的一部分。

您的第二个版本在语法上无效，缩进正确，并且没有多余的空格，它读作

let rec queueaddrec2 n=
 if n>1 then
  Queue.add n qrec;
 queueaddrec (n-1) else Queue.add 1 qrec

关键字

else

出现在任何

if ... then ... 

之外。

Answer 2

作为八时答案的附录，这里的根本原因是 OCaml 的 if/then/else 具有比 ; 更高的

优先级

。也许有些令人困惑，匹配和函数构造具有 lower 优先级，因此以下内容无需使用括号对表达式进行分组即可工作。

let rec add n = 
  match n with 
  | 1 -> Queue.add 1 qrec 
  | _ -> 
    Queue.add n qrec; 
    add (n - 1)

或者：

let rec add = function 
  | 1 -> Queue.add 1 qrec 
  | n -> 
    Queue.add n qrec; 
    add (n - 1)

现在，因为无论哪种情况，你都会添加当前数字，并且只有当它是

1

时才不会递归，你可以写：

let rec add n = 
  Queue.add n qrec;
  if n <> 1 then add (n - 1)

考虑一下，即使进行了这些修复，您的函数也无法终止，除非

n

是

1

。从小于

1

的 int 开始仍然会产生无界递归。