Prolog实现Log Base 2计算器出现栈溢出问题该如何解决？

你写的递归逻辑缺少边界校验和回溯控制，触发了无限递归：

1. 终止子句logBase2(1,0)没有加切断，当2的整数次幂查询得到第一个正确解后，Prolog会回溯进入第二个递归子句，开始无限执行N/2操作，永远匹配不到终止条件，导致栈溢出
2. 没有对输入和递归过程中的值做合法性校验，非2的整数次幂的数值在递归过程中永远得不到整数1，会一直递归下去直到栈溢出

整数对数版本（仅支持2的整数次幂输入，非次幂直接返回false） #

修改后代码如下：

% 终止条件，加切断禁止回溯
logBase2(1, 0) :- !.
% 递归子句，新增前置校验
logBase2(N, R) :-
    % 校验N为大于1的整数
    integer(N),
    N > 1,
    % 校验N是偶数，保证除2后仍为整数
    N mod 2 =:= 0,
    N1 is N // 2,
    logBase2(N1, R1),
    R is R1 + 1.

验证效果 #

• 输入logBase2(16, R)，返回R = 4，尝试获取其他解直接返回false，无栈溢出
• 输入logBase2(10, R)，直接返回false，无栈溢出

近似浮点版本（支持任意正实数输入，返回近似对数结果） #

如果需要支持非2的整数次幂的近似计算，可以使用带精度控制的版本：

% 精度阈值，可根据需求调整
epsilon(0.000001).

logBase2(N, R) :-
    N > 0,
    epsilon(Eps),
    log_base2_inner(N, Eps, 0, R).

% 终止条件：N与1的差值小于精度阈值时返回累计结果
log_base2_inner(N, Eps, Acc, Acc) :-
    abs(N - 1) < Eps,
    !.
% N大于2时正方向递归
log_base2_inner(N, Eps, Acc, R) :-
    N >= 2,
    !,
    N1 is N / 2,
    Acc1 is Acc + 1,
    log_base2_inner(N1, Eps, Acc1, R).
% N小于1时负方向递归
log_base2_inner(N, Eps, Acc, R) :-
    N < 1,
    N1 is N * 2,
    Acc1 is Acc - 1,
    log_base2_inner(N1, Eps, Acc1, R).

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