修改Prolog代码以生成斐波那契序列的所有前缀列表

需求回顾 #

原有代码仅能生成到指定N的完整斐波那契数列列表，现需修改为：

• 调用fib(L, N)时，依次输出该序列的所有前缀列表（如fib(L,3)返回[0]、[0,1]、[0,1,1]、[0,1,1,2]）
• 支持fib(L, [])调用，无限生成斐波那契前缀列表

修改后的代码实现 #

% 尾递归优化的斐波那契数计算，避免重复子问题计算
fibb(0, 0).
fibb(1, 1).
fibb(N, F) :-
    N > 1,
    fibb_tail(N, 1, 0, F).

fibb_tail(2, A, B, F) :- F is A + B.
fibb_tail(N, A, B, F) :-
    N > 2,
    N1 is N - 1,
    NewA is A + B,
    fibb_tail(N1, NewA, A, F).

% 生成对应K的斐波那契前缀列表（K为序列最后一个元素的索引）
fib_prefix(0, [0]).
fib_prefix(K, L) :-
    K > 0,
    K1 is K - 1,
    fib_prefix(K1, L1),
    fibb(K, F),
    append(L1, [F], L).

% 处理指定N的情况：遍历0到N的所有索引，生成对应前缀
fib(L, N) :-
    integer(N),
    N >= 0,
    between(0, N, K),
    fib_prefix(K, L).

% 处理无限生成的情况：遍历从0开始的无限索引，持续生成前缀
fib(L, []) :-
    between(0, inf, K),
    fib_prefix(K, L).

代码说明 #

1. 尾递归优化的斐波那契计算：替换原有递归实现，避免重复计算子问题，大幅提升效率，尤其是生成较长序列时。
2. 前缀生成逻辑：fib_prefix/2通过递归逐步构建前缀列表，每个新前缀基于前一个前缀追加当前索引对应的斐波那契数。
3. 多结果回溯支持：
   • 对于fib(L, N)，利用between(0, N, K)遍历所有可能的前缀长度索引，Prolog回溯时会依次返回每个索引对应的前缀列表。
   • 对于fib(L, [])，使用between(0, inf, K)实现无限遍历，持续生成新的前缀。

测试示例 #

• 指定N的调用结果：

?- fib(L, 3).
L = [0] ;
L = [0, 1] ;
L = [0, 1, 1] ;
L = [0, 1, 1, 2] ;
false.

• 无限生成的调用结果：

?- fib(L, []).
L = [0] ;
L = [0, 1] ;
L = [0, 1, 1] ;
L = [0, 1, 1, 2] ;
L = [0, 1, 1, 2, 3] ;
L = [0, 1, 1, 2, 3, 5] ;
... % 可无限继续生成

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