1. Khái niệm đệ quy
Một đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc qua một đối tượng khác cùng dạng với nó bằng quy nạp.
Nếu lời giải của một bài toán P thực hiện bằng lời giải của bài toán P’ có dạng giống như P thì đó là một lời giải đệ quy. Nói cách khác, đệ quy trong tin học là dạng hồi quy trong toán học.
Một thủ tục (hàm) đệ quy gồm 2 phần:
Phần neo (điều kiện dừng): phần nay thực hiện khi công việc đơn giản, có thể giải trực tiếp được.
Phần đệ quy (lời gọi đệ quy): trong trường hợp bài toán chưa giải được bằng phần neo, ta xác định các bài toán con và gọi lại chính thủ tục (hàm) của nó với tham số khác để giải những các bài toán con đó.
Phần đệ quy thể hiện tính hồi quy của lời giải. Trong một thủ tục (hàm) đệ quy phải có đủ hai phần trên. Nếu không có phần neo thì thủ tục (hàm) sẽ thực hiện vô hạn. Vì vậy, nó rất quan trọng trong việc xác định tính hữu hạn của lời giải.
2. Phân loại đệ quy
2.1 Đệ quy tuyến tính
Đệ quy tuyến tính là loại đệ quy đơn giản và có độ phức tạp dạng đa thức.
Cú pháp:
Ví dụ: Tính n! được định nghĩa đệ quy như sau:
2.2 Đệ quy nhị phân
Dạng đệ quy này cũng đơn giản và có độ phức tạp dạng đa thức. Sự phân cấp biến nhớ trong quá trình xử lý phát triển theo dạng cây nhị phân.
Cú pháp:
Ví dụ:
2.3 Đệ quy phi tuyến
Dạng đệ quy này tương đối phức tạp và thường được sử dụng trong thuật toán quay lui vét cạn. Tùy theo độ khó của bài toán mà ta xác định độ phức tạp của chương trình, hầu hết dạng đệ quy này có độ phức tạp dạng hàm mũ.
Cú pháp 1:
Cú pháp 2:
Kỹ thuật xử lý và các bài tập của đệ quy phi tuyến sẽ bàn chi tiết thông qua từng bài toán trong thuật toán quay lui vét cạn.
2.4 Đệ quy hỗ tương
Dạng đệ quy này khá thú vị, thể hiện tính tương tác đệ quy giữa các đối tuợng cùng xử lý một bài toán với những trường hợp riêng. Tùy thuộc vào dạng toán xử lý ta tính được độ phức tạp của bài toán.
Cú pháp:
Một đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc qua một đối tượng khác cùng dạng với nó bằng quy nạp.
Nếu lời giải của một bài toán P thực hiện bằng lời giải của bài toán P’ có dạng giống như P thì đó là một lời giải đệ quy. Nói cách khác, đệ quy trong tin học là dạng hồi quy trong toán học.
Một thủ tục (hàm) đệ quy gồm 2 phần:
Phần neo (điều kiện dừng): phần nay thực hiện khi công việc đơn giản, có thể giải trực tiếp được.
Phần đệ quy (lời gọi đệ quy): trong trường hợp bài toán chưa giải được bằng phần neo, ta xác định các bài toán con và gọi lại chính thủ tục (hàm) của nó với tham số khác để giải những các bài toán con đó.
Phần đệ quy thể hiện tính hồi quy của lời giải. Trong một thủ tục (hàm) đệ quy phải có đủ hai phần trên. Nếu không có phần neo thì thủ tục (hàm) sẽ thực hiện vô hạn. Vì vậy, nó rất quan trọng trong việc xác định tính hữu hạn của lời giải.
2. Phân loại đệ quy
2.1 Đệ quy tuyến tính
Đệ quy tuyến tính là loại đệ quy đơn giản và có độ phức tạp dạng đa thức.
Cú pháp:
Code:
Kiểu_dữ_liệu TênHàm(<Danh sách tham số>) {
if (<Điều kiện dừng>) {
…
return <Giá trị trả về>;
} else {
…
…TênHàm(<Danh sách tham số>);
…
}
}
Ví dụ: Tính n! được định nghĩa đệ quy như sau:
2.2 Đệ quy nhị phân
Dạng đệ quy này cũng đơn giản và có độ phức tạp dạng đa thức. Sự phân cấp biến nhớ trong quá trình xử lý phát triển theo dạng cây nhị phân.
Cú pháp:
Code:
Kiểu_dữ_liệu TênHàm(<Danh sách tham số>) {
if (<Điều kiện dừng>) {
…
return <Giá trị trả về>;
} else {
…
…TênHàm(<Danh sách tham số>);
…
…TênHàm(<Danh sách tham số>);
…
}
}
Ví dụ:
2.3 Đệ quy phi tuyến
Dạng đệ quy này tương đối phức tạp và thường được sử dụng trong thuật toán quay lui vét cạn. Tùy theo độ khó của bài toán mà ta xác định độ phức tạp của chương trình, hầu hết dạng đệ quy này có độ phức tạp dạng hàm mũ.
Cú pháp 1:
Code:
Kiểu_dữ_liệu TênHàm(<Danh sách tham số>)
{
for (int i=1; i<=n; i++) {
…
if(<Điều kiện dừng>){
…
}
else {
…
TênHàm(<Danh sách tham số>);
…
}
}
}
Cú pháp 2:
Code:
Kiểu_dữ_liệu TênHàm(<Danh sách tham số>)
{
if(<Điều kiện dừng>){
…
}else {
for (int i=1; i<=n; i++) {
…
TênHàm(<Danh sách tham số>);
…
}
}
}
Kỹ thuật xử lý và các bài tập của đệ quy phi tuyến sẽ bàn chi tiết thông qua từng bài toán trong thuật toán quay lui vét cạn.
2.4 Đệ quy hỗ tương
Dạng đệ quy này khá thú vị, thể hiện tính tương tác đệ quy giữa các đối tuợng cùng xử lý một bài toán với những trường hợp riêng. Tùy thuộc vào dạng toán xử lý ta tính được độ phức tạp của bài toán.
Cú pháp:
Code:
Kiểu_dữ_liệu TênHàm2(<Danh sách tham số>);
Kiểu_dữ_liệu TênHàm1(<Danh sách tham số>) {
…
TênHàm2(<Danh sách tham số>);
…
}
Kiểu_dữ_liệu TênHàm2(<Danh sách tham số>) {
…
TênHàm1(<Danh sách tham số>);
…
}