GIẢI THUẬT ĐỆ QUY
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

Đệ 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.

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

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é.

phuong trinh truy hoi ackerman PNG

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.

co che de quy long PNG

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ả:

de quy long PNG

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.

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Top