Trong bài này, bạn sẽ học cách tạo một hàm đệ quy; một hàm gọi tới chính nó.

Một hàm gọi chính nó được coi là hàm đệ quy. Và kỹ thuật này được gọi là đệ quy.

Đệ quy hoạt động như thế nào trong C++?

void recurse()
{
    ... .. ...
    recurse();
    ... .. ...
}

int main()
{
    ... .. ...
    recurse();
    ... .. ...
}

Hình vẽ dưới đây thể hiện cách đệ quy hoạt động bằng cách liên tục gọi tới chính nó.

Đệ quy tiếp tục cho tới khi một vài điều kiện xảy ra.

Để ngăn ngừa việc đệ quy vĩnh viễn, câu lệnh if…else (hoặc cách tương tự) có thể được sử dụng với một nhánh gọi đệ quy và nhánh còn lại thì không.

Ví dụ 1: Tính giai thừa của một số sử dụng đệ quy

// Giai thừa của n = 1*2*3*...*n

#include <iostream>
using namespace std;

int factorial(int);

int main() 
{
    int n;
    cout<<"Enter a number to find factorial: ";
    cin >> n;
    cout << "Factorial of " << n <<" = " << factorial(n);
    return 0;
}

int factorial(int n) 
{
    if (n > 1) 
    {
        return n*factorial(n-1);
    }
    else 
    {
        return 1;
    }
}

Đầu ra

Giải thích: Ví dụ này hoạt động như thế nào?

Giả sử người dùng nhập vào 4, số này được truyền vào hàm factorial().

1. Trong hàm factorial() đầu tiên, biểu thức kiểm tra bên trong câu lệnh if là đúng. Câu lệnh return num*factorial(num-1); sẽ được thực thi. Nó sẽ gọi tới hàm factorial() thứ hai và truyền vào đối số num-1, tức là 3.
2. Trong hàm factorial() thứ hai, biểu thức kiểm tra bên trong câu lệnh if là đúng. Câu lệnh return num*factorial(num-1); được thực thi. Nó sẽ gọi tới hàm factorial() thứ ba và truyền vào đối số num-1, tức là 2.
3. Trong hàm factorial() thứ ba, biểu thức kiểm tra bên trong câu lệnh if là đúng. Câu lệnh return num*factorial(num-1); được thực thi. Nó sẽ gọi tới hàm factorial() thứ tư và truyền vào đối số num-1, tức là 1.
4. Trong hàm factorial() thứ tư, biểu thức kiểm tra bên trong câu lệnh if là sai. Câu lệnh return 1; được thực thi, và sẽ trả về 1 cho hàm factorial() thứ 3.
5. Hàm factorial() thứ 3 sẽ trả về 2 cho hàm factorial() thứ 2.
6. Hàm factorial() thứ 2 sẽ trả về 6 cho hàm factorial() đầu tiên.
7. Cuối cùng, hàm factorial() đầu tiên trả về 24 cho hàm main(), và được hiển thị trên màn hình.