如何在不使用DCG的L-system启发重写系统中实现Prolog递归

你需要将当前头部元素的替换结果，和尾部递归处理后的替换结果做拼接即可，使用Prolog内置的append/3就能实现该逻辑，修改后的linden谓词如下：

linden([], []). 
linden([H|T], Next) :-
    % 匹配当前元素的替换规则，无匹配规则则保留原元素（方便后续添加常量）
    (rule(H, E) -> true ; E = [H]),
    % 递归处理列表剩余元素，得到尾部的替换结果
    linden(T, Rest),
    % 拼接头部替换序列和尾部替换结果，得到完整的新世代列表
    append(E, Rest, Next).

你原来写的单元素分支可以删除，上述通用递归逻辑已经覆盖了空列表、单元素、多元素的所有场景。

如果你想要先生成嵌套列表提升可读性，后续再展平的方案也可以实现，代码如下：

% 先生成嵌套替换列表
linden_nested([], []).
linden_nested([H|T], [E|RestNested]) :-
    (rule(H, E) -> true ; E = [H]),
    linden_nested(T, RestNested).

% 展平嵌套列表得到最终结果
linden(List, Result) :-
    linden_nested(List, Nested),
    flatten(Nested, Result).

修改完成后运行generate.即可得到你预期的迭代输出：

a
ab
aba
abaab
abaababa
...

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