Prolog实现降序幂列表生成时出现无限递归的原因是什么

核心故障原因 #

你的代码出现无限递归栈溢出，是三个逻辑缺陷共同导致的：

• 递归谓词powersAux没有设置终止分支。代码逻辑为只要算出的M的E次幂Z满足Z<=N，就会把E加1继续递归；当Z超过N时，你没有写对应的终止规则，Prolog会持续回溯尝试更大的E值计算幂，递归永远不会停止，最终占满内存栈。
• 列表构造逻辑错误。你从E=0（对应M的0次幂1，是最小的幂值）开始计算，还把新算出的Z拼到已有列表头部，就算递归能停，得到的也是升序列表[1,3,9]，不符合降序返回的要求；且代码中没有对结果变量做正确的递归绑定，无法正确返回列表。
• 基础谓词power缺少边界约束。当传入的指数Y为无约束变量时，规则会持续计算Y-1往负方向递归，也会触发无界计算。

修正方案 #

补全递归终止条件、添加剪枝避免无意义回溯、调整列表构造逻辑即可，修正后可运行代码如下：

% 带边界剪枝的幂计算谓词，避免无界递归
power(_, 0, 1) :- !.
power(X, Y, Z) :- 
    X > 0,
    Y > 0,
    Yminus1 is Y - 1,
    power(X, Yminus1, Z1), 
    Z is X * Z1.

% 辅助谓词：先收集所有<=N的M的幂为升序列表
collect_powers(M, N, E, Acc, Res) :-
    power(M, E, Z),
    Z =< N,
    !, % 剪枝：当前幂合法时不再回溯其他分支
    E1 is E + 1,
    collect_powers(M, N, E1, [Z|Acc], Res).
% 递归终止分支：当前幂超过N时，反转累计列表得到降序结果
collect_powers(_, _, _, Acc, Res) :- reverse(Acc, Res).

% 主调用入口
powers(M, N, Res) :-
    integer(M), integer(N),
    M > 0, N >= 1,
    collect_powers(M, N, 0, [], Res).

调用示例：执行powers(3, 9, Res).会返回Res = [9, 3, 1]，符合预期。

内容的提问来源于stack exchange，提问作者atd