Prolog Recursion returns multiple results

Question

To get started, this is a question asked for me.

I have to write the predicate btree_height \ 2, which takes a binary tree and (for now) just returns the height of the tree.

The binary tree is represented as:

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

where x are integer values ​​of node. (This is just an example of a 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 I am facing is that when I call btree_height (BT, D) and supply it to BT, if the depth is 4, it repeats 4 times and “returns” the number 4 four times. According to my professor, this is a misconduct since it should only return number 4 once. (Using the example above, it returns number 2 twice)

This is my first Prolog encoding, and I have no idea where I should start looking.

This is technically SWI-Prolog, if that matters ...

Answer 1

Since this is homework, I will not give you a complete solution.

When your predicate hits a node that matches node(leaf, _, leaf) , it first executes the second sentence. This returns one. Then, when you ask him to return, he will also execute the third sentence, because it also matches the input with LT=leaf and RT=leaf , so he will overwrite twice and hit the leaf event twice.

Next time, if you need to debug this 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 he says creep , I hit Enter .)