IV. Đệ qui 1. Khái niệm -
Một hàm được gọi là đệ quy nếu bên trong thân hàm có lệnh gọi đến chính nó. Khi hàm gọi đệ qui đến chính nó, thì mỗi lần gọi máy sẽ tạo ra một tập các biến cục bộ mới hoàn toàn độc lập với tập các biến cục bộ đã được tạo ra trong các lần gọi trước.
Để minh hoạ chi tiết những điều trên, ta xét một ví dụ về tính giai thừa của số nguyên dương n. Theo định nghĩa giai thừa của một số nguyên n được ký hiệu là n! và được tính như sau:
-
n!=1* 2 * 3 *…* (n-1) *n = (n-1)! *n (với 0!=1)
-
Như vậy, để tính n! ta thấy nếu n=0 thì n!=1 ngược lại thì n!=n * (n-1)!
-
Ví dụ 4.19: Để minh hoạ chi tiết những điều trên, ta xét một ví dụ về tính giai thừa của số nguyên dương n. Khi không dùng phương pháp đệ qui hàm có thể được viết như sau :
long int gt1(int n) /* Tính n! v?i n>=0*/
{
long int gtphu=1;
int i;
for (i=1;i<=n;++i)
gtphu*=i;
return gtphu;
}
-
Hàm tính n! theo phương pháp đệ qui có thể được viết như sau :
long int gt2(int n)
{
if (n==0 || n==1)
return 1;
else
return(n*gt2(n-1));
}
-
Và lời gọi hàm gt từ chương trình chính được thực hiện như sau:
int main()
{
//printf("\n 3!=%d",gt1(3));
printf("\n 3!=%d",gt2(3));
getch();
return 0;
}
-
Lần gọi đầu tiên tới hàm gt2 được thực hiện từ hàm main(). Máy sẽ tạo ra một tập các biến tự động của hàm gt2. Tập này chỉ gồm các đối n. Ta gọi đối n được tạo ra lần thứ nhất là n thứ nhất. Giá trị của tham số thực ( số 3 ) được gán cho n thứ nhất. Lúc này biến n trong thân hàm được xem là n thứ nhất. Do n thứ nhất có giá trị bằng 3 nên điều kiện trong toán tử if là sai và do đó máy sẽ lựa chọn câu lệnh else. Theo câu lệnh này, máy sẽ tính giá trị biểu thức: n*gt2(n-1) (*). Để tính biểu thức trên, máy cần gọi chính hàm gt2 vì thế lần gọi thứ hai sẽ thực hiện. Máy sẽ tạo ra đối n mới, ta gọi đó là n thứ hai. Giá trị của n-1 ở đây lại là đối của hàm , được truyền cho hàm và hiểu là n thứ hai, do vậy n thứ hai có giá trị là 2. Bây giờ, do n thứ hai vẫn chưa thoả mãn điều kiện if nên máy lại tiếp tục tính biểu thức : n*gt2(n-1) (**). Biểu thức trên lại gọi hàm gt2 lần thứ ba. Máy lại tạo ra đối n lần thứ ba và ở đây n thứ ba có giá trị bằng 1. Đối n=1 thứ ba lại được truyền cho hàm, lúc này điều kiện trong lệnh if được thoả mãn, máy đi thực hiện câu lệnh: return 1=gt2(1) (***). Bắt đầu từ đây, máy sẽ thực hiện ba lần ra khỏi hàm gt2. Lần ra khỏi hàm thứ nhất ứng với lần vào thứ ba. Kết quả là đối n thứ ba được giải phóng, hàm gt2(1) cho giá trị là 1 và máy trở về xét giá trị biểu thức
n*gt2(1) đây là kết quả của (**) ở đây, n là n thứ hai và có giá trị bằng 2. Theo câu lệnh return, máy sẽ thực hiện lần ra khỏi hàm lần thứ hai, đối n thứ hai sẽ được giải phóng, kết quả là biểu thức trong (**) có giá trị là 2.1. Sau đó máy trở về biểu thức (*) lúc này là: n*gt2(2)=n*2*1 n lại hiểu là thứ nhất, nó có giá trị bằng 3, do vậy giá trị của biểu thức trong (*) là 3.2.1=6. Chính giá trị này được sử dụng trong câu lệnh printf của hàm main() nên kết quả in ra trên màn hình là: 3!=6.
-
Từ ví dụ trên ta thấy hàm đệ qui có đặc điểm:
-
Chương trình viết rất gọn,
-
Việc thực hiện gọi đi gọi lại hàm rất nhiều lần phụ thuộc vào độ lớn của đầu vào. Chẳng hạn trong ví dụ trên hàm được gọi n lần, mỗi lần như vậy chương trình sẽ mất thời gian để lưu giữ các thông tin của hàm gọi trước khi chuyển điều khiển đến thực hiện hàm được gọi. Mặt khác các thông tin này được lưu trữ nhiều lần trong ngăn xếp sẽ dẫn đến tràn ngăn xếp nếu n lớn.
-
Hàm đệ qui so với hàm có thể dùng vòng lặp thì đơn giản hơn, tuy nhiên với máy tính khi dùng hàm đệ qui sẽ dùng nhiều bộ nhớ trên ngăn xếp và có thể dẫn đến tràn ngăn xếp. Vì vậy khi gặp một bài toán mà có thể có cách giải lặp ( không dùng đệ qui ) thì ta nên dùng cách lặp này. Song vẫn tồn tại những bài toán chỉ có thể giải bằng đệ qui.
2. Lớp các bài toán giải được bằng đệ qui -
Phương pháp đệ qui thường được dùng để giải các bài toán có đặc điểm:
-
Giải quyết được dễ dàng trong các trường hợp riêng gọi là trường hợp suy biến hay cơ sở, trong trường hợp này hàm được tính bình thường mà không cần gọi lại chính nó;
-
Đối với trường hợp tổng quát, bài toán có thể giải được bằng bài toán cùng dạng nhưng với tham đối khác có kích thước nhỏ hơn tham đối ban đầu. Và sau một số bước hữu hạn biến đổi cùng dạng, bài toán đưa được về trường hợp suy biến.
-
Như vậy trong trường hợp tính n! nếu n = 0 hàm cho ngay giá trị 1 mà không cần phải gọi lại chính nó, đây chính là trường hợp suy biến. Trường hợp n > 0 hàm sẽ gọi lại chính nó nhưng với n giảm 1 đơn vị. Việc gọi này được lặp lại cho đến khi n = 0.
-
Một lớp rất rộng của bài toán dạng này là các bài toán có thể định nghĩa được dưới dạng đệ qui như các bài toán lặp với số bước hữu hạn biết trước, các bài toán UCLN, tháp Hà Nội, ...
-
Cấu trúc chung của hàm đệ qui
-
Dạng thức chung của một chương trình đệ qui thường như sau:
if (trường hợp suy biến)
{
trình bày cách giải // giả định đã có cách giải
}
else // trường hợp tổng quát
{
gọi lại hàm với tham đối "bé" hơn
}
3. Các ví dụ -
Bài toán tìm ước số chung lớn nhất (UCLN): Cho hai số nguyêna và b, tìm USCLN của hai số theo giải thuật đệ qui. Bài toán có thể được định nghĩa dưới dạng đệ qui như sau:
-
Nếu b = 0 thì UCLN = a;
-
Nếu b<>0 thì UCLN(a, b) = UCLN(b, a mod b).
-
Từ đó ta có hàm đệ qui để tính UCLN của a và b như sau.
-
Ví dụ 4.20:
int USCLN(int a, int b)
{
if (b==0)
return a;
else
return USCLN(b,a%b);
}
-
Số Fibinaci: Tính số hạng thứ n của dãy Fibonaci với giải thuật đệ qui. Dãy Fibonaci được định nghĩa như sau:
-
f(0) = f(1) = 1;
-
f(n) = f(n-1) + f(n-2) với n >=2.
Ví dụ 4.21:
long Fib(int n)
{
long kq;
if (n==0 || n==1) kq = 1;
else kq = Fib(n-1) + Fib(n-2);
return kq;
}
-
Bài toán tháp Hà nội: Có n đĩa với kích thước to, nhỏ khác nhau. Ban đầu sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Người chơi phải di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau:
-
Một lần chỉ được di chuyển một đĩa;
-
Một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất).
-
Hình ảnh mô tả bài toán được cho như hình 4.2.
Hình 4.2 - Bài toán tháp Hanoi
-
Đặt tên các cọc là A, B, C và qui ước A là Cọc Nguồn, B là Cọc Đích và C là Cọc Trung Gian;
-
Gọi n là tổng số đĩa;
-
Đánh số đĩa từ 1 (nhỏ nhất, trên cùng) đến n (lớn nhất, dưới cùng).
-
Thuật giải đệ qui: Để chuyển n đĩa từ cọc A sang cọc B với C là cọc trung gian:
-
Chuyển n-1 đĩa từ A sang C. Chỉ còn lại đĩa #n trên cọc A;
-
Chuyển đĩa #n từ A sang B;
-
Chuyển n-1 đĩa từ C sang B cho chúng nằm trên đĩa #n
#include
#include
void chuyen(int sodia, char CotNguon, char CotDich, char CotTG)
{
if (sodia>0)
{
chuyen(sodia-1, CotNguon, CotTG, CotDich);
printf(" Chuyen dia %d Tu %c -> %c\n",sodia,CotNguon,CotDich);
chuyen(sodia-1, CotTG, CotDich, CotNguon);
}
}
int main()
{
char CotNguon,CotDich,CotTG;
int n;
printf("\n Hay nhap so dia: ");
scanf("%d",&n);
chuyen(n,'A','B','C');
getch();
}
-
Kết quả thực hiện ví dụ 4.22 được cho như hình 4.3.
-
Hình 4.3 - Kết quả thực hiện bài toán tháp Hà nội với n=4
Chia sẻ với bạn bè của bạn: |
