The Project | About Us | Contribute | Donations | License

HOME

Recursion is a fundamental concept in Prolog and many other programming languages. It allows a function or predicate to call itself in order to solve a problem. In Prolog, recursion is often used to process lists, trees, and other data structures. This section will cover the basics of recursion, provide practical examples, and include exercises to help you master this concept.

Key Concepts

Base Case: The condition under which the recursion stops. It prevents infinite recursion and typically handles the simplest instance of the problem.
Recursive Case: The part of the predicate that calls itself with a modified argument, gradually reducing the problem size.

Practical Examples

Example 1: Calculating the Length of a List

Let's start with a simple example: calculating the length of a list.

% Base case: The length of an empty list is 0.
list_length([], 0).

% Recursive case: The length of a list is 1 plus the length of the tail.
list_length([_|Tail], Length) :-
    list_length(Tail, TailLength),
    Length is TailLength + 1.

Explanation:

The base case states that the length of an empty list ([]) is 0.
The recursive case states that the length of a list is 1 plus the length of the tail (Tail). The underscore (_) is used to ignore the head of the list.

Example 2: Summing the Elements of a List

Next, let's sum the elements of a list.

% Base case: The sum of an empty list is 0.
list_sum([], 0).

% Recursive case: The sum of a list is the head plus the sum of the tail.
list_sum([Head|Tail], Sum) :-
    list_sum(Tail, TailSum),
    Sum is Head + TailSum.

Explanation:

The base case states that the sum of an empty list is 0.
The recursive case states that the sum of a list is the head (Head) plus the sum of the tail (Tail).

Exercises

Exercise 1: Factorial

Write a Prolog predicate factorial/2 that calculates the factorial of a number.

% Base case: The factorial of 0 is 1.
factorial(0, 1).

% Recursive case: The factorial of N is N times the factorial of N-1.
factorial(N, Result) :-
    N > 0,
    N1 is N - 1,
    factorial(N1, Result1),
    Result is N * Result1.

Solution:

% Base case: The factorial of 0 is 1.
factorial(0, 1).

% Recursive case: The factorial of N is N times the factorial of N-1.
factorial(N, Result) :-
    N > 0,
    N1 is N - 1,
    factorial(N1, Result1),
    Result is N * Result1.

Exercise 2: Fibonacci Sequence

Write a Prolog predicate fibonacci/2 that calculates the N-th Fibonacci number.

% Base cases: The first two Fibonacci numbers are 0 and 1.
fibonacci(0, 0).
fibonacci(1, 1).

% Recursive case: The N-th Fibonacci number is the sum of the (N-1)-th and (N-2)-th Fibonacci numbers.
fibonacci(N, Result) :-
    N > 1,
    N1 is N - 1,
    N2 is N - 2,
    fibonacci(N1, Result1),
    fibonacci(N2, Result2),
    Result is Result1 + Result2.

Solution:

% Base cases: The first two Fibonacci numbers are 0 and 1.
fibonacci(0, 0).
fibonacci(1, 1).

% Recursive case: The N-th Fibonacci number is the sum of the (N-1)-th and (N-2)-th Fibonacci numbers.
fibonacci(N, Result) :-
    N > 1,
    N1 is N - 1,
    N2 is N - 2,
    fibonacci(N1, Result1),
    fibonacci(N2, Result2),
    Result is Result1 + Result2.

Common Mistakes and Tips

Forgetting the Base Case: Always ensure you have a base case to prevent infinite recursion.
Incorrect Recursive Case: Make sure the recursive case correctly reduces the problem size.
Stack Overflow: Deep recursion can lead to stack overflow. Consider using tail recursion or iterative solutions for large inputs.

Conclusion

Recursion is a powerful tool in Prolog that allows you to solve complex problems by breaking them down into simpler subproblems. By understanding the base case and recursive case, you can implement recursive predicates to process lists, calculate mathematical functions, and more. Practice the provided exercises to reinforce your understanding and prepare for more advanced topics in Prolog.

Recursion

Key Concepts

Practical Examples

Example 1: Calculating the Length of a List

Example 2: Summing the Elements of a List

Exercises

Exercise 1: Factorial

Exercise 2: Fibonacci Sequence

Common Mistakes and Tips

Conclusion

Prolog Programming Course

Module 1: Introduction to Prolog

Module 2: Basic Prolog Programming

Module 3: Data Structures in Prolog

Module 4: Advanced Prolog Programming

Module 5: Prolog in Practice

Module 6: Advanced Topics and Optimization