On this page
Recursion ลึก & Backtracking
ฟังก์ชันที่เรียกตัวเอง และเทคนิค backtracking (ลองแล้วถอย) สำหรับโจทย์ค้นหาคำตอบ
recursion คือฟังก์ชันที่แก้ปัญหาโดยเรียกตัวเองกับปัญหาที่เล็กลง เหมาะกับโครงสร้างที่ซ้อนกัน (tree, ปัญหาที่แบ่งย่อยได้) และเป็นรากของ backtracking + dynamic programming
องค์ประกอบของ recursion
ทุก recursion ต้องมี (1) base case — เงื่อนไขหยุด และ (2) recursive case — เรียกตัวเองกับปัญหาเล็กลง
def factorial(n):
if n <= 1: # base case (หยุด)
return 1
return n * factorial(n - 1) # recursive case
print(factorial(5)) # 120 (5*4*3*2*1)ถ้าไม่มี base case หรือไม่เข้าใกล้มัน recursion จะเรียกตัวเองไม่จบจน stack ล้น (RecursionError) — Python จำกัด recursion ลึกประมาณ 1000 ชั้น เสมอตรวจว่า base case ถูกและปัญหาเล็กลงทุกครั้ง
ความซับซ้อนของ recursion & call stack (ลึกกว่าพื้นฐาน)
ทุกครั้งที่ฟังก์ชันเรียกตัวเอง Python ดันเฟรมใหม่เข้า call stack — recursion ลึก n ชั้นจึงใช้ O(n) memory เสมอ แม้โค้ดดูสั้น นี่คือต้นทุนที่ loop ไม่มี และเป็นเหตุผลที่ Python จำกัดความลึกไว้กัน stack ล้น
import sys
print(sys.getrecursionlimit()) # ~1000 (ปรับได้ด้วย setrecursionlimit แต่ระวัง)
# วิเคราะห์ความซับซ้อน:
# factorial(n): เรียก n ครั้ง -> เวลา O(n), call stack O(n)
# fib แบบ naive: แตกเป็น 2 กิ่งทุกชั้น -> O(2^n) ช้าระเบิด!
def fib(n):
return n if n < 2 else fib(n-1) + fib(n-2) # O(2^n) — ดูดีแต่ช้ามากดู (1) จำนวนกิ่งที่แตกต่อชั้น และ (2) ความลึก — factorial แตก 1 กิ่ง ลึก n = O(n); fib แตก 2 กิ่ง ลึก n = O(2^n) การเห็นว่า fib naive เป็น O(2^n) คือเหตุผลที่ต้องมี memoization (บท DP) เชื่อมกับ @lru_cache (บท 3)
Recursion vs Iteration — เลือกอะไรเมื่อไร
recursion เขียนสวยกับปัญหาที่แตกย่อยตามธรรมชาติ (tree, divide & conquer) แต่ loop เร็วกว่าและไม่เปลือง call stack ทุก recursion แปลงเป็น loop ได้ (บางทีต้องใช้ stack ของเราเอง)
# recursion (สวยแต่เปลือง stack)
def sum_rec(arr):
if not arr:
return 0
return arr[0] + sum_rec(arr[1:])
# iteration (เร็วกว่า ไม่เปลือง stack)
def sum_iter(arr):
total = 0
for x in arr:
total += x
return total| recursion | iteration (loop) | |
|---|---|---|
| เหมาะกับ | tree, แตกย่อย, backtracking | งานเชิงเส้นทั่วไป |
| memory | O(ความลึก) จาก call stack | O(1) มักไม่เปลือง |
| ความเสี่ยง | stack overflow ถ้าลึกมาก | ไม่มี |
Backtracking — ลองแล้วถอย
backtracking คือลองทุกความเป็นไปได้ ถ้าทางไหนไม่เวิร์กก็ "ถอย" กลับมาลองทางอื่น เหมาะกับโจทย์หาทุกคำตอบ (permutation, subset, แก้ปริศนา)
# สร้าง subset ทั้งหมด
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:]) # เก็บ subset ปัจจุบัน
for i in range(start, len(nums)):
path.append(nums[i]) # เลือก
backtrack(i + 1, path) # ลงลึก
path.pop() # ถอย (backtrack)
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]# permutation ทั้งหมด
def permutations(nums):
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path[:])
return
for i in range(len(remaining)):
backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])
backtrack([], nums)
return result
print(permutations([1, 2, 3])) # 6 แบบสรุปหัวข้อนี้
- recursion = base case (หยุด) + recursive case; ลืม base case → RecursionError
- ความซับซ้อน: นับกิ่ง×ความลึก (factorial O(n), fib naive O(2^n)); call stack = O(ความลึก) space
- recursion vs iteration: loop เร็ว/ประหยัด stack กว่า — recursion เหมาะ tree/แตกย่อย/backtracking
- backtracking = ลองทุกทางแล้วถอย (subset, permutation, ปริศนา)
1) เขียน factorial และ fibonacci ด้วย recursion 2) สร้าง subset ทั้งหมดของ list 3) สร้าง permutation ทั้งหมด 4) อธิบายว่า 'ถอย' (backtrack) คืออะไรด้วยตัวอย่าง