这段代码是尾递归的吗？

Question

我正在尝试在 Prolog 中为 AdventCode 第 6 天编写一个解决方案。 (http://adventofcode.com/day/6)

之前我编写了一个动态创建和替换谓词的解决方案，以跟踪灯光。毫不奇怪，它相当慢，所以我决定尝试使用更多 "functional" 风格来编写它；即创建一个包含所有灯的列表，然后操作该列表。

我正在尝试构建初始列表，它将包含一百万个元素，每个元素一个术语 light(X, Y, Status)。我想我应该从一个列表 [light(0, 0, off)] 开始，然后在其前面加上新的术语。为此，我查看列表的第一个元素，然后确定下一个元素应该是什么，然后将其添加到前面。重复。

我有一个谓词 next_light/2，它接受一盏灯并确定下一盏灯（要添加的）应该是什么。如果不需要添加更多的灯，它 returns done:

next_light(light(X, Y, _), NextLight) :-
    X < 999,
    NextX is X + 1,
    NextLight = light(NextX, Y, off).
next_light(light(999, Y, _), NextLight) :-
    Y < 999,
    NextY is Y + 1,
    NextLight = light(0, NextY, off).
next_light(light(999, 999, _), done).

然后我尝试使用以下代码构建列表：

init_lights(Lights) :-
    gen_lights([light(0, 0, off)], Lights).

gen_lights(Lights, AllLights) :-
    [Light|_] = Lights,
    next_light(Light, NextLight),
    add_light(Lights, NextLight, AllLights).

add_light(Lights, done, Lights).
add_light(Lights, NextLight, AllLights) :-
    gen_lights([NextLight|Lights], AllLights).

然而，当我在 SWI-Prolog 中运行 init_lights(L) 时，我得到 "ERROR: Out of local stack"。所以有一个堆栈溢出，但是当我查看代码时，它看起来是尾递归的。 add_light 和 gen_lights 是相互递归的；不确定这是否是个问题。

我尝试使用调试器检查调用，但显然 SWI-Prolog 在使用 trace 时关闭了尾调用优化，所以这没有帮助。

（郑重声明，当我将代码更改为使用 3 而不是 999 作为最大坐标时，init_lights(L) 似乎生成了正确的列表，并且没有挂起或导致堆栈溢出。）

我可能忽略了一些东西，但我没有看到。欢迎任何提示！ ^_^

Answer 1

您非常接近解决方案：您的子句是尾递归，但尾递归优化仅在代码 确定性 时才有用！在您的代码中，next_light/2 留下了选择点，因为编译器无法判断哪些情况是互斥的，因此在尾递归调用后无法回收帧。

您可以通过多种方式改进确定性。最丑陋和最容易出错的方法是在一些重要的地方添加 !/0：小心这一点，因为这会破坏代码的许多良好的声明属性。

使用 if-then-else 等功能稍微好一点，但也几乎总是声明错误。

一种更安全、更通用的方法是使用具有 clpfd 约束的 zcompare/3 等功能。

这段代码是尾递归的吗？

Is this code tail-recursive?

tail-recursion

prolog