Thuật toán C/C++

Đệ quy và ngăn xếp lời gọi hàm trong C, C++

Trong bài học này, bạn sẽ tính giai thừa bằng hàm đệ quy, đồng thời tìm hiểu điều kiện dừng và chi phí bộ nhớ của đệ quy.

Giới thiệu

Đệ quy là kỹ thuật giải một bài toán bằng cách đưa nó về bài toán nhỏ hơn cùng loại. Mọi hàm đệ quy đều cần một điều kiện dừng (base case), và mỗi lần gọi phải tiến gần hơn đến điều kiện đó, nếu không chương trình sẽ gọi hàm mãi mãi.

Những điểm quan trọng

Kiểm thử với dữ liệu rỗng, chỉ có một phần tử, có giá trị trùng và đã được sắp xếp.
Viết cho đúng trước, tối ưu sau.
Trong code thực tế, ưu tiên dùng các hàm có sẵn của thư viện chuẩn.

Xem cách hoạt động

Nhấn Từng bước để theo từng lời gọi. Lời gọi mới được đẩy lên call stack, và mỗi lời gọi trả giá trị về cho nơi đã gọi nó.

Code ví dụ bằng C và C++

Chạy code →

main.c

#include <stdio.h>

unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main(void) {
    printf("%llu\n", factorial(6));
}

Kết quả khi chạy

C++

Chạy code →

main.cpp

#include <iostream>

constexpr unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main() {
    constexpr auto value = factorial(6);
    std::cout << value << '\n';
}

Kết quả khi chạy

So sánh C và C++

Hàm factorial trả về 1 khi number nhỏ hơn 2, đây là điều kiện dừng, còn lại thì trả về number * factorial(number - 1). Mỗi lần gọi hàm chiếm thêm một phần bộ nhớ trên ngăn xếp lời gọi (call stack), nên thuật toán dùng O(n) thời gian và O(n) bộ nhớ ngăn xếp. Phiên bản C++ đánh dấu hàm là constexpr nên giá trị có thể được tính ngay lúc biên dịch. Với dữ liệu lớn, bạn nên kiểm tra đầu vào và thường dùng vòng lặp thay cho đệ quy.

Vòng lặp, con trỏ, độ dài và vùng nhớ tạm đều được viết tường minh.

C++

Iterator và các thuật toán chuẩn tách thao tác xử lý khỏi cách dữ liệu được lưu trữ.

Bài tập mở rộng

Hãy chạy cả hai phiên bản, sau đó thử thay đổi code để quan sát sự khác biệt về mức độ an toàn mà mỗi ngôn ngữ mang lại.

Tự mô phỏng từng phép so sánh trên giấy.
Thử với giá trị trùng lặp và các giá trị cực lớn, cực nhỏ.
Đo thời gian chạy của code tự viết và so sánh với thư viện chuẩn.

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách