How does recursive back tracking works in Prolog

Question

I am learning Prolog and I have difficulty in understanding the recursive backtracking. I am trying to understand how the search tree looks like while backtracking and I am kind of lost.

Say for Example the below lines of code, removes all the occurrences of an element from a list :

remove_all(_, [], []).
remove_all(El, [El|Tail], Tail2):- 
    remove_all(El, Tail, Tail2).
remove_all(El, [Head|Tail], [Head|Tail2]):-
    not(El = Head),
    remove_all(El, Tail, Tail2).

Now I query the following ?- remove_all( 2, [1,4,2,3,5,2,7,2], X). I used the online SWISH Prolog to execute it with the trace and I got the following tree

 Call:remove_all(2, [1, 4, 2, 3, 5, 2, 7, 2], _4896)
 Call:not(2=1)
 Exit:not('10758ac0-dc91-4335-a0d8-48b7b11776c0' : (2=1))
 Call:remove_all(2, [4, 2, 3, 5, 2, 7, 2], _5128)
 Call:not(2=4)
 Exit:not('10758ac0-dc91-4335-a0d8-48b7b11776c0' : (2=4))
 Call:remove_all(2, [2, 3, 5, 2, 7, 2], _5146)
 Call:remove_all(2, [3, 5, 2, 7, 2], _5146)
 Call:not(2=3)
 Exit:not('10758ac0-dc91-4335-a0d8-48b7b11776c0' : (2=3))
 Call:remove_all(2, [5, 2, 7, 2], _5164)
 Call:not(2=5)
 Exit:not('10758ac0-dc91-4335-a0d8-48b7b11776c0' : (2=5))
 Call:remove_all(2, [2, 7, 2], _5182)
 Call:remove_all(2, [7, 2], _5182)
 Call:not(2=7)
 Exit:not('10758ac0-dc91-4335-a0d8-48b7b11776c0' : (2=7))
 Call:remove_all(2, [2], _5200)
 Call:remove_all(2, [], _5200)
 Exit:remove_all(2, [], [])
 Exit:remove_all(2, [2], [])
 Exit:remove_all(2, [7, 2], [7])
 Exit:remove_all(2, [2, 7, 2], [7])
 Exit:remove_all(2, [5, 2, 7, 2], [5, 7])
 Exit:remove_all(2, [3, 5, 2, 7, 2], [3, 5, 7])
 Exit:remove_all(2, [2, 3, 5, 2, 7, 2], [3, 5, 7])
 Exit:remove_all(2, [4, 2, 3, 5, 2, 7, 2], [4, 3, 5, 7])
 Exit:remove_all(2, [1, 4, 2, 3, 5, 2, 7, 2], [1, 4, 3, 5, 7])
X = [1, 4, 3, 5, 7]

What I am not able to understand is how the backtracking is happening in these lines of code

 Exit:remove_all(2, [], [])
 Exit:remove_all(2, [2], [])
 Exit:remove_all(2, [7, 2], [7])
 Exit:remove_all(2, [2, 7, 2], [7])
 Exit:remove_all(2, [5, 2, 7, 2], [5, 7])
 Exit:remove_all(2, [3, 5, 2, 7, 2], [3, 5, 7])
 Exit:remove_all(2, [2, 3, 5, 2, 7, 2], [3, 5, 7])
 Exit:remove_all(2, [4, 2, 3, 5, 2, 7, 2], [4, 3, 5, 7])
 Exit:remove_all(2, [1, 4, 2, 3, 5, 2, 7, 2], [1, 4, 3, 5, 7])

How does the Prolog interpreter perform recursion on this? Can some please explain.

Kintalken Kintalken · Accepted Answer · 2019-11-07T10:14:17

The issue of backtracking is not relevant to this example .

Prolog , like most other languages , maintains a function stack . When a function is called , it and its arguments are pushed on the stack . When a function is done , it and its arguments are popped from the stack .

When function 'a' is called , and 'a' in turn calls function 'b' : whilst within 'b' both 'b' and 'a' are on the stack ; when 'b' completes only 'a' is on the stack ; when 'a' completes nothing is on the stack .

When function 'a' is called , and 'a' in turn calls function 'b' , and 'b' in turn calls function 'c' : whilst within 'a' only 'a' is on the stack : whilst within 'b' both 'b' and 'a' are on the stack : whilst within 'c' allof 'c' and 'b' and 'a' are on the stack ; when 'c' completes both 'b and 'a' are on the stack ; when 'b' completes only 'a' is on the stack ; when 'a' completes nothing is on the stack .

The same thing happens if 'a' instead of calling 'b' calls itself recursively .

When function 'a(1)' is called , and 'a(1)' in turn calls function 'a(2)' , and 'a(2)' in turn calls function 'a(3)' : whilst within 'a(1)' only 'a(1)' is on the stack : whilst within 'a(2)' both 'a(2)' and 'a(1)' are on the stack : whilst within 'a(3)' allof 'a(3)' and 'a(2)' and 'a(1)' are on the stack ; when 'a(3)' completes both 'a(2) and 'a(1)' are on the stack ; when 'a(3)' completes only 'a(1)' is on the stack ; when 'a(1)`' completes nothing is on the stack .

The function in the example calls itself recursively thus it builds up a stack . Each time it calls itself the stack depth increases . Since each time it calls itself there is one less item in the list and it stops calling itself when 0 items are in the list it follows that the function will establish a stack depth of function calls equal in size to the size of the original list . When the function is finally called with list of size 0 it no longer invokes itself recursivly ; therefore it returns thus the stack decreases by 1 , now the function call that had list of size 1 returns thus the stack decreases by 1 , now the function call that had list of size 2 returns thus the stack decreases by 1 , now the function call that had list of size 3 returns thus the stack decreases by 1 ,... and so on .

With that explanation perhaps the following formatting of Your debug output will be helpful .

        Call:remove_all(2, [1, 4, 2, 3, 5, 2, 7, 2], _4896)
            Call:remove_all(2, [4, 2, 3, 5, 2, 7, 2], _5128)
                Call:remove_all(2, [2, 3, 5, 2, 7, 2], _5146)
                    Call:remove_all(2, [3, 5, 2, 7, 2], _5146)
                        Call:remove_all(2, [5, 2, 7, 2], _5164)
                            Call:remove_all(2, [2, 7, 2], _5182)
                                Call:remove_all(2, [7, 2], _5182)
                                    Call:remove_all(2, [2], _5200)
                                        Call:remove_all(2, [], _5200)
                                        Exit:remove_all(2, [], [])
                                    Exit:remove_all(2, [2], [])
                                Exit:remove_all(2, [7, 2], [7])
                            Exit:remove_all(2, [2, 7, 2], [7])
                        Exit:remove_all(2, [5, 2, 7, 2], [5, 7])
                    Exit:remove_all(2, [3, 5, 2, 7, 2], [3, 5, 7])
                Exit:remove_all(2, [2, 3, 5, 2, 7, 2], [3, 5, 7])
            Exit:remove_all(2, [4, 2, 3, 5, 2, 7, 2], [4, 3, 5, 7])
        Exit:remove_all(2, [1, 4, 2, 3, 5, 2, 7, 2], [1, 4, 3, 5, 7])

56th

How does recursive back tracking works in Prolog

1 Answers