提问者:小点点

有人能解释一下prolog使用这个递归程序所做的步骤吗?


我最近开始学习prolog,但我很难使用递归规则。我理解简单的规则,但我在这个例子中遇到了麻烦,我发现一个程序给出了列表中所有元素的总和:

addup([], 0).

addup([FirstNumber | RestOfList], Total) :-
    addup(RestOfList, TotalOfRest),   
    Total is FirstNumber + TotalOfRest.

现在,如果我跟踪它,我得到以下内容:

[trace]  ?- addup([3, 5, 7], Total).
   Call: (7) addup([3, 5, 7], _G322)
   Call: (8) addup([5, 7], _L1)
   Call: (9) addup([7], _L2)
   Call: (10) addup([], _L3)
   Exit: (10) addup([], 0)    % I understand what it does till here
^  Call: (10) _L2 is 7+0
^  Exit: (10) 7 is 7+0
   Exit: (9) addup([7], 7)
^  Call: (9) _L1 is 5+7
^  Exit: (9) 12 is 5+7
   Exit: (8) addup([5, 7], 12)
^  Call: (8) _G322 is 3+12
^  Exit: (8) 15 is 3+12
   Exit: (7) addup([3, 5, 7], 15)
Total = 15.

我理解最初的几个步骤;它不断削减并创建新的TotalOfRest,直到原始列表为空并与第一个事实匹配。这使得第三个TotalOfRest(我称之为_L3)等于0。但是现在呢?prolog如何使L2等于7 0的步骤。我知道prolog开始回溯,但是什么与得出这个结论相匹配?Total现在是7吗?或者有三个不同的Total具有不同的值,就像TotalOfRest一样?RestofList仍然等于[],FirstNumber仍然是7吗?

所以基本上:prolog是如何从弄清楚L3到最终结论的?

我对这个很陌生,所以如果有人能慢慢为我解释,我会非常感激!


共1个答案

匿名用户

请注意,您的递归调用引入了一个新变量:

addup([], 0).
addup([FirstNumber | RestOfList], Total) :-
    addup(RestOfList, TotalOfRest),   
    Total is FirstNumber + TotalOfRest.

在每个递归级别,都会创建一个新的TotalOfRest变量。请注意,上层递归级别的TotalRest与递归中更深的级别不同。

trace使用变量的名称可能更方便:

[trace]  ?- addup([3, 5, 7], Total).
   Call: (7) addup([3, 5, 7], _Total)
   Call: (8) addup([5, 7], _TotalOfRest1)
   Call: (9) addup([7], _TotalOfRest2)
   Call: (10) addup([], _TotalOfRest3)
   Exit: (10) addup([], 0)
^  Call: (10) _TotalOfRest2 is 7+0
^  Exit: (10) 7 is 7+0
   Exit: (9) addup([7], 7)
^  Call: (9) _TotalOfRest1 is 5+7
^  Exit: (9) 12 is 5+7
   Exit: (8) addup([5, 7], 12)
^  Call: (8) _Total is 3+12
^  Exit: (8) 15 is 3+12
   Exit: (7) addup([3, 5, 7], 15)
Total = 15.

因此,如果执行递归调用,则会创建一个新的变量_TotalOfRest1。调用是递归完成的,直到_TotalOfRest3。现在在该级别_TotalOfRest3=0设置为0。但是递归中仍然有命令需要解决:Total是FirstNumber TotalOfRest。。请注意,所有这些Total都是局部变量(这也适用于TotalOfRestFirstNumber)。所以在每个级别都解决了这个问题。请注意,例如递归级别2的Total实际上是调用者的_TotalOfRest2

所以递归看起来像:

addup([3, 5, 7], Total) :-
    % FirstNumber = 3
    % RestOfList = [5, 7]
    % Total = Total
    addup([5,7], _TotalOfRest1) :-
         % FirstNumber = 5
         % RestOfList = [7]
         % Total = _TotalOfRest1
         addup([7], _TotalOfRest2) :-
             % FirstNumber = 7
             % RestOfList = []
             % Total = _TotalOfRest2
             addup([],_TotalOfRest3),
             % resolved to _TotalOfRest3 = 0
             Total is 7 + 0.
             % resolved to Total = 7
         % resolved to _TotalOfRest2 = 7
         Total is 5 + 7.
         % resolved to Total = 12
     % resolved to _TotalOfRest1 = 12
     Total is 3 + 12.
     % resolved to Total = 15
% resolved tot Total = 15

代码部分以粗体书写,您会看到在每个级别都有局部变量被接地并传达回外部范围。