Prolog and Recursion

Unlike languages we have learned previously, such as Java, Prolog uses loops often, but they are not declared in the syntax the same way Java is. Prolog uses the process called recursion in order to allow for a set of instructions to occur multiple times until a specific condition is met. Prolog can not execute a task without the usage of recursion because recursion only appears when a predicate containing the goal refers to itself. There are certain ways recursion can be used in Prolog. The recursive rule definition in Prolog is defined by two rules, one defining the direct predecessor, and the second being the indirect predecessor.

Let’s look at an example of how the predecessor and indirect predecessor can be defined. We can say that “some X is an indirect predecessor of some Z if there is a parentship chain of people between X and Z” (Prolog: Programming for Artificial Intelligence, Ivan Bratko). The program I am using is a family program that does a very good job explaining how recursion works. In order to find the condition that is specifically requested by the user, the program runs through the first line, the second, and so on in order to unify the parent to the predecessor. If the first line (fact) is true, then the program stops calling.

This image above is created in Word Pad and later called in SWI-Prolog. The relations above explain that the first object (X) is the parent to the second object (Y). Each line declares which person is the parent of the previous object. When ancestor is called we use the “recursive rule for ancestor”. In order to see what ancestor is, the program reads through each line, and not until the line of parent(tom,bob). does the call to ancestor succeed. After that, each line through the call of ancestor is successful because it is referring to a line above that meets the request of the user. We can assume that ancestor refers to a line of the family that falls before the called object.

Although I created some errors in testing my program, the outcomes that all read true are the outcomes to be focused on. For the first input, I asked if tom was a parent to bob. By reading through the lines until finding what was called, the first input is true. The next input asked if tom is an ancestor to bob which claimed the statement was true because for bob, the ancestor is tom. On line nine, I asked for who was tom an ancestor to? I replaced the object following tom with Z because that is the letter I used to call the parent and who they are an ancestor to. The output for this was bob, so this proves that the program read through each line until it called itself. Finally, on line eleven, I asked the program if pam was an ancestor to bob. By reading through the program, the output reads true. Because the output is true, this means that for bob, the ancestor is pam, even though she is from a previous relation above. By using the recursive rule of ancestor, the program reads through each line to see if what was called is the ancestor to the previous object (Z) who is either a child to or an ancestor to another object.

I used another example to show how Prolog uses recursion. For this example, I used Prolog to calculate factorials with recursion. I created each number to only hold one solution when writing the code in Word Pad. What this example shows is that when the user calls to find a factorial of six the program will first run through the list of numbers, 0!,1!,2!,3!,4!,  5! and 6!. This means that that the program tries to calculate not (!) each number until reaching six, and then the result will be 0!*1*2*3*4*5*6. This means that each number except for zero, stated in the Word Pad document:

X1 is X – 1,

factorial(X1,Z),

Y is Z*X,!.
is called to be multiplied by the number following it until reaching the number called, which is six. This is an example of recursion because the program will loop through a list of numbers endlessly to be multiplied by the previous solution to reach a factorial of the number called. It is finding the result to itself.

The code above is what was created in the Word Pad document.

The results formed in SWI-Prolog are what is shown. What is entered by the user is the call to find the factorial (X) of the number five, six or one. I called random numbers to show different results, but what the program did is run through a number starting at zero for each number called by the user. Until the program finds the number called (itself), it will continuously run through the program.

I felt that trying to figure out what recursion meant for Prolog was somewhat difficult, but by looking at examples online and in the book I use as a source, I was really able to understand how recursion rules work. Recursion is a process that I was not familiar with.

The sources I used for this blog post and examples are:

Prolog: Programming for Artificial Intelligence by Ivan Bratko

and

http://boklm.eu/prolog/page_6.html#622 (this site is what allowed me to find helpful examples I could understand and present)