StandardML 阶乘计算在 Poly/ML REPL 中进入无限循环

Question

下面的阶乘函数非常好...

Poly/ML 5.8.3 Development (Git version v5.8.2-297-g8185978a)
> fun fact 0 = 1
# | fact n = n * fact(n-1);
val fact = fn: int -> int
> fact 2;
val it = 2: int
>

但下面将 Poly REPL 带入无限循环。

Poly/ML 5.8.3 Development (Git version v5.8.2-297-g8185978a)
> fun fact 0 = 1
# | fact n = n * fact n-1;
val fact = fn: int -> int
> fact 2;

想知道是什么原因造成的？

Answer 1

n * fact n-1 与 n * (fact n) - 1 相同 - 因此，n 永远不会减少，您的代码最终会一遍又一遍地调用 fact 2。

Answer 2

Science Force Bru 已经有了充分的答案，为了完成，这里有一个手工评估的例子，它应该揭示无限递归：

fact 2 ~> 2 * fact 2-1
       ~> 2 * (2 * fact 2-1)-1
       ~> 2 * (2 * (2 * fact 2-1)-1)-1
       ~> 2 * (2 * (2 * (2 * fact 2-1)-1)-1)-1
       ~> ...

StandardML 阶乘计算在 Poly/ML REPL 中进入无限循环

StandardML factorial evaluation enters infinite loop in Poly/ML REPL

recursion

sml

polyml