Iteration so với recursion — các đánh đổi là gì?

Question

Accepted Answer

**Iteration** (lặp) dùng vòng lặp; **recursion** (đệ quy) dùng các lời gọi tự thân. Chúng có sức mạnh tương đương (bất cứ điều gì làm được bằng cái này đều làm được bằng cái kia), nhưng khác nhau về độ rõ ràng và chi phí.

## Đặt cạnh nhau

```python
# Tính tổng bằng vòng lặp: bộ nhớ phụ hằng số
def sum_iter(n):
    total = 0
    for i in range(1, n + 1):
        total += i        # cộng dồn trong vòng lặp
    return total

# Tính tổng bằng đệ quy: dùng call stack
def sum_rec(n):
    if n == 0:
        return 0
    return n + sum_rec(n - 1)
```

## So sánh

| Khía cạnh | Iteration | Recursion |
|--------|-----------|-----------|
| Bộ nhớ | O(1) phụ | O(độ sâu) stack |
| Độ dễ đọc | tuyệt vời cho công việc tuyến tính | tuyệt vời cho cây / divide-and-conquer |
| Rủi ro | vòng lặp vô hạn | tràn stack |
| Tốc độ | thường nhanh hơn (không có chi phí gọi hàm) | chi phí gọi hàm cho mỗi khung |

## Khi nào dùng cái nào

- Dùng **iteration** cho các phép duyệt tuyến tính đơn giản và khi độ sâu stack có thể lớn.
- Dùng **recursion** khi bài toán mang tính đệ quy tự nhiên (cây, đồ thị, backtracking) và độ sâu bị giới hạn.

## Những cạm bẫy

Đệ quy sâu có nguy cơ tràn stack; hãy chuyển code đệ quy quan trọng sang dạng lặp (thường với một stack tường minh) khi độ sâu không bị giới hạn.

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

Chọn đúng phong cách giúp code vừa đúng vừa dễ đọc.

Recursion làm cho code xử lý cây và đồ thị trở nên thanh thoát, nhưng biết được chi phí bộ nhớ của nó giúp bạn tránh sập trên các đầu vào sâu.

Khả năng phán đoán đánh đổi này chính là điều người phỏng vấn thăm dò khi họ yêu cầu bạn "chuyển cái này sang dạng lặp".

Khía cạnh	Iteration	Recursion
Bộ nhớ	O(1) phụ	O(độ sâu) stack
Độ dễ đọc	tuyệt vời cho công việc tuyến tính	tuyệt vời cho cây / divide-and-conquer
Rủi ro	vòng lặp vô hạn	tràn stack
Tốc độ	thường nhanh hơn (không có chi phí gọi hàm)	chi phí gọi hàm cho mỗi khung