程序代写代做代考 c++ c/c++ prolog Programming in Prolog – Recursion

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 0 and n = 0
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θ)