Giai thừa đệ quy

Thuộc phần Logic và luồng chương trình trong hành trình C++ của Coddy. Bài học 46 trên 56.

Giai thừa của một số là ví dụ hoàn hảo để minh họa cách đệ quy hoạt động. Giai thừa của n (viết là n!) là tích của tất cả các số nguyên dương từ 1 đến n. Ví dụ: 5! = 5 × 4 × 3 × 2 × 1 = 120.

Điều khiến giai thừa rất phù hợp với đệ quy là nó có thể được định nghĩa dựa trên chính nó: n! = n × (n-1)!. Điều này có nghĩa là để tính 5!, bạn nhân 5 với 4!, để tính 4!, bạn nhân 4 với 3!, và cứ tiếp tục như vậy.

Đây là cách một hàm giai thừa đệ quy trông như thế nào:

int factorial(int n) {
    if (n <= 1) {           // Trường hợp cơ sở: 0! và 1! đều bằng 1
        return 1;
    }
    
    return n * factorial(n - 1);  // Bước đệ quy (recursion): n! = n × (n-1)!
}

Trường hợp cơ sở dừng đệ quy khi n đạt đến 1 hoặc 0, rồi trả về 1. Bước đệ quy nhân số hiện tại với giai thừa của số nhỏ hơn tiếp theo. Khi gọi factorial(4), hàm tính 4 × 3 × 2 × 1 bằng cách gọi liên tiếp cho đến khi đạt đến trường hợp cơ sở, sau đó nhân tất cả kết quả với nhau khi các lần gọi trả về.

Thử thách

Dễ

Tạo một chương trình triển khai hàm giai thừa đệ quy và dùng hàm đó để tính giai thừa cho các giá trị đầu vào khác nhau. Thử thách này sẽ kiểm tra mức độ hiểu của bạn về cách đệ quy hoạt động: hàm tự gọi lại với các tham số đã thay đổi cho đến khi đạt đến trường hợp cơ sở.

Đầu vào sẽ gồm:

Một số nguyên n biểu thị số cần tính giai thừa

Chương trình của bạn cần:

Tạo một hàm đệ quy có tên factorial, nhận một tham số số nguyên và trả về một số nguyên
Hàm cần triển khai trường hợp cơ sở: nếu n nhỏ hơn hoặc bằng 1, trả về 1
Hàm cần triển khai bước đệ quy: trả về n nhân với giai thừa của n-1
Trong hàm main, đọc giá trị đầu vào
Gọi hàm factorial với giá trị đầu vào
In kết quả theo định dạng đã chỉ định

Dùng định dạng đầu ra chính xác sau:

Factorial of [n] is [result]

Hãy nhớ rằng hàm factorial phải tự gọi lại với một giá trị nhỏ hơn mỗi lần, tiến gần hơn đến trường hợp cơ sở sau mỗi lần gọi đệ quy. Trường hợp cơ sở ngăn đệ quy vô hạn bằng cách dừng khi n đạt đến 1 hoặc 0. Bước đệ quy nhân số hiện tại với giai thừa của số nhỏ hơn tiếp theo, tạo nên kết quả cuối cùng khi các lời gọi hàm trả về giá trị.

Tự làm thử

#include <iostream>
using namespace std;

// TODO: Viết hàm (function) tính giai thừa ở đây

int main() {
    // Đọc đầu vào
    int n;
    cin >> n;
    
    // TODO: Gọi hàm tính giai thừa và lưu kết quả
    
    // In kết quả ra
    cout << "Factorial of " << n << " is " << result << endl;
    
    return 0;
}

Tự kiểm tra

Bài học này có một bài trắc nghiệm ngắn. Bắt đầu bài học để trả lời và theo dõi tiến độ.

Tất cả bài học trong Logic và luồng chương trình

3Dự án: Công cụ danh sách công việc

Tổng quan dự án Thêm công việc

Xem công việc

Xóa công việc

Hoàn thiện công cụ

6Tập hợp (các phần tử duy nhất)

Giới thiệu std::set Tạo tập hợp và thêm phần tử Kiểm tra phần tử Xóa phần tử Duyệt qua tập hợp Ôn tập: các số duy nhất

9Thử thách cuối cùng

Lọc dữ liệu vector Tìm kiếm giá trị trong map Con trỏ và mảng động

Tự luyện tập: Trình biên dịch C++ online