On this page
โจทย์ Recursion
ฝึกคิดแบบเรียกตัวเอง — หา base case, แบ่งเป็นปัญหาเล็กลง แล้วเชื่อว่ามันแก้ได้
Recursion เป็นแนวคิดที่ต้องฝึกจนชิน โจทย์ชุดนี้เรียงจากง่ายไปยาก ทุกข้อให้ถาม 2 คำถามเสมอ: (1) base case คืออะไร (2) จะแบ่งเป็นปัญหาเล็กลงอย่างไร อย่าพยายามไล่ตามทุกชั้นในหัว
ทุกฟังก์ชัน recursion ต้องมี base case (จุดหยุด) และ recursive case (เรียกตัวเองด้วยปัญหาที่เล็กลง) ลืม base case = RecursionError วนไม่จบ
ข้อ 1 — factorial 🟢
คำนวณ n! ด้วย recursion (ไม่ใช้ loop) เช่น 5! = 120
เฉลย + คำอธิบาย
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
print(factorial(5)) # 120base case: 0! และ 1! = 1 (หยุด) recursive case: n! = n × (n-1)! ขยาย: 5×factorial(4) = 5×4×factorial(3) = ... = 5×4×3×2×1 จุดสำคัญคือ n-1 ทำให้เข้าใกล้ base case ทุกครั้ง
ข้อ 2 — ผลรวมลิสต์ 🟢
หาผลรวมของลิสต์ด้วย recursion เช่น [1,2,3,4] → 10
เฉลย + คำอธิบาย
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วิธีคิด: ผลรวมของลิสต์ = สมาชิกตัวแรก + ผลรวมของลิสต์ที่เหลือ (nums[1:]) ปัญหาเล็กลงเรื่อย ๆ จนเหลือลิสต์ว่าง (base case = 0) เชื่อว่า sum_list ของส่วนที่เหลือถูกต้อง แล้วแค่บวกตัวแรกเข้าไป
ข้อ 3 — Fibonacci 🟡
หา fibonacci ตัวที่ n (0,1,1,2,3,5,8,...) ทำทั้งแบบธรรมดาและแบบเพิ่ม cache ให้เร็วขึ้น
เฉลย + คำอธิบาย
def fib(n):
if n <= 1:
return n # base: fib(0)=0, fib(1)=1
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]
# เร็วขึ้นมากด้วย cache
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_fast(n):
if n <= 1:
return n
return fib_fast(n - 1) + fib_fast(n - 2)
print(fib_fast(50)) # 12586269025 (เร็ว)fib แบบธรรมดาคำนวณค่าซ้ำมหาศาล (O(2ⁿ)) เช่น fib(5) เรียก fib(3) หลายครั้ง @lru_cache จำผลที่เคยคำนวณ ไม่ต้องคิดซ้ำ ทำให้ fib(50) ทันที นี่คือไอเดียพื้นฐานของ Dynamic Programming
ข้อ 4 — พาลินโดรมด้วย recursion 🟡
เช็คว่าข้อความเป็นพาลินโดรมไหม โดยใช้ recursion (ไม่ใช้ slice [::-1])
เฉลย + คำอธิบาย
def is_palindrome(s):
if len(s) <= 1: # base: ว่างหรือตัวเดียว = ใช่
return True
if s[0] != s[-1]: # หัวกับท้ายไม่ตรง = ไม่ใช่
return False
return is_palindrome(s[1:-1]) # เช็คส่วนในต่อ
print(is_palindrome("level")) # True
print(is_palindrome("hello")) # Falseวิธีคิด: ข้อความเป็นพาลินโดรมถ้า ตัวหน้า = ตัวท้าย และ ส่วนตรงกลาง (s[1:-1]) ก็เป็นพาลินโดรม ลอกเปลือกออกทีละชั้นจนเหลือ 0–1 ตัว (base case) นี่คือ recursion เวอร์ชันของเทคนิค two pointers
ข้อ 5 — Power 🔴
คำนวณ base ยกกำลัง exp ด้วย recursion ให้มีประสิทธิภาพ O(log n) เช่น power(2, 10) = 1024
เฉลย + คำอธิบาย
def power(base, exp):
if exp == 0:
return 1 # base case: x^0 = 1
half = power(base, exp // 2)
if exp % 2 == 0:
return half * half # x^exp = (x^(exp/2))^2
else:
return half * half * base
print(power(2, 10)) # 1024เคล็ดลับ O(log n): แทนที่จะคูณ base ทีละครั้ง n รอบ เราหาร exp ครึ่งทุกครั้ง เพราะ x^10 = (x^5)² คำนวณ x^5 ครั้งเดียวแล้วยกกำลังสอง ทำให้จำนวนการเรียกลดลงครึ่งทุกชั้น — แนวคิดเดียวกับ binary search
ลองเขียน recursion: นับสมาชิกในลิสต์ (ไม่ใช้ len), กลับข้อความ, หาค่ามากสุดในลิสต์, แปลงเลขเป็นฐานสอง การฝึก recursion เยอะ ๆ จะช่วยมากตอนเจอโจทย์ tree และ graph ในการเตรียมสัมภาษณ์