Cơ bản về đệ quy

Đệ quy là một kỹ thuật trong đó hàm gọi chính nó để giải quyết một vấn đề. Cách này giống như giải quyết một vấn đề lớn bằng cách chia nó thành những vấn đề nhỏ hơn, tương tự.

Hãy cùng xem một hàm đệ quy đơn giản để tính giai thừa:

int factorial(int n) {
    // Trường hợp cơ sở: giai thừa của 0 hoặc 1 là 1
    if (n <= 1) {
        return 1;
    }
    
    // Trường hợp đệ quy: n! = n * (n-1)!
    return n * factorial(n - 1);
}

Mỗi hàm đệ quy cần có:

1. Trường hợp cơ sở để dừng đệ quy
2. Trường hợp đệ quy tiến gần đến trường hợp cơ sở

Ví dụ, tính factorial(3):

• factorial(3) gọi factorial(2)
• factorial(2) gọi factorial(1)
• factorial(1) trả về 1 (trường hợp cơ sở)

• factorial(2) trả về 2 * 1 = 2
• factorial(3) trả về 3 * 2 = 6