1

我觉得它很不直截了当,但我想我明白了它的要点,请确认我是否错了。

append([],L,L).
   append([H|T],L2,[H|L3])  :-  append(T,L2,L3). 

这是关于规则和跟踪的查询。

?-  append([a,b,c],[1,2,3],X) 

append([a,  b,  c],  [1,  2,  3],  _G518)
   append([b,  c],  [1,  2,  3],  _G587)
   append([c],  [1,  2,  3],  _G590)
   append([],  [1,  2,  3],  _G593)
   append([],  [1,  2,  3],  [1,  2,  3])
   append([c],  [1,  2,  3],  [c,  1,  2,  3])
   append([b,  c],  [1,  2,  3],  [b,  c,  1,  2,  3])
   append([a,  b,  c],  [1,  2,  3],  [a,  b,  c,  1,  2,  3])

   X  =  [a,  b,  c,  1,  2,  3]
   yes 

append(T,L2,L3), 向前“递归”,减小列表 [H|T] 的大小,然后 append([H|T],L2,[H|L3]) 向后“递归”,增加列表 L3 的大小。所以,如果我理解正确,规则总是向后“递归”,而它的条件总是向前“递归”,对吗?另外,是什么让算法向后追加“递归”?是追加([],L,L)吗?还是在达到基本情况后总是向后“递归”?

令人困惑的是,更简单的序言递归只会向前“递归”。如果我没记错的话,祖先(E,F)只会向前“递归”。

4

1 回答 1

0

这里是关于第三个参数 X 的全部内容。它以大写字母开头,所以它是一个变量。Prolog 需要为这个变量找到一个值。

每次append([H|T], L2, [H|L3])被调用,它都会调用append(T, L2, L3).

append(T, L2, L3)被调用时,Prolog 将首先检查它是否合适append([], L, L),因为这是程序的第一个子句。

如果不合适,Prolog 将转到第二个子句:append([H|T],L2,[H|L3]).

如果第一个参数是空列表,则它适合:[]。如果所有元素(在这种情况下为字母)已被删除,则会发生这种情况。该子句将返回第二个参数 L 作为第三个参数。从头到尾,第二个参数一直[1,2,3]存在。它只存在于这一刻。

空列表[]是基本情况:递归不会从那里更深入,因为该子句没有append再次调用的主体。这是找到结果(第三个参数)的第一个元素的点:L,即[1, 2, 3]。这个结果作为 L3 返回给append调用它的那个,它会将它与它的 H: 结合起来,[H|L3][c, 1, 2, 3]. 这反过来又返回给append调用那个的那个。这种结果的回馈一直持续到最初的、第一次调用的 append 得到它的结果。然后 Prolog 将其打印出来。

在跟踪中,您可以看到像_G518. 在前三行中,尚未达到基本情况,因此无法填写第三个参数(H 已知但 L3 未知)。

于 2013-09-28T20:04:12.853 回答