Giáo trình Lập trình nâng cao trên ngôn ngữ Pascal - Chương 5: Giải thuật đệ quy

ng tính ñệ quy: 
Ví dụ 5.2 
Program Tinh_GT; 
Uses crt; 
Var i,n:byte; gt:longint; 
Begin 
 Clrscr; 
 Write(' Nhap gia tri n '); Readln(n); 
 if (n = 0) or (n=1) then gt:=1; 
 if n > 1 then gt:=1; 
 For i:= 1 to n do gt:=gt*i; 
 Writeln('Giai thua cua ',n,' = ',gt); 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 136 
 Readln; 
 End. 
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 
toán như sau: 
Có n chiếc ñĩa tròn ñường kính khác nhau, các ñĩa có lỗ ở giữa. Người ta xếp lồng các 
ñĩa này vào một cọc theo thứ tự trên nhỏ dưới to. Yêu cầu phải xếp các ñĩa này sang cọc mới 
theo nguyên tắc: 
1. Mỗi lần chỉ ñược chuyển 1 ñĩa 
2. Không ñược ñể xảy ra tình trạng ñĩa to ở trên, ñĩa nhỏ ở dưới dù là tạm thời 
3. ðược phép dùng một cọc trung gian 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 137 
Giả sử cọc ñầu tiên là cọc A, cọc trung gian là B và cọc cần xếp ñĩa sang là cọc C. 
Chúng ta sẽ xét một số trường hợp ñơn giản ñể tìm quy luật (Hình 5.2) 
* n =1: cọc A chỉ có một ñĩa 
Chuyển ñĩa từ cọc A sang cọc C 
Kết thúc 
 A B C 
Hình 5.2 
* n = 2: cọc A có 2 ñĩa (Hình 5.3) 
Chuyển ñĩa trên sang B 
Chuyển ñĩa dưới sang C 
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 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 138 
 A B C 
 Hình 5.4 
Việc chuyển 2 ñĩa từ A sang B chúng ta ñã có lời giải ( trường hợp n = 2 ) 
Tóm lại với bài toán n ñĩa chúng ta có lời giải tổng quát là: 
- Chuyển n-1 ñĩa trên cùng từ A sang B 
- Chuyển ñĩa dưới cùng từ A sang C 
- Chuyển n-1 ñĩa từ B sang C 
- Kết thúc 
Việc chuyển n-1 ñĩa từ A sang B lại dẫn tới bài toán giống như chuyển n ñĩa, song số 
lượng ñĩa ñã giảm ñi 1, nghĩa là: 
- Chuyển n-2 ñĩa từ A sang B 
- Chuyển ñĩa thứ n-1 từ A sang C 
- Chuyển n-2 ñĩa từ B sang C 
- Kết thúc 
Quá trình sẽ dẫn tới lúc trên cọc A chỉ còn ñĩa thứ n trên cọc B có n-1 ñĩa và trên cọc C 
không có ñĩa nào, ñến ñây ta chuyển ñĩa thứ n từ A sang C. Bài toán sẽ ñươc thu nhỏ lại với 
việc chuyển n-2 ñĩa từ B sang A. 
Số lần thực hiện các bước chuyển với n = 3 ñược cho trong bảng 5.1, ở ñây chúng ta ñã 
quy ước ñĩa trên cùng là ñĩa số 1, ñĩa giữa là ñĩa số 2 và ñĩa dưới cùng là ñĩa số 3. Dãy số 
trong các cọc luôn luôn sắp xếp theo chiều tăng dần chứng tỏ rằng ñĩa nhỏ luôn ở trên, ñĩa to 
luôn ở dưới. 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 139 
 Bảng 5.1 
Bước ý nghĩa Cọc A Cọc B Cọc C 
0 1,2,3 
1 2,3 1 
2 3 2 1 
3 
Chuyển hai ñĩa trên cùng từ A 
sang B 
3 1,2 
4 Chuyển ñĩa số 3 từ A sang C 1,2 3 
5 1 2 3 
6 1 2,3 
7 
Chuyển 2 ñĩa từ B sang C 
 1,2,3 
Các ví dụ trên cho thấy số lần chuyển tăng rất nhanh khi số ñĩa tăng tuyến tính, với n= 
1 số lần chuyển là 1, với n = 2 số lần chuyển là 3, với n = 3 số lần chuyển là 7. 
 Bảng 5.2 
Bước ý nghĩa Cọc A Cọc B Cọc C 
0 1,2,3,4 
1 2,3,4 1 
2 3,4 1 2 
3 3,4 1,2 
4 4 3 1,2 
5 1,4 3 2 
6 1,4 2,3 
7 
Chuyển 3 ñĩa trên cùng từ cọc 
A sang cọc trung gian B 
4 1,2,3 
8 Chuyển ñĩa 4 từ A sang C 1,2,3 4 
9 2,3 1,4 
10 2 3 1,4 
11 
Chuyển 2 ñĩa trên cùng từ B 
sang A 1,2 3 4 
12 Chuyển ñĩa 3 từ B sang C 1,2 3,4 
13 2 1 3,4 
14 1 2,3,4 
15 
Chuyển 2 ñĩa 1 và 2 từ A 
sang C 
 1,2,3,4 
Có thể dễ dàng tìm ra công thức truy hồi ñể tính số lần chuyển ñĩa 
Nếu số ñĩa là n thì số lần chuyển là 2n - 1 
Với n = 4 số lần chuyển sẽ là 15 (bảng 5.2). 
Nếu trên cọc có 32 ñĩa thì số lần chuyển ñã là hơn 4 tỷ, còn nếu số ñĩa là 64 theo như 
bài toán cổ về tháp Hanoi thì số lần chuyển sẽ là: 36893488147000000000 lần 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 140 
Giả sử chúng ta cho rằng mỗi lần chuyển một ñĩa hết 1 giây thì ñể chuyển hết số ñĩa 
nói trên từ cọc A sang cọc C chúng ta cần 1 169 884 834 700 năm. ðây là khoảng thời gian 
mà bản thân hệ mặt trời và dải ngân hà cũng khó có thể tồn tại. 
2. Thiết kế giải thuật ñệ quy - Khử ñệ quy 
Với một bài toán toán bất kỳ, ñể xem nó có tính ñệ quy hay không chúng ta phải trả 
lời ñược các câu hỏi sau ñây: 
2.1 Bài toán ñã cho có thể ñược ñịnh nghĩa dưới một dạng giống hệt như nó nhưng có 
kích thước nhỏ hơn hay không? 
2.2 Quá trình thu nhỏ bài toán có dẫn tới một ñiểm dừng nào ñó hay không? Nói cách 
khác bài toán thu nhỏ có dẫn tới một trường hợp ñặc biệt mà ta gọi là trường hợp xuy biến 
nghiã là biết lời giải hay không? 
Với bài toán giai thừa trường hợp xuy biến là 0! = 1 
Với bài toán Tháp Hanoi trường hợp xuy biến là khi chỉ có 1 ñĩa trên cọc A. 
2.3 Khi xử dụng tính ñệ quy mỗi lần thu nhỏ bài toán kích thước bài toán giảm ñi như 
thế nào? 
Các ví dụ về ñệ quy có thể xem trong nhiều tài liệu về lập trình, vấn ñề chúng ta quan 
tâm ở ñây là khi một bài toán có thể giải quyết bằng cả ñệ quy và cách thông thường thì nên 
dùng cách nào? 
Với bài toán tính giai thừa sử dụng vòng lặp For... việc lập trình rất ñơn giản, còn 
dùng ñệ quy sẽ phức tạp hơn. Với bài toán tìm ước số chung lớn nhất rõ ràng là cách dùng ñệ 
quy sẽ ñơn giản hơn các cách khác. Với bài toán Tháp Hanoi nếu không dùng ñệ quy chúng ta 
khó mà tìm ra một thuật giải nào trong sáng hơn. Nói như vậy cũng có nghĩa là không có một 
chuẩn mực nào chung cho mọi bài toán. Kinh nghiệm của các nhà lập trình ñã chỉ ra rằng nếu 
một bài toán vừa có thể giải bằng ñệ quy, vừa có thể giải bằng phương pháp lặp thông thường 
thì nên tránh dùng ñệ quy. 
Một bài toán có thể thay thế giải thuật ñệ quy bằng các giải thuật không tự gọi ñến 
chúng thì gọi là khử ñệ quy. 
Ví dụ với bài toán tính giai thừa chúng ta hoàn toàn có thể giải bằng cách dùng vòng 
lặp For . Bài toán trong trường hợp này ñơn giản hơn cả về thuật toán lẫn kỹ thuật lập trình. 
3. Hiệu lực của bài toán ñệ quy 
Như ñã nêu ñệ quy là một trong các công cụ ñể lập trình giải các bài toán. Cần khẳng 
ñịnh rằng ñệ quy chỉ ñược dùng cho một số bài toán mà chúng ta tìm ñược giải thuật ñệ quy. 
Trở lại ví dụ 4.16 về xây dựng cây nhị phân. Nếu cây mà mỗi nút cha có nhiều nhất hai nút 
con nhưng không quy ñịnh rõ con bên trái và con bên phải bố trí thế nào thì chúng ta không 
thể dùng ñược tính ñệ quy. Trong trường hợp quy ñịnh rõ giá trị ở con bên trái luôn nhỏ hơn 
giá trị ở nút cha còn ở con bên phải là lớn hơn nút cha thì chúng ta thấy việc khảo sát một cây 
nhị phân tổng quát có thể xuy về việc khảo sát riêng từng cây con bên trái và cây con bên 
phải. Chương trình con Taocay trong ví dụ 4.16 ñã sử dụng tính ñệ quy ñể bổ xung dữ liệu 
vào các nút, với cách viết này chương trình Taocay không ñơn giản hơn cách viết dùng vòng 
lặp. Tuy nhiên khi duyệt cây với các chương trình con Quet_trung_tam, Quet_truoc, Quet_sau 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 141 
thì tính ñệ quy ñã làm cho chương trình trở nên trong sáng và rất dễ hình dung là cây ñược 
quét như thế nao. 
Tính ñệ quy về một khía cạnh nào ñó có thể xem như tính quy nạp toán học, tuy nhiên 
cần phân biệt rằng ñệ quy ñược thực hiện là nhờ các bộ nhớ kiểu LIFO hoặc FIFO còn quy 
nạp toán học thuần tuý chỉ là lý thuyết. Việc sử dụng quy nạp toán học ñể chứng minh tính 
ñúng ñắn của giải thuật ñệ quy ñã ñược một vài tác giả thực hiện, ñiều này chỉ chứng minh 
tính ñúng ñắn của giải thuật ñệ quy chứ không cho biết giải thuật ấy hiệu quả như thế nào. 
Vấn ñề là người lập trình phải tự xác ñịnh xem thuật giải nào tiêu tốn ít công sức của người 
lập trình và tài nguyên trong máy nhất. 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 142 
Bài tập chương 5 
1. Dãy số Fibonaci a1, a2, .... an ñược ñịnh nghĩa như sau: 
a1 = a2 = 1 
a3 = a2 + a1 
.................... 
an = an-1 + an-2 
Lập chương trình với việc áp dụng tính ñệ quy ñể xây dựng dãy số Fibonaci, giá trị n 
nhập từ bàn phím. 
2. Lập chương trình giải bài toán Tháp Hanoi 
3. Hàm F(x,y) ñược ñịnh nghĩa như sau: 
 nếu x = 0 
F(x,y) = nếu y = 0 
 với các trường hợp còn lại 
Lập chương trình có dùng ñệ quy ñể tính hàm F với giá trị x,y nhập từ bàn phím. 
4. S là một chuỗi ký tự có ñộ dài tối ña là 255. Lập chương trình nhập S từ bàn phím 
sau ñó in ra chuỗi ngược của chuỗi ban ñầu. Chương trình có dùng ñệ quy 
Ví dụ: S = ‘Chuc mung ngay 8/3’ 
In ra ‘3/8 yagn gnum cuhC’ 
5. Cho dãy số a1, a2, ..... , an . Gọi số hoán vị của dãy số là k. 
Lập một chương trình hiện lên số hoán vị của dãy số và giá trị cụ thể của từng hoán vị 
Ví dụ: dãy số 1 3 2 
In ra: Số hoán vị = 6 
 Giá trị cụ thể 1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1 





−−
−
+
))1,(,1(
)1,1(
1
yxFxF
xF
y