Recursion คืออะไร?

Question

Recursion คืออะไร?

Accepted Answer

**Recursion** คือเมื่อฟังก์ชันเรียกตัวเองเพื่อแก้ปัญหาเวอร์ชันที่เล็กกว่าของปัญหาเดียวกัน ทุก recursion ต้องมี **base case** ที่หยุดมันและ **recursive case** ที่เคลื่อนไปยัง base

## แนวคิด

แบ่งปัญหาออกเป็นปัญหาย่อยที่เหมือนกัน ทุกครั้งที่เรียกจะผลัก frame ลง **call stack**; การคืนค่า pop ออก

## ตัวอย่าง

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

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

## ติดตาม

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

## ความซับซ้อน

ที่นี่ **O(n)** เวลาและ **O(n)** พื้นที่ stack (frame หนึ่งต่อการเรียก)

## ข้อแม้

- **Base case ขาด** -> recursion ไม่สิ้นสุด -> stack overflow
- Recursion ลึกอาจหมดพื้นที่ stack; บางภาษาไม่มี tail-call optimization
- การคำนวณซ้ำของปัญหาย่อยที่ทับซ้อนกันอาจระเบิดไปเป็นเวลา exponential (แก้ไขด้วย memoization)

## เหตุใดจึงสำคัญ

Recursion แสดง ปัญหาที่มีความคล้ายคลึงกัน — ต้นไม้ สำหรับกราฟ แบ่ง และเอาชนะ — อย่างชัดเจนมากกว่า loops

เป็นแบบจำลองทางจิตใจเบื้องหลัง merge sort backtracking และ dynamic programming

การเข้าใจ call stack ยังทำให้คุณดีขึ้นในการ debugging และการใจด้าน memory