云昴

[Learn Prolog Now 3] Recursion

| Prolog

本文英文原文: http://www.learnprolognow.org/ 并会增加自己在Imperial学习中的一些想法,因为自己已经熟悉Prolog,并非完整翻译。

基础

当我们写一个递归的谓词逻辑时,应该至少包含两个子句:一个是基础子句(用于在某些条件下停止递归),另一个是递归子句。如果没有这样做,那么Prolog就会陷入死循环中。

Descendant

child(anne, bridget).

child(bridget, caroline).

child(caroline, donna).

child(donna, emily).

descend(X, Y):- child(X, Z_1), child(Z_1, Z2), child(Z_2, Y).

descend(X, Y) :- child(X, Z_1), child(Z_1, Z_2), child(Z_2, Z_3), child(Z_3, Y).

不够优雅。应当使用递归。

descend(X, Y) :- child(X, Y).

descend(X, Y) :- child(X, Z), descend(Z, Y).

尾递归

尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形,即最后一步新调用的返回值直接被当前函数的返回结果。

云昴