Updated April 6, 2023
Introduction to Prolog Recursion
The prolog recursion is defined as, in prolog, the recursion seems when a predicate has some goal which referred to itself, the recursion is a function that can call itself until the goal succeeds, the predicates in prolog recursion are recursively defined because it has more than one rule in defining to refer itself, recursion is a powerful tool and it is widely used in prolog, it can also be used by many different data structures where the structures include sub-structures, it has two components one is base recursion and another is recursion itself, it mainly involves the predicates to calling itself, so prolog supports recursion.
Syntax:
The syntax of recursion by using the family relationship:
predecessor(M,O) :- parent(M,O).
predecessor(M,O) :- parent(M,N),predecessor(N,O).
So, the first line as the parent(M, O) has some facts given from there it will get instantiated, which is also called a base case, the second line shows the recursive relationship.
The clauses are divided into facts and rules.
- Facts: The clauses without a body is called facts,
Syntax:
parent(M,O).Which can be equivalent to-
parent(M,O):- true.- Rule: The rule is a type of form, it has been used to call the predicates and as we know the predicates are in-built in prolog.
For example, we have the clause that ‘Brain:- Heart.’, so it means ‘Brain is true if Heart is true’.
How Recursion Works in Prolog?
The recursion is a very powerful tool in prolog, recursion is used by many programming languages. So we wish to perform some operations either over data structure or until a certain point to be reached, in prolog this repetition is called recursion. It can also be used by many data structures so recursive data structure is the one where the structures include the sub-structures whose function is the same as that of the whole structure.
The predicate we are using in recursion is recursive in nature. We will see the working of recursion with the help of one example,
Example:
is_eating(S, T):- just_cook(S, T).is_eating(S, T):- just_cook(S, R),is_eating(R, T).So, this type of predicates is called recursive, so if we say that ‘just_cook(veg, food)’ it means that ‘is_eating(veg, food)’ is true. Now if we say ‘is_eating(nonveg, food)’ this will be true if ‘is_eating(nonveg, food):- just_cook(nonveg, veg), is_eating(veg, food)’, then the statement ‘is_eating(nonveg, food)’ is also true.
Let us see the working of recursion in family relationship, so we know that what is recursion, recursion is having mainly two issues, first is that for starting inputs and outputs are known to us so it is known as base case recursion, in prolog it will be satisfied by the given facts and another issue is that a prolog program or the prolog function can call itself, so we will see when the prolog calling itself in its declaration, so this can also a good example of recursion. So in other programming languages, we might have used recursion and prolog supports recursion and here in a family relationship, we can use recursion. As we have already defined parent, male, mother, father, haschild, brother, sister, grandparent, wife, and uncle family relationship and now we will see predecessor relationship. If P is the parent of Q then obviously P can be treated as a predecessor of Q, but if we go one step that means if P is the parent of Q and Q is the parent of R then we can say that P is the predecessor of R, similarly, if P is the parent of Q1 and Q1 is the parent of Q2 and Q2 is the parent of R then P can be called as the predecessor of R. In this way, we can move up to n number of levels.
predecessor(P,R):- parent(P,R).predecessor(P,R):- parent(P,Q),predecessor(Q,R).In the above clauses we have declared predecessor(P, R) clause, we can demonstrate or say the above clause as the predecessor(P, R) if a parent(P, R) otherwise predecessor(P, R) if the parent(P, Q) and predecessor(Q, R), so in this way in predecessor declaration we use recursion. In the case of recursion, it has two issues one is that recursion has some base case where the algorithm gets terminate, the recursion algorithm must have a calling instruction itself either directly or indirectly. The predecessor(P, R) will be nothing but if P is one level higher than R then it will work otherwise we will go for multilevel higher. We are using predecessor on left and right both so that why it is a good example of recursion.
Example #1
Code:
:-initialization(main).
main :- write('Recursion').
sumlist([], 0).
sumlist([First | Item], Sum) :-
sumlist(Item, SumOfItem),
Sum is First + SumOfItem.Input:
sumlist([4, 2, 3], Answer).
Output:
In the above program, we use recursive procedure ‘sumlist’, in every recursive call of ‘sumlist’ there is a separate instance of variables First, Item, Sum, SumofItem, and these are distinguished by a subscript, so it created First1 instance for First to call ‘sumlist’ and also First2 instance created for First in first recursive calling to call ‘sumlist’. We wrote a program to show the sum by putting the input which is given above.
Example #2
Code:
:- initialization(main).
main :- write('fact and rule in recursion').
hat(beautiful).
item(X) :- hat(X).Input:
- hat(beautiful).
- hat(X).
Output:
In the above example, we explain the working of facts and rules in recursion by using prolog computer language. As prolog has an in-built predicate true/0 is always true. Hence to ask for given facts, we have given input as ‘hat(beautiful).’ it will give an output Yes. And when we give input ‘hat(X).’ then it will give the output with its value provided in code so it is ‘X=beautiful’ with yes, which is shown in the screenshot.
Conclusion
In the above article, we conclude that the prolog recursion is a technique to refer itself with some goal, it has declarative syntax with its rules, which has predecessor logic to show the relationship between family, we can also conclude that prolog is very comfortable with using recursive rules by using recursion we can easily find the ancestor.
Recommended Articles
We hope that this EDUCBA information on “Prolog Recursion” was beneficial to you. You can view EDUCBA’s recommended articles for more information.
