struggling to understand PROLOG's recursive funtions

Hope you guys can help me to understand how recursive works in PROLOG. In PROLOG, when defining a recursive funvtion, we need 2 things:

1) the Base case ( to stop the rescursion)
2) the Recursive case ( where the rescursion will actually start)

lets say i have a list that we want to sums all the numbers inside:

% base case
addup([], 0).

% recursive case:
addup([FirstNumber | RestOfList], Total) :-
addup(RestOfList, TotalOfRest),
Total is FirstNumber + TotalOfRest.

ok assuming in the terminal we put:

?-addup([1,2,3], X).

what i understand is that, PROLOG will look at the base case 1st, if it does not match, it will then ( only then ) go to the Recursive case right?

after one of the numbers in the list have been pushed out from the list ( lets say number 1), PROLOG will sum the number and go back to the base case. it it matches, then it stop, if it doesn't it will go back to the recursive case.

is my understanding correct? really have been strugling to understan PROLOG's recursive funtions. Hope someone can verify.

owh, btw, whats the differece between Unification and Equals To in PROLOG

Reply 1

Psyk

16

Jubrits

what i understand is that, PROLOG will look at the base case 1st, if it does not match, it will then ( only then ) go to the Recursive case right?

Not necessarily. Prolog is non-determinstic, meaning that it can match more than one case on the same data. Take this predicate for example:

pred([1|Tail],2).
pred([_,2|Tail],3).

Then if you do the query pred([1,2], R) you would get both R=2 and R=3, because the conditions for both predicates have been met meaning they both succeed.

However your addup predicate looks fine to me in that respect, so in this particular case it would never match both. But it is worth remembering that this is dependent on your predicates, not on the way prolog works.

Jubrits

after one of the numbers in the list have been pushed out from the list ( lets say number 1), PROLOG will sum the number and go back to the base case. it it matches, then it stop, if it doesn't it will go back to the recursive case.

With your predicate it will recurse until it hits the base case, and then it will work it's way backwards summing the numbers.

Reply 2

Jubrits

OP

4

k Psyk i'm really bad at PROLOG recursion, so do bare with me. Lets say i run this:

?- addup([1,2,3], X).

is my understanding correct... first prolog will check the base case:

addup([], 0).

since it is not true, it will then go to the recursive case:

addup([FirstNumber | RestOfList], Total) :-
addup(RestOfList, TotalOfRest),
Total is FirstNumber + TotalOfRest.

ok, the predicate:

addup(RestOfList, TotalOfRest) .

will only take the rest of the list ( which is 2, 3 ). but where did the first item go( where did it stored)? This is whats confusing me since i'm use to Procedural programming, usually we have a variable to hold the data.

and whats the use of TotalOfRest?

for the arithemetic operation:

Total is FirstNumber + TotalOfRest.

after finsihed recursion, only then prolog will perform this operation right?Like you said:

Psyk

With your predicate it will recurse until it hits the base case, and then it will work it's way backwards summing the numbers.

means that when the list is emptied, only then it would summed up?

Why can't we use this instead:

Total is Total + FirstNumber

and if i change the sequance to:

addup([FirstNumber | RestOfList], Total) :-
Total is FirstNumber + TotalOfRest,
addup(RestOfList, TotalOfRest).

there is an infinite loop. Strange since some website advice to put the recursive predicate at that position, for example:

a :- b, a.

hay sorry if i sound very bigginish ( which i am :redface:

). hope you can help me understand it. really interested to know

Reply 3

Psyk

16

Jubrits

k Psyk i'm really bad at PROLOG recursion, so do bare with me. Lets say i run this:

?- addup([1,2,3], X).

is my understanding correct... first prolog will check the base case:

addup([], 0).

since it is not true, it will then go to the recursive case:

addup([FirstNumber | RestOfList], Total) :-
addup(RestOfList, TotalOfRest),
Total is FirstNumber + TotalOfRest.

Yes it will do that, but even if the base case is true, it will still check the recursive case. With this particular predicate it's impossible for both to be true, so it's not an issue.

Jubrits

ok, the predicate:

addup(RestOfList, TotalOfRest) .

will only take the rest of the list ( which is 2, 3 ). but where did the first item go( where did it stored)? This is whats confusing me since i'm use to Procedural programming, usually we have a variable to hold the data.

It's stored on the stack. You can think of it like using recursion in a procedural language. It keeps the data until it has finished processing the predicate, which here isn't until all subsequent recursions have completed.

Jubrits

and whats the use of TotalOfRest?

That's the total that has been calculated so far, when coming back through the stack. So for example for addup([1,2,3], Total), TotalOfRest would be 2+3, and for addup([2,3], Total), it would just be 3.

Jubrits

for the arithemetic operation:

Total is FirstNumber + TotalOfRest.

after finsihed recursion, only then prolog will perform this operation right?Like you said:

means that when the list is emptied, only then it would summed up?

Why can't we use this instead:

Total is Total + FirstNumber

Because there wouldn't be a value in Total yet. The sum so far has been put into TotalOfRest, not Total. Basically everywhere Total occurs in a single predicate will have the same value, otherwise it will fail (not fail as in crash, fail as in it would return 'no'). By using the 'is' keyword you are forcing Total to be equal to something, and this can only be done if Total doesn't already have a value.

Jubrits

and if i change the sequance to:

addup([FirstNumber | RestOfList], Total) :-
Total is FirstNumber + TotalOfRest,
addup(RestOfList, TotalOfRest).

there is an infinite loop. Strange since some website advice to put the recursive predicate at that position, for example:

a :- b, a.

Yes it is better to have it that way round because then it is tail recursive and prolog can optimise it. However, it isn't as simple as just switching them round unfortunately. In this case, you can't do "Total is FirstNumber + TotalOfRest" before the recursive call because TotalOfRest won't be instanciated (ie. won't have a value yet). The way around this is to have an accumulator. The predicate would have to have a 3rd argument which would be the total so far. Then instead of adding into Total, you add TotalSoFar and FirstNumber into a new variable, which you would then pass into the recursive call as the new TotalSoFar. You wouldn't actually do anything to Total until the base case, where you unify it with the third argument. It's probably pretty hard to understand this without seeing the code that goes along with it so I'll do that too:

% base case - here you are taking the total so far and saying that Total is the same thing, ie. unification.
addup([], Total, Total).

% recursive case:
addup([FirstNumber | RestOfList], TotalSoFar, Total) :-
NewTotalSoFar is FirstNumber + TotalSoFar,
addup(RestOfList, NewTotalSoFar, Total).

Then you would have to query it like this: addup([1,2,3],0,Total).
Because TotalSoFar is on the the right hand side of the 'is', it has to be given a value, so you initialise it with 0.

With this new version it adds the number as it goes down the stack instead of when it is coming back up.

Jubrits

hay sorry if i sound very bigginish ( which i am :redface:

). hope you can help me understand it. really interested to know

Thanks for asking because I'm learning Prolog as well and it helps my understanding to explain it to others.

struggling to understand PROLOG's recursive funtions

Related discussions

Latest

Trending

Trending

Articles for you