Prolog Recursion returns multiple results

Question

To start off this is a homework question poised to me.

I am supposed to write a predicate btree_height\2 that takes a Binary tree and (for now) just returns the height of the tree.

A binary tree is represented as:

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

where the x's are integer values of the node. (This is just an example tree).

My code is as follows:

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.

The problem that I am having is that when I call btree_height(BT, D) and supply it with a BT if the depth is 4 then it recurses 4 times and "returns" the number 4 four times. According to my professor this is an incorrect behavior as it should only return the number 4 once. (Using the example above it returns the number 2 twice)

This is my first time coding in Prolog and I have no idea where I should start looking.

This is technically SWI-Prolog if it makes a difference...

note I removed the homework tag because it is officially deprecated — kaveman

Fred Foo Fred Foo · Accepted Answer · 2012-10-12T23:52:33

Since this is homework, I won't give you the full solution.

When your predicate hits a node that matches node(leaf, _, leaf), it first executes the second clause. That returns one. Then, when you ask it to backtrack, it will also execute the third clause, because that also matches the input with LT=leaf and RT=leaf, so it will recurse twice and hit the leaf case both times.

Next time, if you have to debug this kind of problem yourself, trace/1 is a good tool:

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

(Where it says creep, I pressed Enter.)

Prolog Recursion returns multiple results

1 Answers