序言遞歸返回多個結果

開始這是一個準備給我的作業問題。序言遞歸返回多個結果

我應該寫一個謂詞btree_height \ 2，它需要一棵二叉樹並且（現在）只返回樹的高度。

二進制樹被表示爲：

node(node(leaf, x, leaf), x, node(leaf, x, leaf))

其中x是節點的整數值。（這只是一個示例樹）。

我的代碼如下：

btree_height(leaf, 0). 
btree_height(node(leaf,_,leaf), 1). 
btree_height(node(LT,_,RT), D):- 
    btree_height(LT, DL), 
    btree_height(RT, DR), 
    D is max(DL,DR)+1.

，我遇到的問題是，當我打電話btree_height（BT，d），並用一個BT供給它，如果深度爲4則遞歸4次並將數字4「返回」四次。據我的教授說，這是一個不正確的行爲，因爲它應該只返回一次數字4。（使用上面的例子，它返回數字2兩次）

這是我第一次在Prolog中編碼，我不知道應該從哪裏開始尋找。

這在技術上是SWI-Prolog的，如果它有差別......

來源

2012-10-12 OmegaTwig

注我刪除'homework'標記[因爲它已被正式棄用]（http://meta.stackexchange.com/questions/147100/the-homework-tag-is-now-officially-deprecated） – kaveman

由於這是家庭作業，我不會給你完整的解決方案。

當您的謂詞擊中匹配node(leaf, _, leaf)的節點時，它首先執行第二個子句。那會返回一個。然後，當您要求它回溯時，它也會執行第三個條款，因爲也匹配LT=leaf和RT=leaf的輸入，所以它會遞歸兩次並且兩次都擊中leaf的情況。

下一次，如果你要調試這樣的問題自己，trace/1是一個很好的工具：（它說creep，我按輸入）

2 ?- trace. 
true. 

[trace] 2 ?- btree_height(node(node(leaf, x, leaf), x, node(leaf, x, leaf)), H). 
    Call: (6) btree_height(node(node(leaf, x, leaf), x, node(leaf, x, leaf)), _G821) ? creep 
    Call: (7) btree_height(node(leaf, x, leaf), _G903) ? creep 
    Exit: (7) btree_height(node(leaf, x, leaf), 1) ? creep 
    Call: (7) btree_height(node(leaf, x, leaf), _G903) ? creep 
    Exit: (7) btree_height(node(leaf, x, leaf), 1) ? creep 
    Call: (7) _G821 is max(1, 1)+1 ? creep 
    Exit: (7) 2 is max(1, 1)+1 ? creep 
    Exit: (6) btree_height(node(node(leaf, x, leaf), x, node(leaf, x, leaf)), 2) ? creep 
H = 2 ; 
    Redo: (7) btree_height(node(leaf, x, leaf), _G903) ? creep 
    Call: (8) btree_height(leaf, _G903) ? creep 
    Exit: (8) btree_height(leaf, 0) ? creep 
    Call: (8) btree_height(leaf, _G903) ? creep 
    Exit: (8) btree_height(leaf, 0) ? creep 
    Call: (8) _G911 is max(0, 0)+1 ? creep 
    Exit: (8) 1 is max(0, 0)+1 ? creep 
    Exit: (7) btree_height(node(leaf, x, leaf), 1) ? creep 
    Call: (7) _G821 is max(1, 1)+1 ? creep 
    Exit: (7) 2 is max(1, 1)+1 ? creep 
    Exit: (6) btree_height(node(node(leaf, x, leaf), x, node(leaf, x, leaf)), 2) ? creep 
H = 2

來源

2012-10-12 23:52:33

謝謝！我剛剛結束刪除btree_height（node（leaf，_，leaf），1）行，因爲我已經有一個基本情況。現在我覺得很愚蠢...... – OmegaTwig

序言遞歸返回多個結果

回答

相關問題