问题中的递归决策树

Question

所以我试图画出2个Prolog问题树的决定，一个使用累加器，另一个不使用累加器。这里是我的问题和解决办法我没分别，：

length([H|T],N) :- length(T,N1), N is N1+1. 
length([ ],0). 
Goal: ?: length([1,2,3],N) 

第二个累加器：

length_acc(L,N) :- len_acc(L,0,N). 
len_acc([H|T], A, N) :- A1 is A+1, len_acc(T, A1, N). 
len_acc([], A, A). 
Goal: ?-length_acc([1,2], N). 

是决策树正确绘制？还是我犯了一个错误？什么是绘制这种递归决策树的正确方法？

感谢。

Answer 1

您所指的树通常称为搜索树又名SLD树，不要与证明树混淆。

两个你所概述的问题是搜索树的最简单的例子：

• 只有一个解决方案
• 查询不会失败
• 在搜索的每一步只能匹配单个子句（空列表与非空列表）

这三个特征意味着SLD树中只有一个分支。

你会得到下面的搜索树：

注意，它是一个正确的搜索树，最多一个目标是在每个解决这使得搜索树非常大......因此人们常常会在每一步中解决多个目标的简化树，这可能不是真正的搜索树，而是以更简洁的方式说明了搜索。

树中的边缘被替换标记，这些替换作为统一算法的一部分应用于变量。

搜索树与痕迹密切对应，您通常可以从程序的踪迹到搜索树进行直接翻译。

我建议你研究具有多个答案和可能失败的分支的查询的搜索树，这会给出更多有趣的树与多个分支。从序言中的技术人员通过英镑，夏皮罗一个例子：

计划：

father(abraham, isaac).  male(isaac) 
father(haran, lot).   male(lot). 
father(haran, milcah).   female(milcah). 
father(haran, yiscah).   female(yiscah). 

son(X,Y):- father(Y,X), male(X). 
daughter(X,Y):- father(Y,X), female(X). 

查询：

?: son(S, haran) 

搜索树：