Recursion (đệ quy) là gì?

Question

Accepted Answer

**Recursion** (đệ quy) là khi một hàm tự gọi chính nó để giải một phiên bản nhỏ hơn của cùng một bài toán. Mỗi đệ quy cần một **base case** (trường hợp cơ sở) để dừng lại và một **recursive case** (trường hợp đệ quy) tiến dần về phía base case.

## Ý tưởng

Chia một bài toán thành các bài toán con giống hệt nhau nhưng nhỏ hơn. Mỗi lần gọi đẩy một khung (frame) lên **call stack** (ngăn xếp lời gọi); khi trả về thì lấy chúng ra.

## Ví dụ

```python
def factorial(n):
    if n <= 1:            # base case: dừng đệ quy
        return 1
    return n * factorial(n - 1)   # recursive case: bài toán nhỏ hơn

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## Truy vết

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## Độ phức tạp

Ở đây là **O(n)** thời gian và **O(n)** bộ nhớ stack (một khung cho mỗi lần gọi).

## Những cạm bẫy

- **Thiếu base case** -> đệ quy vô hạn -> tràn stack (stack overflow).
- Đệ quy sâu có thể làm cạn kiệt stack; một số ngôn ngữ không có tối ưu hóa đệ quy đuôi (tail-call optimization).
- Tính lại các bài toán con trùng lặp có thể bùng nổ lên thời gian hàm mũ (khắc phục bằng memoization).

## Tại sao điều này quan trọng

Recursion biểu diễn các bài toán có tính tự tương tự một cách tự nhiên — cây, đồ thị, divide and conquer — gọn gàng hơn nhiều so với vòng lặp.

Nó là mô hình tư duy đằng sau merge sort, backtracking và dynamic programming.

Hiểu về call stack cũng giúp bạn giỏi hơn trong việc debug và lập luận về bộ nhớ.