Programming in Prolog – Recursion
Programming in Prolog
Recursion
Romain Barnoud
Thanks to:
Dr Fariba Sadri
Claudia Schulz
Recursion
De�nition
A recursive predicate is a predicate that calls itself.
rec_pred(x_1, x_2, …, x_n) :-
goal_1,
…,
goal_p,
rec_pred(y_1, y_2, …, y_n),
goal_p_1,
…,
goal_q.
A predicate is tail recrusive if the recursive call is the last goal in each
recursive rule.
Example 1 � Factorial
Mathematical De�nition
n! = 1× 2× 3× · · · × (n − 1)× n
n! = (n − 1)!× n
Prolog Implementation
factorial(N, FN) :-
M is N-1,
factorial(M, FM),
FN is N*FM.
Can you spot the problem?
Example 1 � Factorial
Prolog Implementation � Corrected
factorial(0, 1).
factorial(N, FN) :-
N > 0,
M is N-1,
factorial(M, FM),
FN is N*FM.
Do not forget the base case!
Usually, the base case(s) is/are placed before the recursive case(s).
Recursion vs. Loops
Loops do not exist in Prolog: you have to use recursion!
C++
while(i
A(m − 1,A(m, n − 1)) if m > 0 and n > 0
Prolog Implementation � Revisited
ackermann(0, N, R) :-
R is N+1.
ackermann(M, 0, R) :-
M > 0,
M1 is M-1,
ackermann(M1, 1, R).
ackermann(M, N, R) :-
M > 0, N > 0,
N1 is N-1,
ackermann(M, N1, R1),
M1 is M-1,
ackermann(M1, R1, R).
Di�erent �avours of recursion
Program 1
natural_number(0).
natural_number(N) :-
natural_number(M),
N is M+1.
Program 3
natural_number(0).
natural_number(N) :-
N is M+1,
natural_number(M).
Program 2
natural_number(0).
natural_number(N) :-
natural_number(M),
M is N-1.
Program 4
natural_number(0).
natural_number(N) :-
M is N-1,
natural_number(M).
Di�erent �avours of recursion
Test Generate Remark
Program 1 3 3 Slower than Program 4
Program 2 7 7
Program 3 7 7
Tail recursive,
but does not work
Program 4 3 7
Tail recursive,
most e�cient (for testing)
Why is the tail recursive predicate much faster?
?- nn1(3).
?- nn1(M1),
3 is M1+1.
?- 3 is 0+1.
?- nn1(M2), M1 is M2+1,
3 is M1+1
?- M1 is 0+1,
3 is M1+1.
?- 3 is 1+1
?- nn1(M3), M2 is M3+1,
M1 is M2+1, 3 is M1+1.
?- M2 is 0+1, M1 is M2+1,
3 is M1+1.
?- M1 is 1+1, 3 is M1+1.
?- 3 is 2+1.
yes
Why is the tail recursive predicate much faster?
?- nn1(4).
?- nn1(M1),
4 is M1+1.
?- 4 is 0+1.
?- nn1(M2), M1 is M2+1,
4 is M1+1
?- M1 is 0+1,
4 is M1+1.
?- 4 is 1+1
?- nn1(M3), M2 is M3+1,
M1 is M2+1, 4 is M1+1.
?- M2 is 0+1, M1 is M2+1,
4 is M1+1.
?- M1 is 1+1, 4 is M1+1.
?- 4 is 2+1.
?- nn1(M4), M3 is M4+1,
M2 is M3+1, M1 is M2+1,
4 is M1+1.
Why is the tail recursive predicate much faster?
?- nn1(3).
?- nn1(M1),
3 is M1+1.
?- 3 is 0+1.
?- nn1(M2), M1 is M2+1,
3 is M1+1
?- M1 is 0+1,
3 is M1+1.
?- 3 is 1+1
?- nn1(M3), M2 is M3+1,
M1 is M2+1, 3 is M1+1.
?- M2 is 0+1, M1 is M2+1,
3 is M1+1.
?- M1 is 1+1, 3 is M1+1.
?- 3 is 2+1.
yes
?- nn4(3).
?- M is 3-1,
nn4(M).
?- nn4(2).
?- M is 2-1,
nn4(M).
?- nn4(1).
?- M is 1-1,
nn4(M).
?- nn4(0).
yes
Computing ‘nn1(N)’ will take
N(N − 1)/2 additional steps
compared to ‘nn4(N)’
Factorial revisited
Non tail-recursive version
factorial(0, 1).
factorial(N, FN) :-
N > 0,
M is N-1,
factorial(M, FM),
FN is N*FM.
How to make factorial
tail-recursive?
Hint:
How would you code factorial
in an imperative language?
C/C++ version
int factorial(int n) {
int x = 1;
while(n > 0) {
x *= n;
–n;
}
return x;
}
Factorial revisited
Solution: use an accumulator!
Tail-recursive version
factorial(N, FN) :-
trf(N, 1, FN).A
trf(0, Acc, Res) :-
Res is Acc.A
trf(N, Acc, Res) :-
N > 0,A
NewAcc is Acc * N,A
M is N-1,A
trf(M, NewAcc, Res).A }
int acc = 1;
return acc;
while(n > 0) {
acc *= n;
–n;
Factorial revisited
Tail-recursive version
factorial(N, FN) :-
trf(N, 1, FN).
trf(0, Acc, Res) :-
Res is Acc.
trf(N, Acc, Res) :-
N > 0,
M is N-1,
NewAcc is Acc * N,
trf(M, NewAcc, Res).
?- factorial(4, F).
?- trf(4, 1, F).
?- 4 > 0,
M is 4-1,
NewAcc is 1*4,
trf(M, NewAcc, F).
?- trf(3, 4, F).
?- trf(2, 12, F).
?- trf(1, 24, F).
?- trf(0, 24, F).
F = 24
Summary
Do not forget the base case.
Think about how you will use your predicate
(and in particular, which arguments will be ground).
The order of the rules, the calls in the rules and the calls in the query are
extremely important (both for recursive and non-recursive procedures):
try to design tail-recursive programs.
Use trace to see how your predicate is working.
Declarative vs. Procedural Meaning
Consider the rule ‘A :- B, C.’
Declarative meaning (logical interpretation):
A← B ∧ C , i.e. A is true if B is true and C is true.
Procedural Meaning (how Prolog interprets the rule):
to prove A, prove B and then prove C (order matters!).
Consider the rules ‘A :- B. A :- C.’
Declarative meaning: A← B ∨ C
Procedural meaning: to prove A, prove B . If B does not hold, then to
prove A, prove C (again, order matters).
Example: ‘p :- p.’
Declarative meaning: p ← p (tautology)
Procedural meaning: to prove p, prove p… In�nite loop!
Declarative vs. Procedural Meaning
Consider the program P and the query Q
Prolog Logic
Q ground
yes. P � Q
no. P 2 Q
Q contains
variables
θ (Prolog outputs
a valid substitution)
P � ∀X1, . . . ,Xk(Qθ)
no. ∀θ,P 2 ∀X1, . . . ,Xk(Qθ)