ข้ามไปยังเนื้อหาหลัก
Editor
ThePythonBookby pythoncompiler.io

Recursion ใน Python: หลักการทำงาน เมื่อไรควรใช้ และตัวอย่าง

ปานกลาง25 นาที6 แบบฝึกหัด85 XP

บทเรียนนี้แปลจากต้นฉบับภาษาอังกฤษRead in EnglishLeer en españolЧитать на русскомLer em portuguêsแจ้งข้อผิดพลาดในการแปล

ก่อนเริ่มเรียน
ฟังก์ชันใน Python: นิยาม เรียกใช้ และคืนค่า
0/6 แบบฝึกหัด

ลองนึกถึงตุ๊กตาแม่ลูกดกของรัสเซีย คุณเปิดตัวที่ใหญ่ที่สุดแล้วเจอตัวที่เล็กกว่าอยู่ข้างใน เปิดตัวนั้นก็เจอตัวที่เล็กลงไปอีก คุณเปิดไปเรื่อย ๆ จนเจอตัวที่เล็กที่สุดซึ่งเปิดไม่ได้แล้ว นั่นคือจุดสิ้นสุด

การเรียกซ้ำ (recursion) ทำงานแบบเดียวกัน ฟังก์ชันแบบเรียกซ้ำจะเรียกตัวเองด้วยโจทย์ที่เล็กลง ซ้ำแล้วซ้ำอีก จนกว่าจะถึงจุดหยุด นี่คือหนึ่งในเทคนิคที่สวยงามที่สุดในการเขียนโปรแกรม และเมื่อเข้าใจแล้ว คุณจะเห็นมันอยู่ทุกที่

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

การเรียกซ้ำคืออะไร

การเรียกซ้ำคือการที่ฟังก์ชันเรียกตัวเอง นิยามมีแค่นั้น แต่ทำไมเราถึงอยากให้ฟังก์ชันเรียกตัวเองล่ะ

ลองนึกถึงการนับถอยหลังจาก 5 คุณอธิบายขั้นตอนได้แบบนี้ "การนับถอยหลังจาก N ให้พูด N แล้วนับถอยหลังจาก N ลบ 1 หยุดเมื่อถึง 0" นี่คือคำอธิบายแบบเรียกซ้ำ เพราะคำสั่งอ้างถึงตัวเอง

การนับถอยหลังแบบเรียกซ้ำอย่างง่าย
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(5)
ผลลัพธ์
5
4
3
2
1
Go!

ฟังก์ชัน countdown(5) แสดง 5 แล้วเรียก countdown(4) ซึ่งแสดง 4 แล้วเรียก countdown(3) เป็นแบบนี้ไปเรื่อย ๆ จนถึง countdown(0) ที่แสดง "Go!" แล้วหยุด ไม่มีการเรียกต่ออีก

ฟังก์ชันแบบเรียกซ้ำทุกตัวมีส่วนสำคัญสองส่วน ถ้าขาดส่วนใดส่วนหนึ่ง ฟังก์ชันจะทำงานไปตลอดกาล (หรือจนกว่า Python จะหยุดมัน)

กรณีฐาน: จุดที่ต้องหยุด

กรณีฐาน (base case) คือเงื่อนไขที่หยุดการเรียกซ้ำ เปรียบได้กับตุ๊กตาตัวที่เล็กที่สุดซึ่งเปิดไม่ได้ ถ้าไม่มีกรณีฐาน ฟังก์ชันจะเรียกตัวเองไปตลอดกาล

กรณีเรียกซ้ำ (recursive case) คือส่วนที่ฟังก์ชันเรียกตัวเองด้วยอินพุตที่ง่ายลง การเรียกแต่ละครั้งควรพาเข้าใกล้กรณีฐานมากขึ้น

กรณีฐานกับกรณีเรียกซ้ำ
def countdown(n):
# BASE CASE - the stopping condition
if n == 0:
print("Go!")
return
# RECURSIVE CASE - do work, then call with smaller input
print(n)
countdown(n - 1)
countdown(3)
ผลลัพธ์
3
2
1
Go!

หลักง่าย ๆ ที่ควรจำ: เขียนกรณีฐาน ก่อน เสมอ แล้วจึงเขียนกรณีเรียกซ้ำที่เคลื่อนเข้าหากรณีฐาน ลำดับนี้ช่วยกันไม่ให้คุณลืมเงื่อนไขทางออกโดยไม่ได้ตั้งใจ

Call stack ทำงานอย่างไร

เมื่อฟังก์ชันเรียกตัวเอง Python ไม่ได้ลืมว่ากำลังทำอะไรค้างอยู่ แต่ใช้ call stack (สแตกการเรียกฟังก์ชัน) ซึ่งเป็นกองของ "เฟรม" โดยแต่ละเฟรมจำตัวแปรภายในของฟังก์ชันและตำแหน่งที่จะกลับมาทำงานต่อ

ลองนึกถึงกองกระดาษโน้ตแบบแปะ ทุกครั้งที่เรียกฟังก์ชัน Python จะเขียนโน้ตแผ่นใหม่พร้อมรายละเอียดของการเรียกครั้งนั้นแล้ววางไว้บนสุด เมื่อฟังก์ชันคืนค่า Python จะดึงโน้ตแผ่นบนสุดออกแล้วกลับไปที่แผ่นข้างใต้

ดู call stack ขณะทำงาน
def factorial(n):
print(f" Calling factorial({n})")
if n <= 1:
print(f" Base case! factorial({n}) = 1")
return 1
result = n * factorial(n - 1)
print(f" factorial({n}) = {n} * factorial({n-1}) = {result}")
return result
print("Result:", factorial(5))
ผลลัพธ์
  Calling factorial(5)
  Calling factorial(4)
  Calling factorial(3)
  Calling factorial(2)
  Calling factorial(1)
  Base case! factorial(1) = 1
  factorial(2) = 2 * factorial(1) = 2
  factorial(3) = 3 * factorial(2) = 6
  factorial(4) = 4 * factorial(3) = 24
  factorial(5) = 5 * factorial(4) = 120
Result: 120

สังเกตว่าข้อความ "Calling" ลึกลงไปเรื่อย ๆ แล้วผลลัพธ์ก็ค่อย ๆ ส่งกลับขึ้นมา call stack โตขึ้นเมื่อมีการเรียกเข้าไป แล้วหดลงเมื่อผลลัพธ์ส่งกลับออกมา จังหวะ "เข้าแล้วออก" แบบนี้คือหัวใจของการเรียกซ้ำ

ตัวอย่างคลาสสิกของการเรียกซ้ำ

แฟกทอเรียล

แฟกทอเรียล (factorial) ของจำนวน N (เขียนว่า N!) คือ N คูณกับจำนวนเต็มบวกทุกตัวที่น้อยกว่ามัน ตัวอย่างเช่น 5! = 5 x 4 x 3 x 2 x 1 = 120

แฟกทอเรียลมีโครงสร้างแบบเรียกซ้ำโดยธรรมชาติ: 5! = 5 x 4! และ 4! = 4 x 3! ไปเรื่อย ๆ กรณีฐานคือ 1! = 1

แฟกทอเรียลด้วยการเรียกซ้ำ
def factorial(n):
if n <= 1: # Base case
return 1
return n * factorial(n - 1) # Recursive case
print(factorial(1)) # 1
print(factorial(5)) # 120
print(factorial(10)) # 3628800
ผลลัพธ์
1
120
3628800

ผลรวมของลิสต์

มาดูอีกรูปแบบหนึ่ง การหาผลรวมของลิสต์แบบเรียกซ้ำ ทำได้โดยนำสมาชิกตัวแรกไปบวกกับผลรวมของส่วนที่เหลือ

ผลรวมของลิสต์แบบเรียกซ้ำ
def sum_list(numbers):
if len(numbers) == 0: # Base case: empty list
return 0
return numbers[0] + sum_list(numbers[1:]) # First + sum of rest
print(sum_list([1, 2, 3, 4, 5])) # 15
print(sum_list([10])) # 10
print(sum_list([])) # 0
ผลลัพธ์
15
10
0

รูปแบบคือ จัดการกรณีฐานก่อน (ลิสต์ว่างคืนค่า 0) แล้วแบ่งโจทย์เป็น "สมาชิกตัวแรก" บวก "การเรียกซ้ำกับส่วนที่เหลือ" รูปแบบนี้ใช้ได้กับงานลิสต์อีกหลายอย่าง

การเรียกซ้ำกับลูป: เมื่อไรควรใช้แบบไหน

ทุกอย่างที่ทำได้ด้วยการเรียกซ้ำ ก็ทำได้ด้วยลูปเช่นกัน แล้วเมื่อไรควรเลือกแบบไหน

แฟกทอเรียลแบบเรียกซ้ำ
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 120
แฟกทอเรียลแบบวนซ้ำ (ลูป)
def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result = result * i
    return result

print(factorial(5))  # 120

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

การเรียกซ้ำโดดเด่นเมื่อโจทย์มีโครงสร้างเป็นต้นไม้หรือคล้ายตัวเองโดยธรรมชาติ ตัวอย่างเช่น การสำรวจโครงสร้างโฟลเดอร์ การแยกวิเคราะห์ข้อมูลซ้อนกัน (เช่น JSON หรือ HTML) และการท่องต้นไม้หรือกราฟ ในกรณีเหล่านี้ การเรียกซ้ำให้โค้ดที่สะอาดและสั้นกว่า

เมื่อไรการเรียกซ้ำคือเครื่องมือที่ใช่

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

แผ่ลิสต์ซ้อนกันให้เป็นชั้นเดียวด้วยการเรียกซ้ำ
def flatten(lst):
result = []
for item in lst:
if isinstance(item, list):
result.extend(flatten(item)) # Recursion for nested lists
else:
result.append(item)
return result
nested = [1, [2, 3], [4, [5, 6]], 7]
print(flatten(nested)) # [1, 2, 3, 4, 5, 6, 7]
ผลลัพธ์
[1, 2, 3, 4, 5, 6, 7]

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

ข้อผิดพลาดที่พบบ่อยในการเรียกซ้ำ

ข้อผิดพลาดที่ 1: ไม่มีกรณีฐาน

ต้องมีกรณีฐานเสมอ
# DON'T run this - it would crash!
# def bad_countdown(n):
# print(n)
# bad_countdown(n - 1) # Never stops!
# The fix: add a base case
def good_countdown(n):
if n <= 0:
return
print(n)
good_countdown(n - 1)
good_countdown(5)
ผลลัพธ์
5
4
3
2
1

ข้อผิดพลาดที่ 2: ไม่เคลื่อนเข้าหากรณีฐาน

การเรียกแต่ละครั้งต้องเข้าใกล้กรณีฐานมากขึ้น
# DON'T run this - n never decreases!
# def bad_factorial(n):
# if n <= 1:
# return 1
# return n * bad_factorial(n) # Oops! Should be n - 1
# The fix: make sure the argument changes
def good_factorial(n):
if n <= 1:
return 1
return n * good_factorial(n - 1) # n - 1 moves toward base case
print(good_factorial(5))
ผลลัพธ์
120

แบบฝึกหัด

เริ่มจากข้อที่ง่ายกว่าแล้วค่อย ๆ ไต่ระดับขึ้นไป แต่ละข้อต่อยอดจากสิ่งที่คุณได้เรียนมา อย่าลืม: เขียนกรณีฐานก่อนเสมอ

แบบฝึกหัดที่ 1: ทายผลลัพธ์ของการเรียกซ้ำ
ทายผลลัพธ์

อ่านโค้ดนี้แล้วทายผลลัพธ์ จากนั้นเขียนคำสั่ง print() ที่ให้ผลลัพธ์เหมือนกันทุกตัวอักษร

def mystery(n):
    if n <= 0:
        return
    mystery(n - 1)
    print(n)

mystery(3)

สังเกตว่า print(n) อยู่ หลัง การเรียกซ้ำ คิดเรื่องลำดับให้ดี

# Print the exact output of the code above
แบบฝึกหัดที่ 2: ผลรวม 1 ถึง N แบบเรียกซ้ำ
เขียนโค้ด

เขียนฟังก์ชันแบบเรียกซ้ำชื่อ sum_to ที่รับจำนวนเต็มบวก n แล้วคืนค่าผลรวมของตัวเลขทั้งหมดตั้งแต่ 1 ถึง n

ตัวอย่างเช่น sum_to(5) ควรคืนค่า 1 + 2 + 3 + 4 + 5 = 15

กรณีฐาน: sum_to(1) คืนค่า 1

แสดงผลของ sum_to(5) และ sum_to(10) คนละบรรทัด

def sum_to(n):
# Your code here
pass
print(sum_to(5))
print(sum_to(10))
แบบฝึกหัดที่ 3: ซ่อมฟังก์ชันยกกำลังที่พัง
แก้บั๊ก

ฟังก์ชันแบบเรียกซ้ำนี้ควรคำนวณ base ยกกำลัง exp (เหมือน base ** exp) แต่มีบั๊กอยู่สองจุด

แก้บั๊กทั้งสองจุดให้ได้ผลลัพธ์ดังนี้:

8
1
81
def power(base, exp):
if exp == 0:
return 0
return base + power(base, exp - 1)
print(power(2, 3))
print(power(5, 0))
print(power(3, 4))
แบบฝึกหัดที่ 4: ฟีโบนัชชีแบบเรียกซ้ำ
เขียนโค้ด

เขียนฟังก์ชันแบบเรียกซ้ำชื่อ fibonacci ที่คืนค่าจำนวนฟีโบนัชชีตัวที่ n

ลำดับฟีโบนัชชีเริ่มต้นแบบนี้: 0, 1, 1, 2, 3, 5, 8, 13, ...

กฎ:

  • fibonacci(0) คืนค่า 0
  • fibonacci(1) คืนค่า 1
  • เมื่อ n >= 2: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

    • แสดงผลเมื่อ n = 0, 1, 5 และ 10 คนละบรรทัด

    def fibonacci(n):
    # Your code here
    pass
    print(fibonacci(0))
    print(fibonacci(1))
    print(fibonacci(5))
    print(fibonacci(10))
    แบบฝึกหัดที่ 5: กลับด้านสตริงแบบเรียกซ้ำ
    เขียนโค้ด

    เขียนฟังก์ชันแบบเรียกซ้ำชื่อ reverse ที่รับสตริงแล้วคืนค่าสตริงนั้นแบบกลับด้าน

    ตัวอย่างเช่น reverse("hello") ควรคืนค่า "olleh"

    คำใบ้: ตัวอักษรตัวสุดท้าย บวกกับสตริงกลับด้านของทุกตัวยกเว้นตัวสุดท้าย

    แสดงผลของ reverse("hello") และ reverse("Python") คนละบรรทัด

    def reverse(s):
    # Your code here
    pass
    print(reverse("hello"))
    print(reverse("Python"))
    แบบฝึกหัดที่ 6: นับจำนวนหลักแบบเรียกซ้ำ
    เขียนโค้ด

    เขียนฟังก์ชันแบบเรียกซ้ำชื่อ count_digits ที่รับจำนวนเต็มที่ไม่ติดลบ แล้วคืนค่าจำนวนหลักของตัวเลขนั้น

    ตัวอย่างเช่น:

  • count_digits(0) คืนค่า 1
  • count_digits(5) คืนค่า 1
  • count_digits(123) คืนค่า 3
  • count_digits(99999) คืนค่า 5

    • คำใบ้: การหารด้วย 10 ด้วย // จะตัดหลักสุดท้ายออก

    แสดงผลสำหรับ 0, 5, 123 และ 99999 คนละบรรทัด

    def count_digits(n):
    # Your code here
    pass
    print(count_digits(0))
    print(count_digits(5))
    print(count_digits(123))
    print(count_digits(99999))

    สรุป

    สิ่งที่คุณได้เรียนเกี่ยวกับการเรียกซ้ำ:

    แนวคิดความหมาย
    การเรียกซ้ำ (recursion)ฟังก์ชันที่เรียกตัวเอง
    กรณีฐาน (base case)เงื่อนไขที่หยุดการเรียกซ้ำ
    กรณีเรียกซ้ำ (recursive case)ส่วนที่เรียกตัวเองด้วยอินพุตที่ง่ายลง
    Call stackระบบของ Python ที่ติดตามการเรียกฟังก์ชันที่ซ้อนกัน
    สแตกล้น (stack overflow)สิ่งที่เกิดขึ้นเมื่อการเรียกซ้ำลึกเกินไป (ไม่มีกรณีฐาน)
    การเรียกซ้ำกับลูปลูปสำหรับการทำซ้ำแบบง่าย การเรียกซ้ำสำหรับโจทย์แบบต้นไม้

    กฎทองของการเรียกซ้ำ: เขียนกรณีฐานก่อนเสมอ และตรวจให้แน่ใจว่าการเรียกซ้ำทุกครั้งเคลื่อนเข้าหากรณีฐาน ถ้าทำได้ คุณก็จะเขียนฟังก์ชันแบบเรียกซ้ำได้ทุกแบบ

    เรียนอะไรต่อ

    บทเรียนถัดไปคือ map(), filter() และ reduce() เครื่องมือการเขียนโปรแกรมเชิงฟังก์ชันที่ทรงพลังของ Python คุณจะได้เรียนรู้วิธีแปลง กรอง และรวมชุดข้อมูลในบรรทัดเดียว

    บทเรียนที่เกี่ยวข้อง

    ฟังก์ชัน·เริ่มต้น
    ฟังก์ชันใน Python: นิยาม เรียกใช้ และคืนค่า
    25 นาที6 แบบฝึกหัด
    ฟังก์ชัน·ปานกลาง
    อาร์กิวเมนต์ฟังก์ชันใน Python: *args, **kwargs และค่าเริ่มต้น
    25 นาที7 แบบฝึกหัด
    ฟังก์ชัน·ปานกลาง
    ฟังก์ชัน Lambda ใน Python: ควรใช้เมื่อไร และเมื่อไรไม่ควรใช้
    20 นาที5 แบบฝึกหัด
    ฟังก์ชัน·ปานกลาง
    สโคปของตัวแปร โคลเชอร์ และกฎ LEGB ใน Python
    25 นาที5 แบบฝึกหัด
    โครงสร้างข้อมูล·ปานกลาง
    ข้อมูลซ้อนกันใน Python: ลิสต์ ดิกชันนารี และโครงสร้างซับซ้อน
    25 นาที6 แบบฝึกหัด
    โครงสร้างข้อมูล·ปานกลาง
    copy กับ deepcopy ใน Python: ทำไม "สำเนา" ถึงไม่ใช่สำเนาจริง
    20 นาที5 แบบฝึกหัด

    บทเรียนนี้มีประโยชน์หรือไม่

    เสนอแนะการปรับปรุง