การวนซ้ำ กับ การเรียกซ้ำ — ข้อแลกเปลี่ยนคืออะไร

Question

Accepted Answer

**การวนซ้ำ** ใช้ loop; **การเรียกซ้ำ** ใช้การเรียกตัวเอง พวกมันมีพลังเท่ากัน (สิ่งใดที่คุณทำได้ด้วยสิ่งหนึ่ง คุณก็ทำได้ด้วยอีกสิ่งหนึ่ง) แต่พวกมันแตกต่างกันในความชัดเจนและต้นทุน

## เคียงข้างกัน

```python
# Iterative sum: constant extra space
def sum_iter(n):
    total = 0
    for i in range(1, n + 1):
        total += i        # accumulate in a loop
    return total

# Recursive sum: uses the call stack
def sum_rec(n):
    if n == 0:
        return 0
    return n + sum_rec(n - 1)
```

## การเปรียบเทียบ

| ด้าน | การวนซ้ำ | การเรียกซ้ำ |
|--------|-----------|----------|
| หน่วยความจำ | O(1) เพิ่มเติม | O(ความลึก) stack |
| ความเข้าใจง่าย | ยอดเยี่ยมสำหรับการทำงานเชิงเส้น | ยอดเยี่ยมสำหรับต้นไม้ / divide-and-conquer |
| ความเสี่ยง | loop ไม่สิ้นสุด | stack overflow |
| ความเร็ว | มักจะเร็วกว่า (ไม่มีค่าใช้จ่าย call) | ค่าใช้จ่าย call ต่อ frame |

## เมื่อใดจึงควรใช้อะไร

- ใช้ **การวนซ้ำ** สำหรับการข้ามผ่านเชิงเส้นแบบง่ายและเมื่อความลึก stack อาจมีขนาดใหญ่
- ใช้ **การเรียกซ้ำ** เมื่อปัญหามีลักษณะเป็นแบบเรียกซ้ำตามธรรมชาติ (ต้นไม้ กราฟ backtracking) และความลึกถูกจำกัด

## อันตราย

การเรียกซ้ำแบบลึกมีความเสี่ยงต่อ stack overflow; แปลงโค้ด recursive แบบ hot เป็น iteration (มักจะมี stack ที่ชัดเจน) เมื่อความลึกไม่จำกัด

## เหตุที่สำคัญ

การเลือกรูปแบบที่ถูกต้องช่วยให้โค้ดถูกต้องและอ่านง่ายทั้งสองประการ

การเรียกซ้ำทำให้โค้ดต้นไม้และกราฟสวยงาม แต่การรู้ต้นทุน memory ของมันช่วยให้คุณหลีกเลี่ยงข้อขัดข้องบนข้อมูล input ที่ลึก

การตัดสินใจแลกเปลี่ยนนี้คือสิ่งที่ผู้สัมภาษณ์สอบถามอย่างแน่นอนเมื่อพวกเขาขอให้คุณ "แปลงสิ่งนี้เป็น iterative"

ด้าน	การวนซ้ำ	การเรียกซ้ำ
หน่วยความจำ	O(1) เพิ่มเติม	O(ความลึก) stack
ความเข้าใจง่าย	ยอดเยี่ยมสำหรับการทำงานเชิงเส้น	ยอดเยี่ยมสำหรับต้นไม้ / divide-and-conquer
ความเสี่ยง	loop ไม่สิ้นสุด	stack overflow
ความเร็ว	มักจะเร็วกว่า (ไม่มีค่าใช้จ่าย call)	ค่าใช้จ่าย call ต่อ frame