Kỹ thuật đệ quy

(((

Kỹ thuật đệ quy
Đệ quy là một thuật toán dùng để đơn giản hóa những bài toán phức tạp bằng cách phân nhỏ phép toán đó thành nhiều phần đồng dạng. Qua việc giải những bài toán được phân nhỏ này, những lời giải sẽ được kết hợp lại để giải quyết bài toán lớn hơn.
Một số các ví dụ đệ quy
Định nghĩa số tự nhiên
0 là số tự nhiên
N là số tự nhiên n-1 là số tự nhiên
Định nghĩa giai thừa của n
0! là 1
Nếu n>0, n! = n *(n-1)!
Hàm đệ quy : Hàm đệ quy là một hàm trong đó có dùng lời gọi hàm đến chính bản thân nó.
Ví dụ ta có hàm đệ quy như sau:
int Sum(int n)
{
if (n==0)
return 0;
else
return (n+Sum(n-1)); // gọi đệ quy đến chính bản thân hàm sum
}
Khi một hàm đệ quy gọi đến chính nó thì mỗi lần gọi máy sẽ tạo ra tập các biến cục bộ mới hoàn toàn độc lập với biến cục bộ đã tạo ra trong lần gọi trước. Bao nhiêu lần gọi hàm đệ quy thì tương ứng với bấy nhiêu lần thoát ra khỏi hàm, mỗi lần ra khỏi hàm thì tập biến cục bộ bị xóa.
Có một sự tương ứng giữa các lời gọi hàm và lần thoát khỏi hàm theo thứ tự ngược lại: lần ra khỏi hàm đầu tiên tương ứng với lần gọi hàm cuối cùng.
Ví dụ minh họa hàm đệ quy: tính giai thừa của n (tích của các số từ 1 đến n). Ta có định nghĩa của giai thừa n như sau: n! = 1.2.3...(n-1).n
hoặc định nghĩa:
n! =

Phương pháp thứ nhất là dùng vòng lặp:
long GT(int n)
{
long result = 1;
for(int i=1; i <= n; i++)
result *= i;
return result;
}
Phương pháp thứ hai là dùng hàm đệ quy:
long Giaithua(int n)
{
if (n == 0) return 1;
else return (n*Giaithua(n-1));
}
Phân tích chương trình thực hiện đệ quy:
Giả sử chương trình có lời gọi hàm như sau
long l = Giaithua(5);


Hình 2.1: Gọi đệ quy của hàm giai thừa.
Lưu ý: Hàm đệ quy dùng nhiều vùng nhớ trên ngăn xếp do đó có thể dẫn đến tràn ngăn xếp. Do đó nếu một bài toán có thể dùng phương pháp lặp (không đệ quy) để giải quyết thì nên sử dụng cách này.
Phân loại hàm đệ quy:
Đệ quy trực tiếp: trong một hàm có lời gọi hàm đến chính bản thân hàm đó.
Đệ quy tuyến tính: thân hàm gọi một lần đến chính nó:
Un a, n =1
r + Un-1, n>1
double U(int n, double a, double r)
{
if (n == 1)
return a ;
return r + U(n-1, a, r) ;
}
Đệ quy nhị phân: thân hàm có hai lần gọi chính nó
Un 1, n =1, 2
Un-2 + Un-1, n>2
long Fibo(int n)
{
if (n<2 ) return 1 ;
return Fibo(n-1) + Fibo(n-1) ;
}
Đệ quy phi tuyến: thân hàm gọi nhiều lần đến nó
Un n, n < 6
Un-5 + Un-4 Un-3 + Un-2+ Un-1, n>=6
long U( int n)
{
if (n<6) return n;
long S= 0;
for (int i = 5; i>0; i--)
S+= U(n-i);
return S;
}
Đệ quy hỗ tương: hai hàm đệ quy gọi nhau
Un n, n <5
Un-1 + Gn-2, n>=5
Gn n-3, n <8
Un-1 + Gn-2, n>=8
long G(int n);
long U( int n)
{
if (n<5)
return n;
return U(n-1) + G(n-2);
}
long G(int n)
{
if (n<8)
return n-3;
return U(