Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Đệ quy lồng (Nested Recursion)
Trong bài này mình sẽ giới thiệu các bạn một trong các hàm đệ quy tiếp theo đó chính là đệ quy lồng (Nested Recursion).
Đây là một hàm đệ quy được sử dụng khá nhiều trong lập trình nói chung và C++ nói riêng.
Chúng ta sẽ cùng nhau tìm hiểu đệ quy lồng (Nested Recursion) là gì? cách nó hoạt động ra sao?
1. Đệ quy lồng là gì?
Đệ quy lồng là loại đệ quy gọi đối số của nó là một đệ quy. Hiểu đơn giản là tham số truyền vào của hàm đệ quy là một đệ quy.
Bài viết này được đăng tại [free tuts .net]
Ví dụ chúng ta có một hàm đệ quy lồng như sau:
int ackerman(int m, int n){
if(m == 0)
return n + 1;
else if(n == 0)
return ackerman(m - 1, 1);
else
return ackerman(m-1, ackerman(m, n-1));
}
Trong hàm trên, tham số truyền vào khi return ackerman(m-1, ackerman(m, n-1)) là một đệ quy. Một hàm tương tự như vậy được gọi là đệ quy lồng.
Các bạn cùng mình xem cơ chế hoạt động của nó ra sao nhé.
2. Cơ chế đệ quy lồng (Nested Recursion)
Trong phần này mình sẽ lấy hàm ackerman() để làm ví dụ thực hiện xem cơ chế hoạt động của nó như thế nào.
Để làm được nó, việc đầu tiền các bạn phải hiểu được nó là hàm như thế nào. Các bạn có thể tìm hiểu thêm về hàm ackerman().
Ở đây mình sẽ để phương trình truy hồi của nó để các bạn dễ hình dung nhé.
Trong phương trình trên có hai phần, phần thứ nhất là kết quả trả về của phương trình và phần thứ hai là điểm dừng.
Trong trường hợp m > 0 và n > 0, thì tham số của hàm ackerman() chính là một đệ quy.
Để ngắn gọn hơn, mình sẽ ký hiệu hàm ackerman() = A().
Hàm A()
int A(int m, int n){
if(m == 0)
return n + 1;
else if(n == 0)
return A(m - 1, 1);
else
return A(m-1, A(m, n-1));
}Giả sử mình truyền vào hàm A() với hai tham số là m = 2 và n = 1. Khi đó cơ chế hoạt động của hàm trên được biểu diễn như hình dưới đây.
Các bạn có thể thấy nó được thực hiện rất nhiều lần gọi đệ quy và các đệ quy này được lồng vào nhau. Chúng ta đơn giản chỉ cần thực hiện từng đệ quy một, theo đúng tuần tự thì nó không có gì khó cả.
Các bạn có thể luyện tập bằng cách chạy code bằng tay, truyền tham số với m và n tùy chọn. Điều này giúp các bạn rèn luyện tư duy logic rất tốt.
Code mẫu:
#include <iostream>
using namespace std;
int A(int m, int n){
if(m == 0) // nếu m == 0 thì return n + 1
return n + 1;
else if(n == 0) // nếu n == 0 thì return đệ quy A(m - 1, 1)
return A(m - 1, 1);
else // nếu m > 0 và n > 0 thì return đệ quy lồng A(m-1, A(m, n-1))
return A(m-1, A(m, n-1));
}
int main() {
int kq = A(2,1); // truyển tham số đầu vào cho A() là m = 2 và n = 1
cout<<"\nKết quả: "<<kq;
cout<<"\n---------------------------\n";
cout<<"Chương trình này được đăng tại Freetuts.net";
}
Kết quả:
3. Kết luận
Như vậy là chúng ta đã tìm hiểu xong về hàm đệ quy lồng. Đây là một hàm được sử dụng rất nhiều trong lập trình, vì vậy các bạn hãy luyện tập thật nhiều để thành thạo nó nhé. Các bạn có thể tham khảo thêm các bài tập C++ và bài tập C tại đây.
