Why Prolog Predicates Recurse
Prolog has no built-in loop constructs like for or while; iteration is expressed through recursion, where a predicate calls itself with a smaller or reduced argument each time until a base case is reached. This mirrors mathematical induction: prove a base case directly, then prove the inductive step assuming the smaller case already holds, and let the recursive calls chain that reasoning together at run time.
Cricket analogy: Recursion is like a Test match's overs: each over calls the next over with one fewer over remaining in the day's quota, recursing down until zero overs are left and the session ends, exactly like a base case.
Base Cases and Recursive Cases
A recursive predicate typically has at least two clauses: a base case that matches a terminating condition directly, such as N=0 or list=[], and a recursive case that matches a general shape and calls the predicate again on a reduced argument. Prolog tries clauses top-to-bottom and backtracks into later clauses on failure, so clause order affects which solution is found first even though both clause types are needed for the predicate to terminate correctly.
Cricket analogy: The base case is like a declared innings: runs keep piling up recursively over by over until the captain declares, similar to factorial(0,1) stopping the multiplication chain the moment N reaches zero.
% factorial/2: base case and recursive case
factorial(0, 1).
factorial(N, F) :-
N > 0,
N1 is N - 1,
factorial(N1, F1),
F is N * F1.
?- factorial(5, F).
F = 120.
Recursion Over Lists
Recursion is the natural way to walk a list: pair a base case for [] (returning some terminal value or accumulated result) with a recursive case for [H|T] that processes H and then recurses on T. This mirrors recursion over integers counting down to zero, except the structure shrinking toward the base case is the list's tail rather than a number. Threading a running total through an extra accumulator argument is a common refinement that lets many Prolog systems apply tail-call optimization on long lists.
Cricket analogy: Processing a list of scores recursively is like a scorer tallying one delivery at a time: the base case is no balls left in the innings, and the recursive case is record this ball's runs, then tally the rest of the over.
An accumulator-based recursive predicate, for example summing a list by threading a running total through an extra argument, allows many Prolog implementations to apply last-call or tail-call optimization, avoiding growth of the environment stack on long lists compared to a naive non-accumulating version.
Mutual Recursion and Termination
Predicates can also recurse indirectly through each other, called mutual recursion, such as is_even/1 defined in terms of is_odd/1 and vice versa. Whatever the recursion shape, every argument that changes across recursive calls must move toward some base case, or the predicate will recurse forever. Forgetting to shrink an argument, or having clause ordering that lets backtracking retry the same non-terminating path, is one of the most common sources of runaway recursion and stack overflow bugs.
Cricket analogy: Mutual recursion is like two commentators handing commentary back and forth ball by ball, one calling odd-numbered balls and the other even-numbered ones, terminating only when both agree there are no balls left.
Forgetting to shrink the recursive argument, for example writing count_down(N) :- N > 0, write(N), count_down(N). instead of count_down(N-1), causes infinite recursion and, in most Prolog systems, a stack overflow rather than a clean failure.
- Prolog has no native loop keywords; iteration is expressed via recursive predicate calls.
- A recursive predicate needs at least one base case clause and one recursive clause.
- The recursive case must call the predicate with an argument that moves toward the base case.
- List recursion typically pairs a base case of [] with a recursive case of [H|T].
- Accumulator arguments enable a tail-recursive style, which many systems optimize to avoid stack growth.
- Mutual recursion lets two or more predicates call each other, as long as every thread eventually reaches a base case.
- Missing or unreachable base cases are the most common cause of infinite recursion and stack overflow.
Practice what you learned
1. What construct does Prolog use instead of for/while loops?
2. In factorial(0,1). factorial(N,F):-N>0,N1 is N-1,factorial(N1,F1),F is N*F1. what is the base case?
3. What typically causes infinite recursion in a Prolog predicate?
4. What is mutual recursion?
5. Why are accumulator arguments useful in recursive list predicates?
Was this page helpful?
You May Also Like
Lists in Prolog
Learn how Prolog represents lists as recursive [Head|Tail] structures and how unification lets you construct, deconstruct, and pattern-match them.
List Processing Built-ins
Master Prolog's standard list library predicates, member/2, append/3, length/2, reverse/2, nth0/3, maplist/2-4, and findall/3, for common list tasks without hand-rolled recursion.
Arithmetic in Prolog
Learn how Prolog evaluates arithmetic expressions with is/2, the difference between unification and arithmetic comparison, and common numeric predicates.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics