Giáo trình Cấu trúc dữ liệu và Giải thuật - Chương 2: Giải thuật đệ quy - Đỗ Tuấn Anh

 Factorial(n-1);
}
Phải làm cho bài toán đơn giản hơn:
long Factorial(long n){
if (n==0)
return 1;
else
return n * Factorial(n+1);
}
Oops!
Không có điểm
dừng
Oops!
Dãy số Fibonacci
zDãy số Fibonacci:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 
trong đó mỗi số là tổng của 2 số đứng
trước nó.
zĐịnh nghĩa theo đệ quy:
{F(0) = 0;
{F(1) = 1;
{F(n) = F(n-1)+ F(n-2);
Dãy số Fibonacci – Thủ tục đệ quy
//Tính số Fibonacci sử dụng hàm đệ quy.
int fib(int number)
{
if (number == 0) return 0;
if (number == 1) return 1;
return (fib(number-1) + fib(number-2));
}
int main(){
int inp_number;
printf ("Please enter an integer: “);
scanf (“%d”, &inp_number);
int intfib = fib(inp_number);
printf("The Fibonacci number for %d is %d\n“,inp_number,intfib);
return 0;
}
Cơ chế thực hiện
z Tính fibonacci của 4, num=4:
fib(4):
4 == 0 ? Sai; 4 == 1? Sai.
fib(4) = fib(3) + fib(2)
fib(3):
3 == 0 ? Sai; 3 == 1? Sai.
fib(3) = fib(2) + fib(1) 
fib(2):
2 == 0? Sai; 2==1? Sai.
fib(2) = fib(1)+fib(0) 
fib(1):
1== 0 ? Sai; 
1 == 1? Đúng.
fib(1) = 1;
return fib(1);
int fib(int num)
{
if (num == 0) return 0;
if (num == 1) return 1;
return
(fib(num-1)+fib(num-2));
}
Cơ chế thực hiện
fib(0):
0 == 0 ? Đúng.
fib(0) = 0; 
return fib(0);
fib(2) = 1 + 0 = 1;
return fib(2);
fib(3) = 1 + fib(1)
fib(1):
1 == 0 ? Sai; 
1 == 1? Đúng
fib(1) = 1;
return fib(1);
fib(3) = 1 + 1 = 2;
return fib(3)
Cơ chế thực hiện
fib(2):
2 == 0 ? Sai; 2 == 1? Sai.
fib(2) = fib(1) + fib(0)
fib(1):
1== 0 ? Sai; 1 == 1? Đúng.
fib(1) = 1;
return fib(1);
fib(0):
0 == 0 ? Đúng.
fib(0) = 0; 
return fib(0);
fib(2) = 1 + 0 = 1;
return fib(2); 
fib(4) = fib(3) + fib(2) 
= 2 + 1 = 3;
return fib(4);
Thủ tục đệ quy tổng quát
int Hàm_đệ_quy(DS tham số){
if(thỏa mãn điều kiện dừng)
return giá_trị_dừng_tương_ứng;
// other stopping conditions if needed
return hàm_đệ_quy(tham số suy giảm) 
} 
Bài toán tháp Hà Nội
Ban đầu: Cột 1
Kết thúc:
Cột 2 Cột 3
Cột 1 Cột 2 Cột 3
Quy tắc: đĩa lớn hơn không được đặt trên đĩa nhỏ hơn trong quá trình
chuyển đĩa
Giải thuật đệ quy
1. Chuyển n – 1 đĩa từ cột 1 sang cột 2
2. Chuyển đĩa dưới cùng từ cột 1 sang 3
3. Chuyển n-1 đĩa từ cột 2 sang cột 3
1 2 3
1 2 3
21 3
Thủ tục đệ quy
// chuyển n đĩa từ cột nguồn sang cột đích
// sử dụng một đĩa trung gian
void hanoi (int n, int cot1, int cot3, int cot2)
{
if (n > 0) 
{
hanoi(n-1, cot1, cot2, cot3); 
Chuyen_dia(n, cot1, cot3); 
hanoi(n-1, cot2, cot3, cot1); 
}
}
Cơ chế thực hiện
hanoi(2, 1, 3, 2)
hanoi(1, 1, 2, 3)
hanoi(0, 1, 3, 2)
“Chuyển đĩa 1 từ cột 1 sang cột 2”
hanoi(0, 3, 2, 1)
“Chuyển đĩa 2 từ cột 1 sang cột 3”
hanoi(1, 2, 3, 1)
hanoi(0, 2, 1, 3)
“Chuyển đĩa 1 từ cột 2 sang cột 3”
hanoi(0, 3, 1, 2)
hanoi(n, cot1, cot3, cot2)
Cây đệ quy trong trường hợp
chuyển 3 đĩa
hanoi(3, 1, 3, 2)
hanoi(2, 1, 2, 3)
hanoi(1, 1, 3, 2)
hanoi(0,1,2,3)
hanoi(0,2,3,1)
hanoi(1,3,2,1)
hanoi(0,3,1,2)
hanoi(2,2,3,1)
hanoi(1,2,1,3)
hanoi(0,2,3,1) hanoi(0,1,2,3)
hanoi(1,1,3,2)
hanoi(0,1,2,3) hanoi(0,3,1,2) hanoi(0,2,3,1)
4. Hiệu quả của giải thuật đệ quy
z Nhược điểm: 
{ Tốn không gian nhớ
{ Tốc độ chậm
z Ưu điểm: đơn giản, ngắn gọn, dễ viết code
{ Một số giải thuật đệ quy cũng có hiệu lực cao, ví dụ
như Quick sort
z Mọi giải thuật đệ quy đều có thể thay thế bằng
một giải thuật không đệ quy (sử dụng vòng lặp)
Gọi hàm và Bộ nhớ Stack
Runtime stack: khi hàm được gọi, một vùng nhớ trên stack 
được sử dụng để lưu trữ: các tham số, địa chỉ trở về của hàm
Biến địa
phương
Địa chỉ
trở về
Các tham số
Activation
Record 
Activation Frame
Đệ quy và Stack
M M
A
M
A
B
M
A
M
A
C
M
A
C
D
M
A
C
M
A
Stack
được
cấp
phát
cho dữ
liệu
Thời gian
Các cột theo chiều dọc chỉ ra nội dung của stack tại một thời điểm, và sự thay đổi
của stack khi gọi hàm và thoát khỏi hàm
M M
D
M
D
D
M
D
D
D
M
D
D
M
D
M
Cây lời gọi hàm
D
A
M
B C D
D
D
Cây gọi hàm tương
đương
Bắt đầu Kết thúc
Đệ quy là trường hợp khi:
• Một hàm gọi chính nó, hoặc
• Một hàm gọi một chuỗi các hàm khác trong đó một/ một vài
trong số chúng gọi lại hàm đầu tiên
Gọi hàm và địa chỉ trở về
F()
F(<DS tham số
hình thức>)
long Factorial (long n)
{
int temp; 
if (n == 0)
return 1;// giải phóng activation record
else
{ // đẩy activation record của
// lời gọi Factorial(n-1)
temp = n * Factorial (n-1); 
return temp; // giải phóng activation 
// record
}
}
void main ( )
{ 
int n; 
// đẩy activation record của Factorial(4)
// vào Stack
n = Factorial(4); 
} RecLoc1
RecLoc2
Factorial(4) và Stack 
4 RecLoc1
1 RecLoc2Factorial(1)
0 RecLoc2Factorial(0)
2 RecLoc2Factorial(2)
3 RecLoc2Factorial(3)
Factorial(4)
tham_số địa_chỉ_trả_về Lệnh trước khi trả về
temp = 1 * 1; // 1 từ Factorial (0)
return temp; 
temp = 2 * 1; // 1 từ Factorial(1)
return temp; 
temp = 3 * 2; // 2 từ Factorial(2)
return temp; 
temp = 4 * 6; // 6 từ Factorial(3)
return temp; 
N = Factorial(4); // quay lại main
Khử đệ quy
z Hàm tính giai thừa không đệ quy
// Sử dụng vòng lặp
long Factorial (long n)
{ 
long prod = 1; // 0! = 1
// tính tích = 1*2*  * n
for (i = 1; i < n+1; i++)
prod * = i; 
return prod; 
}
Hàm tính Fibonacci không đệ quy
//Tính số Fibonacci sử dụng vòng lặp
//hiệu quả hơn nhiều so với dùng đệ quy
int fib(int n)
{
int f[n+1]; 
f[0] = 0; f[1] = 1;
for (int i=2; i<= n; i++)
f[i] = f[i-1] + f[i-2];
return f[n];
}
4. Đệ quy và Quy nạp toán học
zChứng minh tính đúng đắn của giải thuật
Factorial
Đánh giá giải thuật Tháp Hà nội
Gọi f(n) là số lần chuyển đĩa cần thiết để chuyển n đĩa từ
cột 1 sang cột 3.
f(1) = 1; 
f(n) = 2 * f(n – 1) + 1, if n > 1
Dự đoán: f(n) = 2 * f(n – 1) + 1
= 22 * f(n – 2) + 2 + 1
= 
= 2n-1 * f(1) +  + 2 + 1
= 2n-1 + 2n-2 +  + 2 + 1
= 2n – 1
Chứng minh?
zChứng minh bằng quy nạp
f(1) = 21 – 1 = 1
Giả sử đúng với n = k
f(k) = 2k – 1
f(k+1) = 2*f(k) +1
= 2*(2k – 1) + 1
= 2k+1 -1 => Công thức đúng
Các nhà sư phải chuyển 64 đĩa. Giả sử mỗi lần chuyển mất 1 
giây, các nhà sư sẽ phải mất 5 * 1011 năm = 25 lần tuổi của vũ
trụ. Khi chuyển xong chồng đĩa thì đã đến ngày tận thế!
11
5. Đệ quy quay lui (back tracking)
z Bài toán 8 con hậu: “Hãy xếp 8 con hậu trên bàn
cờ 8x8 sao cho không có con hậu nào có thể ăn
con hậu nào”
Đệ quy quay lui
z Phương pháp “thử từng bước”
{Thử dự đoán
{Nếu dự đoán là sai, quay trở lại và thử dự đoán khác => 
quay lui
z Dễ dang thể hiện phương pháp quay lui bằng đệ
quy
{Các biến trạng thái của hàm đệ quy được lưu trữ trên
Stack
{Quay lui lại trạng thái ban đầuÙ Quay trở lại hàm
trước đó (hàm gọi hàm hiện tại)
Bài toán 8 con hậu
zGiải thuật 1: 
{Thử lần lượt tất cả các trường hợp ứng với mọi
vị trí của 8 con hậu
{Số phép thử = 64*63**58*57 
= 178,462,987,637,760
Bài toán 8 con hậu
z Nhận xét:
{Mỗi cột phải có 1 con hậu
zCon hậu 1 nằm trên cột 1
z
zCon hậu j nằm trên cột j
z
zCon hậu 8 nằm trên cột 8
{Các con hậu phải không cùng hàng
{Các con hậu phải không nằm trên đường chéo của nhau
Bài toán 8 con hậu
zBài toán: Con hậu thứ j nằm trên cột j
{[1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]
{Lựa chọn hàng cho từng con hậu để mỗi con hậu
không ăn nhau
zGiải thuật:
{Thử lần lượt từng vị trí hàng của con hậu 1 (1-8)
{Với từng vị trí của con hậu 1
zThử lần lượt từng vị trí hàng của con hậu 2
zVới từng vị trí của con hậu 2
• Thử lần lượt từng vị trí hàng của con hậu 3
Giải thuật
function Try (column) {
for (row = 1; row <= 8; row++) {
if ( [row, column] là an toàn) {
Đặt con hậu vào vị trí [row, column];
if (column == 8) 
In kết quả;
else
Try (column + 1);
Xóa con hậu khỏi vị trí [row, column];
}
}
}
Con hậu thứ 8 là an toàn
Xóa để tiếp tục thử vị trí
[row+1, column]
Thử lần lượt từng vị trí hàng
Nếu vị trí thử không bị
con hậu nào tấn công
Đệ quy để với con hậu tiếp
Kiểm tra An toàn
Thiết kế dữ liệu
z int pos[] : lưu vị trí của con hậu
{pos[column] = row Ù có con hậu tại vị trí (row, column)
z bool rowFlag[] : lưu trạng thái của các hàng
{rowFlag[i] = false Ù không có con hậu nào chiếm hàng i
z bool rowPlusCol[] : lưu trạng thái của các đường
chéo x+y (2 ≤ x+y ≤ 16)
{rowPlusCol[x+y] = false Ù không có quân hậu nào chiếm
đường chéo x+y
z bool rowMinusCol[] : lưu trạng thái của các đường
chéo y-x (-7 ≤ y-x ≤ 7)
{rowMinusCol[y-x] = false Ù không có quân hậu nào chiếm
đường chéo y-x
Kiểm tra an toàn của vị trí
[row, column]
zHàng row chưa bị chiếm
{rowFlag [row] == false ?
zĐường chéo row+column chưa bị chiếm
{rowPlusCol [row+column] == false ?
zĐường chéo row-column chưa bị chiếm
{rowMinusCol [row-column] == false ?
Đặt con hậu vào vị trí [row, column]
zLưu vị trí của con hậu
{pos[column] = row
zĐánh dấu hàng row đã bị chiếm
{rowFlag[row] = true
zĐánh dấu đường chéo row+column đã bị
chiếm
{rowPlusCol [row+column] = true
zĐánh dấu đường chéo row-column đã bị
chiếm
{rowMinusCol [row-column] = true
Xóa con hậu khỏi vị trí [row, column]
zXóa vị trí của con hậu
{pos[column] = -1
zĐánh dấu lại hàng row chưa bị chiếm
{rowFlag[row] = false
zĐánh dấu lại đường chéo row+column
chưa bị chiếm
{rowPlusCol [row+column] = false
zĐánh dấu lại đường chéo row-column 
chưa bị chiếm
{rowMinusCol [row-column] = false
In kết quả
function PrintSolution(int pos[]) 
{
for (int col=1; col<=8; col++)
printf(“Con hau thu %d nam tai hang 
%d”, col, pos[col] );
}
function Try (int column) {
for (row = 1; row <= 8; row++) {
if (!rowFlag [row] && !rowPlusCol [row+column] &&
!rowMinusCol [row-column] ) {
//Đặt con hậu vào vị trí [row, column]
pos[column] = row;
rowFlag[row] = true;
rowPlusCol [row+column] = true;
rowMinusCol [row-column] = true;
if (column == 8) // con hậu thứ 8 an toàn
PrintSolution(pos);
else
Try (column + 1);
// Xóa con hậu khỏi vị trí [row, column]
pos[column] = -1;
rowFlag[row] = false;
rowPlusCol [row+column] = false;
rowMinusCol [row-column] = false;
}
}