Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................-
133
Chương 5

Giải thuật ñệ quy

Nội dung của chương này ñề cập ñến những bài toán có tính ñệ quy. Không phải bài
toán nào cũng có tính ñệ quy và không phải các bài toán có tính ñệ quy thì ñều phải giải bằng
giải thuật ñệ quy. Các vấn ñề cần quan tâm trong chương này:
 Bài toán có tính ñệ quy không
 Có cần dùng giải thuật ñệ quy không
 ðệ quy có mang lại hiệu quả hơn các phương pháp thông thường hay không

Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................-
134

1. Khái niệm ñệ quy

Trong thân một chương trình con có thể ñưa lời gọi tới chính chương trình con ñó, tính
chất này ñược gọi là tính "ðệ qui của chương trình con".
Trong toán học khái niệm giai thừa ñược ñịnh nghĩa như sau:
0! = 1

1.3) những gì gửi vào cuối cùng thì ñược lấy ra trước tiên. Bóc ô nhớ trên ñỉnh ta có 1! = 1 và
lộ ra ô tiếp theo 2! = 2*1!. Vì 1! ñã biết nên tính ñược 2! = 2, bóc tiếp ô nhớ phía dưới ta có
3! = 3*2!, vì 2! ñã biết nên 3! = 3*2 = 6 quá trình tiếp tục cho ñến khi bóc ô nhớ dưới cùng và
chúng ta nhận ñược 5! = 120. Dưới ñây là chương trình tính giai thừa

5! = 5*4!
4! = 4*3!
3! = 3*2!
2! = 2*1!
1! = 1

Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................-
135

Ví dụ 5.1:
Program Giaithua;
Uses crt;
Var n: integer;
Function GT(m: integr): integer; (* Hàm GT tính giai thừa của n*)
Begin
if m=0 then GT:=1 else GT:= m*GT(m-1); (*Gọi ñệ qui của GT *)
End;
Begin
Clrscr;
write ('Tinh giai thua cua n = '); Readln (n) (*ðọc giá trị n*)
write('Gia thua cua ',n, ' = ',GT(n)); (* Viết giá trị hàm GT *)
Repeat until keypressed;
End.

Ví dụ 5.1 có một số ñiều ñáng lưu ý sau ñây:


Ví dụ 5.3: Lập chương trình tìm ước số chung lớn nhất của hai số nguyên n, m.
Ước số chung lớn nhất của hai số n và m tính theo công thức :
n nếu m = 0
USC(n,m) =
USC(m, n mod m ) nếu m <> 0

Ví dụ n= 4, m=8
USC(4,8) = USC(8, 4) = USC(4,0) = 4
Chương trình ñược xây dụng như sau:

Program timUSC ;
Uses crt;
Var n,m : word; Lam: Char;
FUNCTION USC(a,b:word): word;
Begin
If b=0 then USC := a Else USC := USC(b,a mod b);
End;
BEGIN
Repeat
Clrscr;
Write(' Hay cho hai so "n" va "m" can tim uoc so chung ');
Readln(n,m);
Writeln(' Uoc so chung lon nhat cua ',n,' va ',m, ' la ',USC(n,m):5);
Writeln;
Write('Tim tiep hay thoi ? C/K '); read(lam);
Until Upcase(lam)='K';
END.

Bài toán kinh ñiển ứng dụng giải thuật ñệ quy là bài toán Tháp Hanoi. Nội dung bài

Chuyển ñĩa từ B sang C
Kết thúc
A B C C

Hình 5.3
* n = 3: cọc A có 3 ñĩa
Với trường hợp 3 ñĩa nếu chúng ta coi 2 ñĩa trên là một ñĩa thì bài toán quy về trường
hợp n = 2, khi ñó lời giải sẽ là: (Hình 5.4)
Chuyển 2 ñĩa trên sang B
Chuyển ñĩa dưới cùng sang C
Chuyển 2 ñĩa từ B sang C
Kết thúc