Đệ quy lồng (Nested Recursion) - Giải thuật đệ quy

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.

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<<"
Kết quả: "<<kq;

  cout<<"
---------------------------
";
  cout<<"Chương trình này được đăng tại Zaidap.com.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.