การเรียกซ้ำและการคิดแบบแบ่งย่อย

การเรียกซ้ำ (recursion) คือเครื่องมือทางความคิด ไม่ใช่แค่ลูกเล่นของภาษาโปรแกรม หัวใจของมันคือประโยคเดียว: “แก้ปัญหาเวอร์ชันที่เล็กลงของปัญหาเดิม” แล้วประกอบคำตอบกลับขึ้นมา เมื่อคุณมองปัญหาออกว่ามันซ้อนตัวมันเองอยู่ การเขียนโค้ดก็จะกลายเป็นการอธิบายความสัมพันธ์นั้นตรง ๆ

ลองนึกภาพตุ๊กตาแม่ลูกดก (matryoshka) ถ้าอยากรู้ว่าข้างในตุ๊กตาตัวใหญ่ที่สุดมีอะไร คุณเปิดมันแล้วถามคำถาม เดียวกันเป๊ะ กับตุ๊กตาตัวข้างในที่เล็กลง — โครงสร้างเหมือนเดิมทุกอย่าง แค่เล็กลง คุณถามซ้ำแบบนี้ไปเรื่อย ๆ จนถึงตุ๊กตาตัวเล็กที่สุดที่ข้างในไม่มีอะไรแล้ว นั่นคือจุดหยุด จากนั้นย้อนกลับออกมา ตุ๊กตาแต่ละตัวก็รายงานสิ่งที่เจอให้ตัวที่เปิดมันฟัง การเคลื่อนไหวแบบ “ลึกลงไปจนกว่าจะง่ายสุด แล้วรายงานย้อนกลับขึ้นมา” นี้ คือสิ่งที่ฟังก์ชันเรียกซ้ำทำบน call stack เป๊ะ ๆ

กายวิภาคของฟังก์ชันเรียกซ้ำ

ฟังก์ชันแบบเรียกซ้ำทุกตัวต้องมีสองส่วนเสมอ:

• Base case (กรณีฐาน) — กรณีที่เล็กที่สุดที่เรารู้คำตอบทันที ไม่ต้องเรียกตัวเองอีก นี่คือ “ปุ่มหยุด”
• Recursive case (กรณีเรียกซ้ำ) — แตกปัญหาให้เล็กลง แล้วเรียกตัวเองกับปัญหาที่เล็กลงนั้น โดยต้องเข้าใกล้ base case เสมอ

ถ้าตัดทุกอย่างออกจนเหลือแต่โครง ฟังก์ชันเรียกซ้ำทุกตัวจะหน้าตาแบบนี้:

def recurse(problem):
    if is_base_case(problem):              # 1. เงื่อนไขหยุด — กรณีเล็กสุดที่รู้คำตอบแล้ว
        return base_answer(problem)

    smaller_problem = shrink(problem)      # 2. ทำให้เข้าใกล้ base case ขึ้น
    sub_answer = recurse(smaller_problem)  # 3. เรียกตัวเอง — เชื่อมันไปเลย (leap of faith)
    return combine(problem, sub_answer)    # 4. ประกอบผลลัพธ์เป็นคำตอบสุดท้าย

The leap of faith: เวลาเขียนกรณีเรียกซ้ำ ให้ “เชื่อ” ไปเลยว่าการเรียกตัวเองกับปัญหาที่เล็กกว่าจะคืนคำตอบที่ถูกต้องมาให้ คุณไม่ต้องไล่ตามในหัวทุกชั้น แค่ดูแลว่า (1) base case ถูก และ (2) แต่ละครั้งเข้าใกล้ base case จริง เท่านี้ตรรกะก็สมบูรณ์

ตัวอย่างคลาสสิกคือแฟกทอเรียล โดยนิยาม n! = n × (n-1)! และ 0! = 1:

def factorial(n):
    if n == 0:          # base case
        return 1
    return n * factorial(n - 1)   # recursive case

สังเกตว่าโค้ดแทบจะลอกนิยามทางคณิตศาสตร์มาตรง ๆ นี่คือเสน่ห์ของการเรียกซ้ำ: เมื่อปัญหานิยามตัวมันเองได้ โค้ดก็จะอ่านเหมือนนิยามนั้น

การไล่รอย call stack

ทุกครั้งที่ฟังก์ชันถูกเรียก ระบบจะสร้าง “เฟรม (frame)” วางซ้อนบน call stack เก็บค่าตัวแปรและจุดที่ต้องกลับมาทำต่อ มาไล่ดู factorial(4) ทีละขั้น

ช่วง push (ขาลง — เรียกลึกลงไปเรื่อย ๆ จนถึง base case):

              ┌─────────────────────────────┐
push 5 →      │ factorial(0)  return 1       │  ← base case! เริ่มคลายกลับ
              ├─────────────────────────────┤
push 4 →      │ factorial(1)  1 * factorial(0)│
              ├─────────────────────────────┤
push 3 →      │ factorial(2)  2 * factorial(1)│
              ├─────────────────────────────┤
push 2 →      │ factorial(3)  3 * factorial(2)│
              ├─────────────────────────────┤
push 1 →      │ factorial(4)  4 * factorial(3)│  ← เฟรมแรกสุด
              └─────────────────────────────┘

ช่วง pop (ขาขึ้น — แต่ละเฟรมได้คำตอบจากเฟรมที่อยู่ข้างบนแล้วคืนค่าออกไป):

factorial(0) = 1                   pop →  ส่ง 1 ขึ้นไป
factorial(1) = 1 * 1   = 1         pop →  ส่ง 1 ขึ้นไป
factorial(2) = 2 * 1   = 2         pop →  ส่ง 2 ขึ้นไป
factorial(3) = 3 * 2   = 6         pop →  ส่ง 6 ขึ้นไป
factorial(4) = 4 * 6   = 24        pop →  คำตอบสุดท้าย = 24

ขาลงคือการ “แตกปัญหา” ขาขึ้นคือการ “ประกอบคำตอบ” คำตอบจริงจะคำนวณตอนคลายสแตกกลับ ไม่ใช่ตอนเรียกลงไป

รูปแบบ push/pop เดียวกันนี้เกิดกับฟังก์ชันเรียกซ้ำอื่น ๆ ได้เหมือนกัน แม้จะเรียบง่ายกว่า ลองไล่ sum_list([3, 1, 4]):

การเรียก	ตัวฟังก์ชันคำนวณเป็น	คืนค่า (เมื่อการเรียกข้างในคืนค่าแล้ว)
sum_list([3, 1, 4])	3 + sum_list([1, 4])	3 + 5 = 8
sum_list([1, 4])	1 + sum_list([4])	1 + 4 = 5
sum_list([4])	4 + sum_list([])	4 + 0 = 4
sum_list([])	base case ไม่เรียกต่อ	0

อ่านตารางจากบนลงล่างคือลำดับ push อ่านจากล่างขึ้นบนคือลำดับ pop — คำตอบจะเป็นรูปเป็นร่างจริงก็ต่อเมื่อแถวล่างสุด (base case) คลี่คลายก่อน

Tree recursion: เมื่อการเรียกหนึ่งครั้งกลายเป็นหลายครั้ง

ทุกการเรียกซ้ำใน factorial จะก่อให้เกิดการเรียกซ้ำอีกครั้งเดียวเท่านั้น — สายการเรียกจึงเป็นเส้นตรง ลึกลงไป n ชั้น นี่คือ linear recursion: วาดกราฟการเรียกออกมาจะได้เส้นทางเดียว ปริมาณงานทั้งหมดจึงแปรผันตรงกับความลึก คือ O(n)

ฟีโบนัชชีต่างออกไป fib(n) = fib(n-1) + fib(n-2) เรียกตัวเอง สองครั้ง ในแต่ละชั้น และแต่ละครั้งก็เรียกต่ออีกสองครั้ง วาดออกมาจะได้ต้นไม้ที่แตกกิ่ง ไม่ใช่เส้นตรง นี่คือ tree recursion

def fib(n):
    if n < 2:                       # base case
        return n
    return fib(n - 1) + fib(n - 2)  # เรียกซ้ำสองครั้ง — ต้นไม้แตกกิ่งตรงนี้

ต้นไม้การเรียกของ fib(4):

                          fib(4)
                       /          \
                 fib(3)            fib(2)
                /       \          /      \
           fib(2)     fib(1)   fib(1)    fib(0)
          /      \
     fib(1)      fib(0)

สังเกตให้ดี: fib(2) ถูกคำนวณสองครั้ง และ fib(1) ถูกคำนวณถึงสามครั้ง ลองซูมออกไปที่ fib(30) ปัญหาย่อยเล็ก ๆ แบบนี้จะถูกคำนวณซ้ำนับล้านครั้ง นี่คือ overlapping subproblems (ปัญหาย่อยที่ซ้อนทับกัน) — อินพุตเดียวกันเป๊ะ ๆ โผล่ขึ้นมาซ้ำ ๆ ในหลายจุดของต้นไม้ และการเรียกซ้ำแบบไร้เดียงสาก็คำนวณมันใหม่ตั้งแต่ต้นทุกครั้ง แล้วทิ้งคำตอบไปทันทีที่คืนค่า

ลองลากสไลเดอร์ในวิดเจ็ตด้านบน แล้วดูจำนวนโหนดของต้นไม้ระเบิดขึ้น — ต้นไม้จะมีขนาดเพิ่มขึ้นเกือบเท่าตัวทุกครั้งที่ n เพิ่มขึ้น 1 เพราะแต่ละโหนดแตกลูกออกไปสองตัว การเพิ่มเป็นเท่าตัวแบบนี้คือลายเซ็นของการเติบโตแบบเอ็กซ์โพเนนเชียล

Linear recursion (เรียกครั้งเดียวต่อชั้น เหมือน factorial) เสียค่าใช้จ่ายรวม O(n) ครั้ง ส่วน tree recursion ที่มี branching factor เท่ากับ b และความลึก n จะเสียค่าใช้จ่ายราว O(bⁿ) ครั้ง — สำหรับ fib แบบไร้เดียงสา คือ O(2ⁿ) (แม่นยำกว่านั้นคือ O(φⁿ) โดย φ ≈ 1.618 แต่ประเด็นสำคัญคือคำว่า “เอ็กซ์โพเนนเชียล”)

ทำไมการเรียกซ้ำแบบไร้เดียงสาถึงระเบิด — และวิธีแก้

ลองดูตัวเลขจริง: fib(30) เรียกตัวเองกว่า 2.7 ล้านครั้ง เพื่อคำนวณเลขจำนวนเต็มตัวเดียวที่เก็บได้ในไม่กี่ไบต์ fib(50) จะเรียกตัวเองกว่า 4 หมื่นล้านครั้ง — ต้องรอเป็นนาทีเพื่อได้คำตอบที่เครื่องคิดเลขให้ได้ทันที ปัญหาไม่ได้อยู่ที่การเรียกซ้ำเอง แต่อยู่ที่ ปัญหาย่อยเดียวกันถูกแก้ซ้ำแล้วซ้ำเล่า และแต่ละครั้งที่แก้เสร็จ คำตอบก็ถูกทิ้งไปทันที

วิธีแก้แทบจะง่ายจนน่าอาย: จำสิ่งที่คำนวณไปแล้วเอาไว้

def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n < 2:
        return n
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

ตอนนี้แต่ละค่า n จะถูกคำนวณแค่ครั้งเดียว — fib(30) ลดจากราว 2.7 ล้านครั้งเหลือแค่ 30 ครั้ง เทคนิคนี้ — การแคชผลลัพธ์ของแต่ละปัญหาย่อยที่ไม่ซ้ำกัน เพื่อไม่ต้องทำงานซ้ำอีก — เรียกว่า memoization มันเปลี่ยนต้นไม้เอ็กซ์โพเนนเชียลของงานที่ทำซ้ำ ให้กลายเป็นสายงานเชิงเส้นที่ทำครั้งเดียวจบ

Memoization คือสะพานเชื่อมระหว่างการเรียกซ้ำกับ dynamic programming: เมื่อไหร่ก็ตามที่คุณเจอต้นไม้การเรียกซ้ำที่มี overlapping subproblems ให้ถามตัวเองว่า “ปัญหาย่อยนี้เคยแก้ไปแล้วหรือยัง” ถ้าใช่ นั่นคือสัญญาณให้แคชไว้ บทเรียนถัดไปจะต่อยอดแนวคิดนี้ให้เป็นเทคนิคเต็มรูปแบบ — ทั้ง top-down memoization และ bottom-up table

การเรียกซ้ำ กับ การวนซ้ำ (Recursion vs. Iteration)

การเรียกซ้ำและการวนซ้ำ (while/for) คำนวณผลลัพธ์เดียวกันได้ — คำถามคือรูปแบบไหนเข้ากับทรงของปัญหา และคุณยอมจ่ายอะไรเพื่อแลกกับมัน

	Recursion	Iteration
พื้นที่	O(d) เฟรมบน call stack ตามความลึก d	O(1) พื้นที่เพิ่มเติม (ส่วนใหญ่)
เหมาะเมื่อ	ปัญหามีลักษณะซ้อนตัวเองตามธรรมชาติ (ต้นไม้, โครงสร้างซ้อนกัน, divide-and-conquer)	ปัญหาเป็นการไล่เชิงเส้นตรง ๆ
ความเสี่ยง	stack overflow ถ้า d ใหญ่	ไม่มีความเสี่ยงจากความลึก — ลูปไม่กินสแตก
เฉพาะ Python	ไม่มี tail-call optimization; เพดานเริ่มต้นราว 1000 ครั้ง	ไม่มีเพดาน นอกจากหน่วยความจำที่มีอยู่
รูปร่างโค้ด	มักสั้นกว่า สะท้อนนิยามทางคณิตศาสตร์	บางครั้งยาวกว่า แต่เห็นทุกขั้นตอนชัดเจน

แฟกทอเรียลที่เขียนใหม่แบบวนซ้ำไม่ต้องใช้สแตกเพิ่มเลย:

def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

คำตอบเดียวกัน แต่ใช้พื้นที่ O(1) แทนที่จะเป็น O(n) เมื่อไหร่ที่ฟังก์ชันเรียกซ้ำเป็นแบบ linear (เรียกครั้งเดียวต่อชั้น) และ ความลึกอาจใหญ่ (แปรผันตามขนาดอินพุต) ให้เลือกเวอร์ชันวนซ้ำแทน ใช้การเรียกซ้ำเมื่อความลึกตื้นตามธรรมชาติ (O(log n) เช่นใน binary search) หรือเมื่อข้อมูลเป็นต้นไม้/กราฟอยู่แล้ว ซึ่งถ้าเขียนแบบวนซ้ำก็ต้องจัดการสแตกเองอยู่ดี การเรียกซ้ำจึงแค่ใช้ call stack ที่ Python มีให้ฟรีอยู่แล้ว

แบ่งแยกแล้วพิชิต (Divide and Conquer)

การเรียกซ้ำคือรูปแบบหนึ่งของการ แบ่งย่อย (decomposition) — แทนที่จะแก้ปัญหาก้อนใหญ่ทีเดียว เราแบ่งมันเป็นปัญหาย่อยที่เหมือนกัน แก้แต่ละชิ้น แล้วรวมผลลัพธ์ แนวคิด “แบ่งแล้วพิชิต (divide and conquer)” คือการนำหลักนี้มาใช้อย่างจงใจ: แบ่ง ปัญหาออกเป็นส่วน ๆ, พิชิต แต่ละส่วนด้วยการเรียกซ้ำ, แล้ว รวม คำตอบ

• Merge sort — แบ่งลิสต์ออกเป็นสองครึ่ง เรียงแต่ละครึ่ง (เรียกซ้ำ) แล้ว merge สองครึ่งที่เรียงแล้วเข้าด้วยกัน ได้ O(n log n)
• Binary search — มองครึ่งหนึ่งของช่วงค้นหาทิ้งไปทุกครั้งที่เทียบกับค่ากลาง เหลือปัญหาที่เล็กลงครึ่งหนึ่ง ทำให้ค้นเจอใน O(log n)

สังเกตคำว่า log n ที่โผล่มา — มันเป็นลายเซ็นของการ “ตัดปัญหาลงครึ่งหนึ่งทุกขั้น” ซึ่งเป็นหัวใจของ divide and conquer เทียบกับ tree recursion ด้านบน: divide-and-conquer ก็แตกกิ่งเหมือนกัน แต่แต่ละกิ่งทำงานกับส่วนของอินพุตที่ ไม่ทับซ้อนกัน จึงไม่มีงานซ้ำต้องคำนวณใหม่ นี่คือสิ่งที่ทำให้ O(n log n) และ O(log n) ยังเร็วอยู่ ไม่ระเบิดแบบเอ็กซ์โพเนนเชียล

ต้นทุนของการเรียกซ้ำ

ความสง่างามมีราคา ทุกการเรียกที่ยังไม่คืนค่าจะกินเฟรมบน call stack หนึ่งช่อง ดังนั้นการเรียกซ้ำที่ลึก d ชั้นใช้พื้นที่ O(d) เสมอ แม้ตัวงานต่อชั้นจะเล็กก็ตาม

• ถ้าลึกเกินไป สแตกจะเต็ม เกิด stack overflow (ใน Python จะเป็น RecursionError)
• Python ตั้งเพดานไว้กันลูปไม่รู้จบ ดูได้ด้วย sys.getrecursionlimit() (ปกติ ~1000) และตั้งใหม่ได้ด้วย sys.setrecursionlimit(n) — แต่ดันสูงเกินไปอาจทำให้ล่มจริง ๆ
• Python ไม่มี tail-call optimization จึงไม่สามารถพึ่งการเรียกซ้ำลึก ๆ แบบบางภาษาได้

import sys
print(sys.getrecursionlimit())   # เช่น 1000

เมื่อความลึกของการเรียกซ้ำเป็นสัดส่วนกับขนาดข้อมูล (เช่น วน element ละ 1 ชั้นกับลิสต์ล้านตัว) การวนซ้ำ (iteration) ด้วย while/for มักปลอดภัยกว่า เพราะใช้พื้นที่ O(1) และไม่ชนเพดานสแตก ใช้การเรียกซ้ำเมื่อความลึกตื้น (เช่น O(log n)) หรือเมื่อโครงสร้างเป็นต้นไม้ตามธรรมชาติ

ปัญหาจากโลกจริง

โครงสร้างที่ “เป็นต้นไม้” คือสนามเด็กเล่นของการเรียกซ้ำ เช่นการเดินสำรวจสารบบไฟล์ (directory tree) ที่โฟลเดอร์หนึ่งมีโฟลเดอร์ย่อยซ้อนได้ไม่จำกัด

import os

def total_size(path):
    """คืนขนาดรวม (ไบต์) ของทุกไฟล์ใต้ path แบบเรียกซ้ำ"""
    if os.path.isfile(path):          # base case: เป็นไฟล์ คืนขนาดของมันเลย
        return os.path.getsize(path)

    total = 0
    for name in os.listdir(path):     # recursive case: เป็นโฟลเดอร์
        child = os.path.join(path, name)
        total += total_size(child)    # บวกขนาดของลูกแต่ละตัว (เรียกซ้ำ)
    return total

print(total_size("."))

โครงสร้างโฟลเดอร์ซ้อนกันลึกแค่ไหนก็ได้ แต่โค้ดยังสั้นเท่าเดิม เพราะแต่ละชั้นเราแค่บอกว่า “ขนาดของโฟลเดอร์ = ผลรวมขนาดของลูก ๆ” แล้วปล่อยให้การเรียกซ้ำลงไปจัดการชั้นที่ลึกกว่าเอง — นี่คือ leap of faith ในการใช้งานจริง

แบบฝึกหัด

ลองเขียนเองก่อนเปิดเฉลยทุกข้อ

๑. ผลรวมของลิสต์ — เขียน sum_list(xs) ที่คืนผลรวมของตัวเลขในลิสต์โดยใช้การเรียกซ้ำ

เฉลย

def sum_list(xs):
    if not xs:              # base case: ลิสต์ว่าง
        return 0
    return xs[0] + sum_list(xs[1:])   # หัว + ผลรวมของหาง

๒. กลับด้านสตริง — เขียน reverse(s) ที่คืนสตริงที่กลับด้านแล้ว

เฉลย

def reverse(s):
    if len(s) <= 1:         # base case: ว่างหรือตัวเดียว
        return s
    return reverse(s[1:]) + s[0]   # กลับด้านหาง แล้วต่อหัวไว้ท้าย

๓. ฟีโบนัชชี — เขียน fib(n) โดยที่ fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2)

เฉลย

def fib(n):
    if n < 2:               # base case: fib(0)=0, fib(1)=1
        return n
    return fib(n - 1) + fib(n - 2)

เวอร์ชันนี้ตรงไปตรงมา แต่ช้ามาก — อย่างที่หัวข้อ tree recursion ด้านบนแสดงไว้ มันคำนวณค่าซ้ำ ๆ จนเวลาเป็น O(2ⁿ) เช่น fib(40) เรียกตัวเองนับร้อยล้านครั้ง วิธีแก้คือ memoization ลดเหลือ O(n) ซึ่งคือจุดเริ่มต้นของ dynamic programming ที่จะได้เรียนต่อไป

๔. ยกกำลัง — เขียน power(base, exp) คืนค่า base ยกกำลัง exp (จำนวนเต็มไม่ติดลบ)

เฉลย

def power(base, exp):
    if exp == 0:            # base case: อะไรก็ตามยกกำลัง 0 = 1
        return 1
    return base * power(base, exp - 1)

ทำให้เร็วขึ้นเป็น O(log exp) ได้ด้วยการยกกำลังแบบแบ่งครึ่ง: power(b, e) = power(b, e//2)² (แล้วคูณ b เพิ่มถ้า e เป็นเลขคี่) — นี่ก็คือ divide and conquer อีกครั้ง และยังเป็น linear recursion (เรียกครั้งเดียวต่อชั้น) ไม่ใช่ tree recursion เพราะแต่ละครั้งย่อขนาดลงไปหาปัญหาย่อยเดียวเท่านั้น

๕. นับโหนดในต้นไม้ — กำหนดต้นไม้เป็น dict {"value": x, "children": [...]} เขียน count_nodes(tree) นับจำนวนโหนดทั้งหมด

เฉลย

def count_nodes(tree):
    count = 1               # นับตัวเอง
    for child in tree["children"]:
        count += count_nodes(child)   # บวกจำนวนโหนดของแต่ละลูก
    return count
# โหนดใบ (children ว่าง) คือ base case โดยปริยาย: ลูปไม่ทำงาน คืน 1

๖. GCD แบบยุคลิด — Big O คืออะไร นี่คือการหา greatest common divisor แบบเรียกซ้ำ ความซับซ้อนด้านเวลาของมันคืออะไร ในรูปของ a และ b

def gcd(a, b):
    if b == 0:              # base case
        return a
    return gcd(b, a % b)    # recursive case

เฉลย

O(log(min(a, b))) แต่ละครั้งที่เรียกจะแทน (a, b) ด้วย (b, a % b) และผลลัพธ์คลาสสิก (เกี่ยวโยงกับเลขฟีโบนัชชีผ่าน Lamé’s theorem) แสดงว่า a % b จะเล็กลงประมาณครึ่งหนึ่งภายในทุกสองขั้น จำนวนการเรียกจึงเพิ่มแบบลอการิทึม ไม่ใช่เชิงเส้น ตามขนาดอินพุต นี่คือเหตุผลที่อัลกอริทึมของยุคลิดจัดการอินพุตนับร้อยหลักได้ทันที — ต่างกันสุดขั้วกับการระเบิดแบบเอ็กซ์โพเนนเชียลของ fib แบบไร้เดียงสาด้านบน ทั้งที่ทั้งคู่เป็นการเรียกซ้ำเหมือนกัน

๗. ทายผลลัพธ์ — โดยไม่ต้องรันโค้ด มันจะพิมพ์อะไรออกมา และเรียงลำดับยังไง

def mystery(n):
    if n == 0:
        return
    print("enter", n)
    mystery(n - 1)
    print("exit", n)

mystery(3)

เฉลย

enter 3
enter 2
enter 1
exit 1
exit 2
exit 3

print("enter", ...) ทุกครั้งเกิดขึ้นตอนขาลง (push phase) ก่อนการเรียกซ้ำ ส่วน print("exit", ...) ทุกครั้งเกิดขึ้นตอนขาขึ้น (pop phase) หลังการเรียกซ้ำคืนค่ากลับมาแล้ว สอดคล้องกับการ trace push/pop ของแฟกทอเรียลก่อนหน้านี้: โค้ดที่เขียนไว้ ก่อน การเรียกซ้ำจะทำงานจากบนลงล่าง ส่วนโค้ดที่เขียนไว้ หลัง จะทำงานจากล่างขึ้นบน

๘. จับบั๊ก — ฟังก์ชันนี้ควรจะพิมพ์ n, n-1, ..., 1 มันมี base case อยู่ แต่กลับ crash ด้วย RecursionError ทำไม

def count_down(n):
    if n == 0:
        return
    print(n)
    count_down(n)

เฉลย

การเรียกซ้ำส่ง n แบบเดิมไปโดยไม่ลดค่าเป็น n - 1 มี base case อยู่จริง (n == 0) แต่ไม่มีการเรียกครั้งไหนเข้าใกล้มันเลยเมื่อ n เริ่มต้นมากกว่า 0 — ฟังก์ชันเรียกตัวเองด้วยอาร์กิวเมนต์เดิมไปเรื่อย ๆ ไม่รู้จบ การมี base case เป็นเงื่อนไขที่จำเป็นแต่ไม่เพียงพอ: ทุกการเรียกซ้ำต้องเข้าใกล้ base case อย่างวัดผลได้ด้วย วิธีแก้: count_down(n - 1)

๙. ปรับปรุงโค้ดนี้ให้ดีขึ้น — ผู้สัมภาษณ์ขอให้คุณทำให้ฟังก์ชันนี้เร็วขึ้นโดยไม่เปลี่ยนค่าที่มันคืน คุณจะทำยังไง และเร็วขึ้นแค่ไหน

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

เฉลย

เพิ่ม memoization — แคชค่าแต่ละ n ตั้งแต่ครั้งแรกที่คำนวณเสร็จ แล้วดึงจากแคชแทนการคำนวณใหม่ทุกครั้งที่ถูกเรียกอีก:

def fib(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n < 2:
        return n
    cache[n] = fib(n - 1, cache) + fib(n - 2, cache)
    return cache[n]

วิธีนี้ทำให้เวอร์ชันไร้เดียงสาที่เรียก O(2ⁿ) ครั้ง ลดเหลือ O(n) — สำหรับ fib(30) ราว 2.7 ล้านครั้งยุบเหลือแค่ 30 ครั้ง ผลลัพธ์เหมือนเดิม โครงสร้างการเรียกซ้ำเหมือนเดิม แต่ต้นทุนต่างกันสุดขั้ว เพียงเพราะ overlapping subproblems ไม่ถูกคำนวณซ้ำอีกต่อไป การแคชแบบนี้คือแก่นของ dynamic programming

AI Code Critique

ผู้ช่วย AI ถูกขอให้เขียนฟังก์ชันนับถอยหลังจาก n ลงไปและตอบกลับมาแบบนี้ พร้อมยืนยันว่า “ทำงานได้แน่นอน” คุณเห็นด้วยไหม

def countdown(n):
    print(n)
    countdown(n - 1)   # เรียกตัวเองลดลงทีละ 1

countdown(5)

ลองคิดก่อนเลื่อนดูเฉลย: ฟังก์ชันนี้จะหยุดเมื่อไหร่

Solution

ผิด — ไม่มี base case ฟังก์ชันนี้เรียกตัวเองไม่มีวันหยุด ค่า n ลดลงเรื่อย ๆ ผ่าน 0 ไปติดลบไม่สิ้นสุด จนสแตกเต็มและเกิด RecursionError: maximum recursion depth exceeded นี่คือ infinite recursion ซึ่งเป็นข้อผิดพลาดที่ AI ชอบทำเมื่อลืมเงื่อนไขหยุด

แก้โดยเพิ่ม base case ที่ทำให้การเรียกซ้ำสิ้นสุด:

def countdown(n):
    if n < 0:           # base case: หยุดเมื่อเลยศูนย์
        return
    print(n)
    countdown(n - 1)

บทเรียน: เวลารับโค้ดเรียกซ้ำจากใครก็ตาม (รวมถึง AI) เช็กสองข้อทันที — (1) มี base case ไหม และ (2) ทุกการเรียกเข้าใกล้ base case จริงหรือเปล่า ถ้าขาดข้อใดข้อหนึ่ง โค้ดจะวนไม่รู้จบ แบบฝึกหัดข้อ ๘ ด้านบนแสดงความล้มเหลวแบบที่สองแยกให้ดูชัด ๆ: มี base case อยู่จริง แต่ไม่มีทางไปถึงมันได้เลย

🎮 เกมเดฟ: การเรียกซ้ำ

เครื่องมือเทสี (paint bucket), การเผยฝ้าหมอกสงคราม (fog of war), และตัวตรวจจับกลุ่มเจมในเกม match-3 ล้วนเป็นอัลกอริทึมเดียวกันแค่สวมชุดคนละแบบ นั่นคือ flood fill เริ่มจากช่องเมล็ดพันธุ์หนึ่งช่อง แล้วมันจะเรียกซ้ำแผ่ออกไปยังทุกช่องข้างเคียงที่มีคุณสมบัติเดียวกับเมล็ดพันธุ์ (สีเดียวกัน, สถานะ “ยังไม่สำรวจ” เดียวกัน, ชนิดเจมเดียวกัน) แล้วหยุดตรงที่คุณสมบัตินั้นขาดตอน นี่คือรูปแบบ “ย่อปัญหา-เชื่อ-ประกอบคำตอบ” เป๊ะ ๆ เหมือนกับ total_size ด้านบน เพียงแต่ “ลูก” ของแต่ละช่องคือช่องข้างเคียงทั้งสี่ทิศ แทนที่จะเป็นไฟล์ในโฟลเดอร์

Flood fill แบบเรียกซ้ำไร้เดียงสา เชื่อมต่อแบบ 4 ทิศ (4-connected) มี base case สามแบบ: หลุดขอบแผนที่, ไปแล้ว, สีไม่ตรง

def flood_fill(grid, x, y, target, replacement, visited=None):
    """เรียกซ้ำเพื่อทาสีทุกช่องที่เชื่อมต่อแบบ 4 ทิศกับ (x, y) และมีสีตรงกับ
    target — เครื่องมือเทสี, การตรวจกลุ่มเจมใน match-3, และการเผยฝ้าหมอกสงคราม
    ล้วนเป็นอัลกอริทึมเดียวกันนี้ แค่สวมหมวกคนละใบ"""
    if visited is None:
        visited = set()
    height, width = len(grid), len(grid[0])

    if not (0 <= x < width and 0 <= y < height):   # base case: หลุดขอบแผนที่
        return
    if (x, y) in visited:                          # base case: ทำไปแล้ว
        return
    if grid[y][x] != target:                       # base case: สีไม่ตรง / เป็นกำแพง
        return

    visited.add((x, y))
    grid[y][x] = replacement                        # ลงมือทำงานที่ช่องนี้

    flood_fill(grid, x + 1, y, target, replacement, visited)  # ขวา
    flood_fill(grid, x - 1, y, target, replacement, visited)  # ซ้าย
    flood_fill(grid, x, y + 1, target, replacement, visited)  # ลง
    flood_fill(grid, x, y - 1, target, replacement, visited)  # ขึ้น

องค์ประกอบสามอย่างเดียวกับฟังก์ชันเรียกซ้ำทุกตัวในบทเรียนนี้: base case ที่หยุดการเรียกซ้ำ, recursive case ที่คืบหน้าเข้าใกล้ base case (การมาร์กช่องว่า “ไปแล้ว” ก่อนเรียกซ้ำ คือ ความคืบหน้าในที่นี้), และ leap of faith ที่เชื่อว่า flood fill ของช่องข้างเคียงแต่ละช่องจะจัดการทุกอย่างที่อยู่ถัดไปได้ถูกต้อง

รูป: การเรียกซ้ำแบบ flood fill แผ่ออกเป็นวงจากช่องเริ่มต้น (0) — ตัวเลขคือความลึกของการเรียกซ้ำนับจากช่องเริ่มต้น ส่วนช่อง × สองช่องคือกำแพงที่หยุดการแผ่ทันที

วิธีแก้แบบวนซ้ำ. รัน flood_fill บนห้องทดสอบเล็ก ๆ มันทำงานสมบูรณ์แบบ แต่ถ้ารันบนแผนที่หมอกสงครามโล่งกว้าง 500×500 ช่อง มันอาจ crash ด้วย RecursionError ทั้งที่ตัวอัลกอริทึมไม่ได้ผิดอะไรเลย การเดินแบบ depth-first อาจมุดลึกไปในทิศทางเดียวหลายหมื่นช่องก่อนจะย้อนกลับ ความลึกของการเรียกซ้ำวัดตามความยาวของอุโมงค์นั้น ไม่ใช่จำนวนช่องทั้งหมด — และ call stack ของ Python ไม่มีที่พอสำหรับอุโมงค์ยาว 1 แสนเฟรม นี่คือหัวข้อ “ต้นทุนของการเรียกซ้ำ” ที่เจอมาแล้ว เพียงแค่สวมหมวกของการออกแบบด่าน: พื้นที่ที่มีรูปทรงให้ DFS มุดลึกได้ก่อนจะแตกกิ่ง คือ stack overflow ที่รอวันเกิดขึ้น

วิธีแก้คือแบบเดียวกับที่หัวข้อนั้นบอกไว้แล้ว: เอาสแตกโดยนัย (call stack) มาแลกกับสแตกที่ประกาศเอง

def flood_fill_iterative(grid, x, y, target, replacement):
    height, width = len(grid), len(grid[0])
    stack = [(x, y)]
    while stack:
        cx, cy = stack.pop()
        if not (0 <= cx < width and 0 <= cy < height):
            continue
        if grid[cy][cx] != target:
            continue
        grid[cy][cx] = replacement
        stack.extend([(cx + 1, cy), (cx - 1, cy), (cx, cy + 1), (cx, cy - 1)])

ช่องที่ถูกทาสียังเหมือนเดิม ปริมาณงานเท่าเดิม แต่ “สแตก” ตอนนี้เป็นลิสต์ของ Python บน heap ไม่ใช่เฟรมบน C stack — มันขยายได้ถึงล้านรายการโดยไม่บ่น ถ้าเปลี่ยนจาก list.pop() (LIFO) เป็น collections.deque กับ popleft() (FIFO) การทาสีชุดเดียวกันจะเกิดขึ้นแบบ breadth-first เป็นวง ๆ ทีละชั้น — ภาพวงกลมขยายตัวคลาสสิกของการเผยฝ้าหมอกสงคราม

วิดเจ็ตกริดนี้ในทางเทคนิคแก้ปัญหาคนละแบบ — หาเส้นทางที่สั้นที่สุด ไม่ใช่ flood fill — แต่ลองคลิกวางกำแพงสักสองสามช่องแล้วดูว่ามันตัดแบ่งเส้นทางการเดินอย่างไร สัญชาตญาณเดียวกัน: กำแพงคือ base case ที่หยุดการแผ่ทันที และรูปทรงของกำแพงเป็นตัวกำหนดรูปทรง (และความลึก) ของการค้นหา

การเดินสำรวจ scene tree งานอีกอย่างของการเรียกซ้ำในเกมเอนจินคือการเดินสำรวจ scene tree เอง — ลำดับชั้นพ่อ-ลูกของโหนดทั้งหมด ตั้งแต่วิดเจ็ตของแผง UI ไปจนถึง hitbox ของศัตรู แบบฝึกหัดข้อ ๕ ในบทเรียนหลัก คือ count_nodes เป็น การเดินสำรวจ scene tree ในภาษาเกมพอดี: สลับคำว่า “tree” เป็น “scene root” และ “children” เป็น “child nodes” ก็จะได้ฟังก์ชันเดียวกับที่เอนจินใช้นับจำนวนวัตถุทั้งหมดใต้ prefab หรือใช้เรียก destroy() แบบเรียกซ้ำกับโหนดหนึ่งและทุกอย่างที่อยู่ใต้มัน ก่อนจะคืนหน่วยความจำ

หมายเหตุเรื่อง minimax tree recursion โผล่มาอีกครั้งใน AI ของเกม minimax สำรวจต้นไม้ของการเดินหมากในอนาคตของเกม เหมือนกับที่ fib สำรวจต้นไม้ของปัญหาย่อยของมันเป๊ะ ๆ — แตกกิ่งทุกชั้น (ply) — เพียงแต่แต่ละชั้นสลับกันระหว่างการเลือกค่า max จากคะแนนของลูก (ตาเดินของเรา) กับ min (ตาเดินของคู่ต่อสู้) มันสืบทอดการระเบิดแบบเอ็กซ์โพเนนเชียลเดียวกับ fib แบบไร้เดียงสาเป๊ะ ๆ ด้วยเหตุผลเดียวกัน: ต้นไม้มีขนาด O(bᵈ) เมื่อ b คือ branching factor และ d คือความลึกของการค้นหา คำตอบของ AI ในเกมไม่ใช่ memoization (เพราะตำแหน่งกระดานแทบไม่ซ้ำกันเป๊ะ ๆ) แต่เป็นแนวคิดลูกพี่ลูกน้องกัน — alpha-beta pruning ตัดกิ่งที่พิสูจน์ได้ว่าไม่มีทางเปลี่ยนผลลัพธ์ทิ้งไป และการจำกัดความลึกแบบตายตัวคือการยอมแลกคำตอบที่สมบูรณ์แบบ กับคำตอบที่คืนค่าทันเวลาก่อนงบเฟรมจะหมด

ลองลากวิดเจ็ตด้านบน แล้วจินตนาการว่าแต่ละชั้นสลับ max/min แทนที่จะเป็นการบวก — รูปทรงของการแตกกิ่งและการระเบิดเหมือนเดิมทุกอย่าง ต่างกันแค่สิ่งที่เกิดขึ้นในแต่ละโหนด

แบบฝึกหัด

๑. ไล่รอยการทาสี กำหนดห้องนี้ (. = พื้น, # = กำแพง) และ flood_fill(grid, 0, 0, '.', '*') เรียกซ้ำตามลำดับ ขวา → ซ้าย → ลง → ขึ้น จงเรียงลำดับช่องตามที่มันถูกทาสี

. . #
. # .
. . .

เฉลย

(0,0) → (1,0) → (0,1) → (0,2) → (1,2) → (2,2) → (2,1) — พื้นทั้งเจ็ดช่องตามลำดับนี้ จาก (0,0) การเดินไปทางขวาถึง (1,0) ซึ่งเป็นทางตัน (ขวาเป็นกำแพง ซ้ายไปแล้ว ลงเป็นกำแพง ขึ้นหลุดขอบแผนที่) จึงย้อนกลับแล้วลงจาก (0,0) แทน แล้วมุดอ้อมกำแพงที่ (1,1) ลงไปทางขวาจนไปถึง (2,1) จากด้านบน

๒. หา base case ทั้งสามแบบ ใช้ห้องเดิมและโค้ด flood_fill ด้านบน จงยกตัวอย่างการเรียก (x, y) ที่เป็นรูปธรรมหนึ่งตัวอย่างสำหรับ base case แต่ละแบบในสามแบบ

เฉลย

หลุดขอบแผนที่: เช่น (3, 0) หรือ (-1, 1) สีไม่ตรง: (2, 0) ซึ่งเป็น # ไปแล้ว: เรียก flood_fill(grid, 0, 0, ...) ซ้ำอีกครั้งหลังจากขั้นตอนที่ 1 มาร์ก (0,0) ว่าไปแล้ว

๓. นับจำนวนการเรียก flood_fill จะยิงการเรียกซ้ำครบทั้งสี่ทิศทุกครั้งหลังจากทาสีช่องหนึ่ง ไม่ว่าช่องข้างเคียงเหล่านั้นจะถูกต้องหรือไม่ ถ้าเริ่มบนห้องโล่งไม่มีกำแพงขนาด w × h จะมีการเรียก flood_fill ทั้งหมดกี่ครั้ง (รวมครั้งที่เจอ base case ทันที) ในรูปของ w และ h ลองคำนวณสำหรับห้องขนาด 3×4

เฉลย

ทุกช่องในจำนวน w·h ช่องจะถูกทาสีเพียงครั้งเดียว และแต่ละครั้งจะยิงการเรียกต่ออีก 4 ครั้งเสมอ ดังนั้นจำนวนการเรียกทั้งหมด = 1 + 4·w·h (+1 คือการเรียกครั้งแรกสุด) สำหรับห้อง 3×4: 1 + 4·12 = 49 ครั้ง ในจำนวนนี้มีเพียง 12 ครั้งที่ทาสีจริง ส่วนอีก 37 ครั้งเจอ base case ทันที

๔. ทำไมถึง crash ผู้ทดสอบรายงานว่าเจอ RecursionError บนห้องหมอกสงครามที่โล่งกว้างมาก แต่ไม่เจอบนห้องเขาวงกตเล็ก ๆ ที่มีกำแพงเยอะ ทั้งที่บางกรณีเขาวงกตมีช่องที่ไปถึงได้รวมมากกว่าด้วยซ้ำ อะไรคือตัวกำหนดความลึกของการเรียกซ้ำจริง ๆ ถ้าไม่ใช่จำนวนช่อง

เฉลย

ความลึกวัดตามความยาวของ สายการเรียกที่ยาวที่สุดก่อนจะย้อนกลับครั้งแรก — พูดง่าย ๆ คือ DFS มุดลึกไปทิศทางเดียวได้ไกลแค่ไหนก่อนจะหมดช่องข้างเคียงใหม่ ห้องโล่งกว้างเปิดโอกาสให้การเดินคดเคี้ยวไปทั่วทั้งพื้นที่เป็นสายเดียวยาว ๆ (ความลึกอาจเข้าใกล้จำนวนช่องทั้งหมด) ในขณะที่เขาวงกตที่มีกำแพงเยอะบังคับให้ย้อนกลับบ่อย ๆ ทำให้สายการเรียกใด ๆ สั้นอยู่เสมอ แม้พื้นที่ที่ไปถึงได้รวมจะใกล้เคียงกัน นี่คือเหตุผลที่ “หลีกเลี่ยงการเรียกซ้ำลึกบนพื้นที่ใหญ่” จริง ๆ แล้วหมายถึง “หลีกเลี่ยงการเรียกซ้ำที่ความลึกแปรผันตามขนาดพื้นที่” ไม่ใช่ “หลีกเลี่ยงการเรียกซ้ำบนพื้นที่ที่มีช่องเยอะ”

โจทย์ท้าทาย

ก. การเชื่อมต่อแบบทแยงมุม เขียน flood fill ใหม่ให้เชื่อมต่อแบบ 8 ทิศ (รวมแนวทแยง) แทนที่จะเป็น 4 ทิศ — มีประโยชน์กับเกม match-3 ที่กลุ่มเจมซึ่งอยู่ติดกันแบบทแยงมุมควรนับเป็นกลุ่มเดียว

แนวทาง

แทนที่การเรียกซ้ำสี่ครั้งที่ฮาร์ดโค้ดไว้ด้วยลูปวนผ่านออฟเซ็ตแปดทิศ:

DIRS_8 = [(1, 0), (-1, 0), (0, 1), (0, -1),
          (1, 1), (1, -1), (-1, 1), (-1, -1)]

def flood_fill_8(grid, x, y, target, replacement, visited=None):
    if visited is None:
        visited = set()
    height, width = len(grid), len(grid[0])
    if not (0 <= x < width and 0 <= y < height):
        return
    if (x, y) in visited or grid[y][x] != target:
        return
    visited.add((x, y))
    grid[y][x] = replacement
    for dx, dy in DIRS_8:
        flood_fill_8(grid, x + dx, y + dy, target, replacement, visited)

การเลือกวิธีเชื่อมต่อเป็นการตัดสินใจเชิงดีไซน์ ไม่ใช่แค่เชิงเทคนิค: สองช่องที่อยู่ติดกันแบบทแยงมุมข้ามมุมของกำแพง จะ “เชื่อมต่อกัน” ภายใต้การเชื่อมต่อ 8 ทิศ แต่ไม่เชื่อมต่อกันภายใต้ 4 ทิศ ซึ่งมีผลต่อว่าแสง, การเผยฝ้า, หรือกลุ่มเจมใน match-3 จะได้รับอนุญาตให้ “รั่ว” ผ่านมุมแบบทแยงหรือไม่

ข. แปลงเป็นวนซ้ำทีละวง การเผยฝ้าหมอกสงครามไม่ควร crash เลย และควรขยายตัวออกด้านนอกเหมือนรัศมีที่โตขึ้นตามเวลา ไม่ใช่มุดไม่สม่ำเสมอไปทิศทางเดียวแบบที่การเรียกซ้ำ depth-first ทำ จงแปลง flood_fill เป็นเวอร์ชันวนซ้ำที่ทั้งเลี่ยง stack overflow และ ทาสีช่องตามลำดับวงที่ขยายออก

แนวทาง

สลับจากสแตก (LIFO) เป็นคิว (FIFO) — การเดินแบบ breadth-first จะเยี่ยมทุกช่องที่ระยะ d จากเมล็ดพันธุ์ก่อนช่องที่ระยะ d + 1 เสมอ ซึ่งตรงกับลำดับ “วง” ที่แอนิเมชันการเผยฝ้าต้องการเป๊ะ ๆ:

from collections import deque

def flood_fill_bfs(grid, x, y, target, replacement):
    height, width = len(grid), len(grid[0])
    queue = deque([(x, y)])
    seen = {(x, y)}
    while queue:
        cx, cy = queue.popleft()
        if grid[cy][cx] != target:
            continue
        grid[cy][cx] = replacement
        for nx, ny in ((cx + 1, cy), (cx - 1, cy), (cx, cy + 1), (cx, cy - 1)):
            if 0 <= nx < width and 0 <= ny < height and (nx, ny) not in seen:
                seen.add((nx, ny))
                queue.append((nx, ny))

ความลึกของสแตกตอนนี้เป็น O(1) เสมอ ไม่ว่าห้องจะรูปทรงอย่างไร และเพราะ deque ขยายบน heap แผนที่ล้านช่องก็ไม่อันตรายไปกว่าแผนที่สิบช่อง ถ้าจะทำแอนิเมชันการเผยฝ้า ให้ดึงคิวออกทีละวง (ประมวลผลทุกอย่างที่อยู่ในคิว ณ ขณะนั้นก่อนดึงสิ่งที่ถูกเพิ่มเข้ามารอบนี้) แล้ว render หนึ่งเฟรมระหว่างแต่ละวง

เจาะลึกเพิ่มเติม

• MIT 6.0001 — Introduction to Computer Science and Programming in Python (OCW) — บทว่าด้วย recursion และ dictionaries อธิบาย base/recursive case อย่างค่อยเป็นค่อยไป
• MIT 6.006 — Introduction to Algorithms (OCW) — เจาะลึก divide and conquer, merge sort, การวิเคราะห์ความซับซ้อน
• Harvard CS50x — สัปดาห์ว่าด้วย recursion พร้อมตัวอย่างภาพประกอบ call stack ที่เข้าใจง่าย
• Stanford CS106B — Programming Abstractions — หน่วยว่าด้วย recursion และ recursive backtracking อย่างละเอียด
• CLRS — Introduction to Algorithms, บทที่ 4 — Divide-and-Conquer และการแก้ recurrence relation ด้วย master theorem ซึ่งเป็นเครื่องมือทางการสำหรับวิเคราะห์การเรียกซ้ำแบบแตกกิ่งในบทเรียนนี้
• Sedgewick & Wayne — Algorithms, 4th ed. — โค้ด mergesort และ quicksort ที่เขียนได้สะอาด ทำให้แพทเทิร์น divide-and-conquer จับต้องได้เป็นรูปธรรมในโค้ดจริง
• Bhargava — Grokking Algorithms, 2nd ed. — บทว่าด้วย recursion เป็นหนึ่งในคำอธิบายที่เข้าใจง่ายที่สุดสำหรับผู้เริ่มต้น มีภาพประกอบ call stack และ “leap of faith” ที่ดีมาก
• Roughgarden — Algorithms Illuminated, Part 1 — อธิบาย recurrence และ master method อย่างรัดกุมแต่เข้าถึงง่าย เข้ากันดีกับ CLRS บทที่ 4