Recursion — ฟังก์ชันที่เรียกตัวเอง

Recursion คือฟังก์ชันที่เรียกตัวเองเพื่อแก้ปัญหาย่อยที่เล็กลงเรื่อย ๆ เป็นแนวคิดที่ทรงพลังและสวยงาม ใช้กับปัญหาที่มีโครงสร้างซ้ำตัวเอง เช่น tree, graph, การแบ่งย่อย เป็นพื้นฐานของหลายอัลกอริทึมขั้นสูง

สองส่วนที่ขาดไม่ได้

ทุกฟังก์ชัน recursion ต้องมี 2 ส่วนเสมอ ขาดข้อใดข้อหนึ่งจะวนไม่จบ

• Base case — เงื่อนไขหยุด เคสเล็กสุดที่ตอบได้เลยโดยไม่ต้องเรียกตัวเองอีก
• Recursive case — เรียกตัวเองด้วยปัญหาที่ "เล็กลง" เข้าใกล้ base case

# factorial: 5! = 5*4*3*2*1
def factorial(n):
    if n <= 1:               # base case — หยุด
        return 1
    return n * factorial(n - 1)  # recursive case (n เล็กลง)

print(factorial(5))  # 120
# ขยาย: 5*factorial(4) = 5*4*factorial(3) = ... = 5*4*3*2*1

วิธีคิด recursion ให้ออก

เคล็ดลับ: อย่าพยายามไล่ตามทุกชั้นในหัว ให้ "เชื่อ" ว่าฟังก์ชันแก้ปัญหาเล็กกว่าได้ถูกต้องแล้ว (เรียกว่า leap of faith) จากนั้นถามแค่ 2 ข้อ

1. เคสเล็กสุดคืออะไร และตอบว่าอะไร? (base case)
2. ถ้าฉันมีคำตอบของปัญหาที่เล็กกว่า 1 ขั้น ฉันจะประกอบเป็นคำตอบของปัญหาเต็มได้อย่างไร? (recursive case)

# ผลรวมของลิสต์แบบ recursion
def sum_list(nums):
    if not nums:             # base: ลิสต์ว่าง = 0
        return 0
    return nums[0] + sum_list(nums[1:])  # ตัวแรก + ผลรวมที่เหลือ

print(sum_list([1, 2, 3, 4]))  # 10

# กลับข้อความ
def reverse(s):
    if len(s) <= 1:
        return s
    return reverse(s[1:]) + s[0]
print(reverse("hello"))  # olleh

ตัวอย่างคลาสสิก: Fibonacci

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

print([fib(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

from functools import lru_cache

@lru_cache(maxsize=None)   # จำผลลัพธ์อัตโนมัติ
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))  # 12586269025  (เร็วมากเพราะไม่คำนวณซ้ำ)

Recursion vs Loop

หลายปัญหาเขียนได้ทั้งสองแบบ loop มักเร็วกว่าและใช้ memory น้อยกว่า ส่วน recursion อ่านง่ายกว่าสำหรับปัญหาที่มีโครงสร้างซ้ำตัวเอง (tree, graph, การแบ่งย่อย) เลือกตามความเหมาะสม

สรุปหัวข้อนี้

• Recursion = ฟังก์ชันเรียกตัวเอง ต้องมี base case (หยุด) และ recursive case (เล็กลง)
• วิธีคิด: เชื่อว่าฟังก์ชันแก้ปัญหาเล็กกว่าได้ แล้วประกอบคำตอบ
• ลืม base case → RecursionError
• ปัญหาที่คำนวณซ้ำ (เช่น fibonacci) ใช้ memoization (@lru_cache) ช่วยให้เร็วขึ้นมาก
• Recursion อ่านง่ายกับปัญหาโครงสร้างซ้ำตัวเอง, loop เร็วและประหยัด memory กว่า