这是我用 Prolog 制作的阶乘代码的问题

Question

我编写了两个代码来用 Prolog 计算阶乘。
第一个是

factorial(0, 1).
factorial(N, Result) :-
   N > 0, factorial(N - 1, Interim), Result is N * Interim.

，第二个是

factorial(0, 1).
factorial(N, Result) :-
   N > 0, M is N - 1, factorial(M, Interim), Result is N * Interim.

虽然第一个代码有堆栈溢出错误，但第二个代码运行正常。

为了测试我做了如下代码

sum_2(N, R) :- R is N + 2.
sum_f(N, R) :- sum_2(N + 2, R).

以上代码正常执行

我不明白为什么第一个计算阶乘的代码是堆栈溢出错误。

如果你能告诉我原因，我将不胜感激。

Answer 1

您确定第一个版本出现堆栈溢出吗？你怎么称呼它？像 factorial(5, Result) 这样的调用应该会失败，即导致像 false 或 no.

这样的答案

Prolog 不像其他编程语言那样“计算表达式”。像 N - 1 这样的术语只是数据：一个带有函子 - 和两个参数 N 和 1 的术语。即使 N 绑定到某个数字，比如 5，该术语仍然只是 5 - 1 而不是 4。如果您专门询问 is 谓词或算术比较谓词之一（>、=<，则它仅映射到 4 , =:=, 等) 对其进行评估。

因此，如果您将第一个 factorial 谓词称为 factorial(5, Result)，则会发生以下情况：

目标factorial(5, Result)与factorial(0, 1)不统一，本条略过
目标 factorial(5, Result) 与 factorial(N, Result) 和统一符 N = 5 统一，此子句的主体与此绑定一起执行
- 目标5 > 0成功
- 执行调用factorial(5 - 1, Interim)：
  - 目标factorial(5 - 1, Interim)与factorial(0, 1)不统一，本条略过
  - 目标 factorial(5 - 1, Interim) 与 factorial(N, Result) 与统一符 N = 5 - 1 和 Interim = Result 统一，此子句的主体与此绑定一起执行
    - 目标5 - 1 > 0成功
    - 执行调用factorial((5 - 1) - 1, Interim)：
      - ...

这最终会调用 factorial 并使用更大的术语 5、5 - 1、(5 - 1) - 1、((5 - 1) - 1) - 1 等等。由于这些项中的 none 与 0 统一，因此计算永远不会成功。由于这些术语中的每一个都与 N 的新副本统一，因此第二个子句始终匹配，但最终您会达到一个包含足够 - 1 步的术语，因此目标 N > 0 将失败，并且查询 factorial(5, Result) 将失败。

这是我用 Prolog 制作的阶乘代码的问题

Here is a problem with the factorial code that I made with Prolog

recursion

prolog

factorial