Bài toán đệ quy

I. Đệ quy là gì?

        Đệ quy là kỹ thuật trong lập trình mà trong đó một hàm gọi lại chính nó để giải quyết một bài toán.

    Giải pháp đệ quy chia bài toán lớn thành các bài toán con giống chính nó, nhưng nhỏ hơn → cho đến khi đạt được “điều kiện dừng” (base case).

II. Cấu trúc của một hàm đệ quy

    1. Điều kiện dừng (base case) – để kết thúc đệ quy, tránh lặp vô hạn.

    2. Gọi lại chính nó (recursive call) – để giải bài toán con.

python

    def  ham_de_quy():

        if điều_kiện_dừng:

        return kết_quả

        else:

        return ham_de_quy(giá_trị_mới)

III. Ví dụ dễ hiểu: Tính giai thừa

Định nghĩa toán học:

$$n! = n \times (n-1) \times (n-2) \times \dots \times 1 \quad (n > 0), \quad 0! = 1$$

Viết bằng Python:

 Giải thích: 

- giaithua(3)` sẽ tính như sau: 

3 * giaithua(2) * 3* (2 * giaithua(1)) * 3 * (2 * (1 * giaithua(0))) *`3 * 2 * 1 * 1 = 6

IV. Ví dụ 2: Tính dãy Fibonacci

$$ F(0) = 0,\quad F(1) = 1,\quad F(n) = F(n-1) + F(n-2) $$ Ví dụ 3: Tính tổng từ 1 đến n Giải thích: t

        Tong(4) = 4 + tong(3) = 4 + 3 + tong(2) = 4 + 3 + 2 + 1 = 10

VI. Khi nào dùng đệ quy? Đệ quy phù hợp khi:

     * Bài toán có thể chia thành các bài toán con giống nhau 

     * Cần giải bài toán cây, danh sách lồng nhau, thuật toán chia để trị (ví dụ: quicksort, mergesort) 

VII. Cảnh báo khi dùng đệ quy 

        Đệ quy có thể gây tràn bộ nhớ (stack overflow) nếu không có điều kiện dừng. 

        Với bài toán lớn, đệ quy chạy chậm hơn vòng lặp → cần cải tiến như memoization hoặc quy hoạch động (dynamic programming).