Prolog101(05)

递归定义都包括两个部分:边界条件与递归部分。
边界条件定义最简单的情况。而递归部分,则首先解决一部分问题,然后再调用其自身来解决剩下的部分,
每一次都将进行边界检测,如果剩下的部分已经是边界条件中所定义的情况时,那么递归就圆满成功了。

递归解决阶乘问题

%swipl -s factorial.pl
%Hansen

fun(N):- N>0,fact(N,1).
fun(N):- write(N), write(' is smaller than 1. '),fail.

fact(1,M):- write(M),!.
fact(N,M):- N1 is N-1, M1 is M*N, fact(N1,M1).
 1 ?- fun(0).
0 is smaller than 1. 
false.

 2 ?- fun(1).
1
true .

 3 ?- fun(2).
2
true .

 4 ?- fun(3).
6
true .

 5 ?- fun(4).
24
true .

 6 ?- fun(5).
120
true .

 7 ?- fun(6).
720
true .

递归解决汉诺塔问题

%swipl -s hanoi.pl
%Hansen

%N个盘子从A到C的问题,用递归解决的思路:
%N-1个盘子,从A到B
%1个盘子,从A到C
%N-1个盘子,从B到C

hanoi(N):-move(N,a,b,c).
move(1,A,_,C):-fromto(A,C),!.
move(N,A,B,C):-N1 is N-1,move(N1,A,C,B),fromto(A,C),move(N1,B,A,C).
fromto(Loc1,Loc2):-nl,write('move one disk from '),write(Loc1),write(' to '),write(Loc2).

执行查询:

 1 ?- hanoi(1).

move one disk from a to c
true.

 2 ?- hanoi(2).

move one disk from a to b
move one disk from a to c
move one disk from b to c
true.

 3 ?- hanoi(3).

move one disk from a to c
move one disk from a to b
move one disk from c to b
move one disk from a to c
move one disk from b to a
move one disk from b to c
move one disk from a to c
true.

%这里就会出错啦
 4 ?- hanoi(0).
ERROR: Out of local stack

Leave a Reply

Your email address will not be published. Required fields are marked *

*