Prolog Recursion Length Count

Question

This might be a simple / basic problem but I am having troubles grasping the logic.

I want to calculate the length of the list, using recursion. Imagine having a list [a,b,c,d] for this problem.

We have a basic clause, and a recursive clause as can be seen below. The basic clause always deals with the most basic problem, in this case an empty list. The recursive clause tries to solve the problem for size N-1 of the list.

listLength([],0).

listLength([Head|Tail], Count):-
    listLength(Tail, PartialCount),
    Count is PartialCount+1.

Now, my question is the following:

Let's look at this piece of code:

listLength(Tail, PartialCount)

The program will keep on running until the Tail is empty, which will then pass to listLength([],0). for which PartialCount becomes equal to 0. Then, the program continues to Count is PartialCount+1. and Count becomes equal to 1.

Then the program starts backtracking to the other "unsolved" lengths. First it starts with [d], since this was the last element that it tried to solve, now PartialCount becomes 1, and this is what I don't understand. How come PartialCount suddenly becomes "1", which makes Count equal to 2 afterwards, since in the program, there is no indiciation of re-defining the PartialCount.

The program also backtracks to [c,d], which makes Partial Count equal to 2, and so forth.

Can someone explain how this happens? As far as I know, PartialCount is set to "0" in the listLength([],0] example, but I don't know how its value gets updated? I see thatCount gets updated, but not PartialCount

Tomas By Tomas By · Accepted Answer · 2017-11-18T12:39:17

There is a separate PartialCount in each recursive call. It's like local variables versus global. Local variable masks global variable with the same name. The local variable in the deepest nesting masks the ones outside it.

ADDITION: Here is what happens:

Call [a,b,c,d]
  Call [b,c,d]
    Call [c,d]
      Call [d]
        Call []
        Success (first clause): Count = 0, no ParticalCount
      Success (2nd clause): PartialCount = 0, Count = 1
    Success (2nd clause): PartialCount = 1, Count = 2
  Success (2nd clause): PartialCount = 2, Count = 3
Success (2nd clause): PartialCount = 3, Count = 4

Prolog Recursion Length Count

1 Answers