Giải thích về hàm đệ quy trong C++ dễ hiểu nhất

Trong bài viết này, chúng ta sẽ tìm hiểu về hàm đệ quy trong ngôn ngữ lập trình C++. Đây là một khái niệm có thể gây khó khăn cho những người mới bắt đầu học lập trình. Đệ quy là một phương pháp giải quyết vấn đề bằng cách gọi lại chính nó cho đến khi điều kiện dừng được kích hoạt.

Hàm đệ quy trong C++ là gì?

Trong C++, một hàm gọi chính nó được gọi là hàm đệ quy. Trong thân hàm, chúng ta gọi đúng tên hàm hiện tại và truyền vào các tham số đã được khai báo.

Cú pháp:

type functionName(type parameter) {   // statements   functionName(parameter); // recursive call   // statements }

Hãy xem một ví dụ đơn giản về hàm đệ quy trong C++, tính giai thừa của một số nguyên.

Trước khi giải bài toán tính giai thừa, chúng ta cần nhớ công thức tính giai thừa trong toán học:

• 0! = 1
• n! = 1 2 3 ... n (n > 0)

Giờ chúng ta sẽ giải bài toán trên bằng vòng lặp for trong C++.

Giải bằng vòng lặp For

#include  using namespace std;  int giaiThua(int n) {     int giai_thua = 1;      for (int i = 1; i = n; ++i) {         giai_thua *= i;     }      return giai_thua; }  int main() {     int n;      cout  "Nhap so can tinh giai thua: ";     cin >> n;      cout  "Giai thua cua "  n  " la: "  giaiThua(n);      return 0; }

Kết quả khi thực thi chương trình trên sẽ là:

Nhap so can tinh giai thua: 5 Giai thua cua 5 la: 120

Như vậy, để giải quyết bài toán giai thừa của một số bằng vòng lặp for trong C++ rất đơn giản.

Giải bằng đệ quy C++

Hãy xem xét thuật toán tính giai thừa:

• Giả sử chúng ta cần tính 5!
• 5! = 4! * 5
• 4! = 3! * 4
• 3! = 2! * 3
• 2! = 1! * 2
• 1! = 1

Thay các giá trị vào ta có: 5! = 1 2 3 4 5.

Giả sử ta có một hàm đệ quy để tính giai thừa của một số, gọi là tinhGiaiThua, thuật toán đệ quy sẽ là:

• tinhGiaiThua(5) = tinhGiaiThua(4) * 5
• tinhGiaiThua(4) = tinhGiaiThua(3) * 4
• tinhGiaiThua(3) = tinhGiaiThua(2) * 3
• tinhGiaiThua(2) = tinhGiaiThua(1) * 2
• tinhGiaiThua(1) = 1

Vậy, ta có thể sử dụng đệ quy để giải bài toán giai thừa bằng cách gọi lại chính hàm đó.

#include  using namespace std;  int tinhGiaiThua(int n) {     // Điều kiện dừng đệ quy     if (n == 1) {         return 1;     }     // Đệ quy     else {         return tinhGiaiThua(n - 1) * n;     } }  int main() {     int n;      cout  "Nhap so can tinh giai thua: ";     cin >> n;      cout  "Giai thua cua "  n  " la: "  tinhGiaiThua(n);      return 0; }

Kết quả khi thực thi chương trình trên sẽ là:

Nhap so can tinh giai thua: 5 Giai thua cua 5 la: 120

Đối với những người mới bắt đầu học lập trình, cách giải bài toán giai thừa bằng vòng lặp for sẽ dễ hiểu hơn rất nhiều so với việc giải bằng đệ quy. Tuy nhiên, đừng lo lắng, chúng ta sẽ giải thích đoạn mã cho bạn dễ hiểu.

Giả sử mình nhập n = 5, chương trình sẽ chạy như sau:

1. Gọi hàm tinhGiaiThua(5).
2. Hàm tinhGiaiThua(5) gọi lại hàm tinhGiaiThua(4) * 5.
3. Hàm tinhGiaiThua(4) gọi lại hàm tinhGiaiThua(3) * 4.
4. Hàm tinhGiaiThua(3) gọi lại hàm tinhGiaiThua(2) * 3.
5. Hàm tinhGiaiThua(2) gọi lại hàm tinhGiaiThua(1) * 2.
6. Hàm tinhGiaiThua(1) trả về 1.
7. Kết quả cuối cùng là 5 * 4 * 3 * 2 * 1 = 120.

Mục đích của đệ quy là chia vấn đề ban đầu thành các vấn đề nhỏ hơn cho đến khi đạt được điều kiện cơ bản. Trong ví dụ trên, chúng ta giải quyết hàm giai thừa GiaiThua(n) bằng cách gọi hàm giai thừa nhỏ GiaiThua(n-1), điều này được lặp lại liên tục cho đến khi giá trị n đạt đến điều kiện cơ sở (GiaiThua(1) = 1).

Điều kiện dừng đệ quy C++ rất quan trọng

Trong hàm đệ quy, chúng ta nên xác định ít nhất một điều kiện để dừng đệ quy, gọi là điều kiện cơ sở. Nếu không có điều kiện cơ sở để dừng đệ quy, chương trình sẽ lặp vô tận. Do đó, khi giải quyết một bài toán bằng hàm đệ quy mà bạn không tìm ra được điều kiện dừng, hãy tránh sử dụng hàm đệ quy để tránh gây ra vòng lặp vô tận trong chương trình.

Đệ quy trực tiếp và đệ quy gián tiếp C++

Đệ quy trực tiếp: Khi hàm gọi chính nó, gọi là đệ quy trực tiếp. Ví dụ: hàm A gọi hàm A.

Đệ quy gián tiếp: Khi hàm gọi hàm khác và hàm đó lại gọi lại chính hàm gọi, gọi là đệ quy gián tiếp. Ví dụ: hàm A gọi hàm B và hàm B lại gọi lại hàm A.

Chúng ta cùng xem một ví dụ đơn giản về đệ quy gián tiếp:

#include  using namespace std;  void A() {     cout  "Hello from function A!"  endl; }  void B() {     cout  "Hello from function B!"  endl;     A(); }  int main() {     B();      return 0; }

Kết quả khi thực thi chương trình trên sẽ là:

Hello from function B! Hello from function A!

Nhìn chương trình, ta có thể thấy tình huống rất rối, vì vậy hạn chế sử dụng đệ quy trực tiếp và đệ quy gián tiếp.

Một số loại đệ quy C++ thường gặp

Trong lập trình nói chung và trong C++ nói riêng, chúng ta có một số loại đệ quy như sau:

• Đệ quy tuyến tính
• Đệ quy đuôi
• Đệ quy nhị phân
• Đệ quy đa tuyến
• Đệ quy lồng
• Đệ quy tương hỗ

Một số bài toán đệ quy cơ bản:

• Chuỗi Fibonacci

Kết luận

Qua bài học này, chúng ta đã tìm hiểu về hàm đệ quy trong ngôn ngữ lập trình C++. Một điều quan trọng khi sử dụng hàm đệ quy là phải đảm bảo rằng hàm đệ quy đó phải có ít nhất một điều kiện dừng.

Tuy không khuyến khích sử dụng hàm đệ quy trong chương trình, vì nó có thể làm cho chương trình rối và tốn tài nguyên.