Download Introduction to Prolog Programming

56
A.2
Appendix A. Recursive Programming
The Recursion Principle
The basic idea of recursive programming, the recursion principle is the following: To
solve a complex problem, provide the solution for the simplest problem of its kind and
provide a rule for transforming such a (complex) problem into a slightly simpler problem.
In other words, provide a solution for the base case and provide a recursion rule
(or step). You then get an algorithm (or program) that solves every problem of this
particular problem class.
Compare: Using induction, we prove a statement by going from a base case “up”
through all cases. Using recursion, we compute a function for an arbitrary case by going
through all cases “down” to the base case.
Recursive definition of functions. The factorial n! of a natural number n is defined
as the product of all natural numbers from 1 to n. Here’s a more formal, recursive
definition (also known as an inductive definition):
1! = 1
n! = (n − 1)! · n
for n > 1
(base case)
(recursion rule)
To compute the actual value of, say, 5! we have to pass through the second part of that
definition 4 times until we get to the base case and are able to calculate the overall result.
That’s a recursion!
Recursion in Java. Here’s a Java method to compute the factorial of a natural number. It is recursive (for didactic reasons; note that this is not the best way of implementing
the factorial in Java).
public int
if (n ==
return
} else {
return
}
}
factorial(int n) {
1) {
1;
// base case
factorial(n-1) * n;
// recursion step
Recursion in Prolog.
factorial(1, 1).
The definition of a Prolog predicate to compute factorials:
% base case
factorial(N, Result) :- % recursion step
N > 1,
N1 is N - 1,
factorial(N1, Result1),
Result is Result1 * N.