Hàm đệ quy trong C++

Bài tập

Cho số nguyên dương n được nhập từ bàn phím, bạn hãy viết hàm đệ quy trả về n! (n giai thừa).

Ví dụ: nếu bạn nhập n = 5 thì chương trình sẽ hiển thị lên màn hình 120.

Lý thuyết

Hàm đệ quy là hàm mà gọi tới chính nó, ví dụ một hàm đệ quy sẽ trông giống như sau:

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

Do tính chất tự gọi lại chính nó nên để tránh việc hàm đệ quy chạy không bao giờ dừng bạn luôn cần có điểm dừng (điểm dừng được hiểu đơn giản là tới 1 lúc nào đó, hàm đệ quy sẽ không gọi lại chính nó nữa).

Mô tả hàm đệ quy tính 5!:

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120

Điểm dừng ở ví dụ trên chính là khi đầu vào của hàm factorial bằng 1 thì hàm factorial sẽ trả về 1 thay vì gọi tiếp tới chính nó.

Để hiểu rõ hơn bạn hãy xem ví dụ tiếp theo về hàm đệ quy tính tổng các số từ 1 tới n:

#include<iostream>

using namespace std;

int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
}

int main() {
    cout << sum(10);
    return 0;
}

Điểm dừng ở đây chính là khi n = 0 thì hàm sum trả về 0 thay vì gọi tiếp tới chính nó.

Bạn có thể làm bài này dựa vào ví dụ trên, nếu bạn vẫn chưa làm được thì có thể xem hướng dẫn bên dưới:

Hướng dẫn

Code mẫu:

#include<iostream>

using namespace std;

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

int main() {
    int n;
    cin >> n;
    cout << factorial(n);
    return 0;
}
​​