Nguyên lý Đệ quy (Recursion) trong Cấu trúc dữ liệu

Đệ quy là quá trình hàm gọi chính nó. Dùng đệ quy để giải bài toán lớn thành các bài toán con nhỏ hơn. Chỉ dùng đệ quy khi các bài toán con theo cùng mẫu.

Hàm đệ quy có hai phần: trường hợp cơ sở (base case) và trường hợp đệ quy (recursive case). Base case dùng để kết thúc đệ quy. Nếu không có base case, hàm sẽ đệ quy vô hạn (lý thuyết).

Trong chương trình, khi gọi hàm, giá trị program counter lưu vào ngăn xếp nội bộ trước khi nhảy vào hàm. Sau khi xong, lấy địa chỉ ra gán vào program counter để tiếp tục. Khi đệ quy, lưu địa chỉ nhiều lần. Nếu không có base case, sẽ đệ quy mãi, đầy ngăn xếp → lỗi "Internal Stack Overflow".

Ví dụ: Tính giai thừa n! = n * (n-1)!. Hàm giai thừa gọi lại với tham số giảm 1. Khi tham số 1 hoặc 0, trả về 1 → base case.

Ví dụ (C++)

#include 
using namespace std;
long fact(long n){
    if(n <= 1)
        return 1;
    return n * fact(n-1);
}
main(){
    cout << "Factorial of 6: " << fact(6);
}

Đầu ra

Factorial of 6: 720