Recursion in Prolog

Our example demonstrates recursive functions in Prolog. Here’s a classic example of factorial calculation.

% This fact/2 predicate uses recursion until it reaches the base case of fact(0, 1).
fact(0, 1).
fact(N, Result) :-
    N > 0,
    N1 is N - 1,
    fact(N1, SubResult),
    Result is N * SubResult.

% Main predicate to demonstrate usage
main :-
    fact(7, Result),
    write(Result), nl,
    fib(7, FibResult),
    write(FibResult), nl.

% Fibonacci sequence using recursion
fib(0, 0).
fib(1, 1).
fib(N, Result) :-
    N > 1,
    N1 is N - 1,
    N2 is N - 2,
    fib(N1, Result1),
    fib(N2, Result2),
    Result is Result1 + Result2.

In Prolog, recursion is a fundamental concept. The fact/2 predicate calculates the factorial of a number. It has a base case fact(0, 1). and a recursive case for all other numbers.

The fib/2 predicate calculates the Fibonacci sequence. It has two base cases for fib(0, 0) and fib(1, 1), and a recursive case for all other numbers.

To run this program, save it in a file (e.g., recursion.pl) and use a Prolog interpreter:

$ swipl -s recursion.pl -g main -t halt
5040
13

This will load the file, call the main/0 predicate, and then exit. The output shows the factorial of 7 (5040) and the 7th Fibonacci number (13).

In Prolog, we don’t need to explicitly declare variables or use closures for recursion. The language naturally supports recursive definitions through its declarative nature and unification mechanism.