ทำความเข้าใจ Recursion

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Miriam Antona

Software engineer

นิยาม

• ฟังก์ชันเรียกตัวเอง
• ใช้แทนลูปได้เกือบทุกกรณี
  • แทนที่ลูปด้วย recursion
• แก้ปัญหาที่ดูซับซ้อนได้

ตัวอย่าง - แฟกทอเรียล

$n!$

ตัวอย่าง - แฟกทอเรียล

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

120

ตัวอย่าง - แฟกทอเรียลด้วย recursion

$n!= n$ · $(n-1)!$

def factorial_recursion(n):
  return n * factorial_recursion(n-1)

• ทำงานวนซ้ำไม่สิ้นสุด!

ตัวอย่าง - การระบุกรณีฐาน

• เพิ่มเงื่อนไข
  • ป้องกันไม่ให้อัลกอริทึมทำงานวนซ้ำไม่สิ้นสุด
• กรณีฐานของแฟกทอเรียล -> $n=1$

def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120

Recursion ทำงานอย่างไร

• คอมพิวเตอร์ใช้ stack ติดตามการทำงานของฟังก์ชัน
  • Call stack

Recursion ทำงานอย่างไร

• factorial(5) เริ่มทำงาน
• ก่อน factorial(5) เสร็จ -> factorial(4) เริ่มทำงาน
• ก่อน factorial(4) เสร็จ -> factorial(3) เริ่มทำงาน

Recursion ทำงานอย่างไร

• factorial(5) เริ่มทำงาน
• ก่อน factorial(5) เสร็จ -> factorial(4) เริ่มทำงาน
• ก่อน factorial(4) เสร็จ -> factorial(3) เริ่มทำงาน
• ก่อน factorial(3) เสร็จ -> factorial(2) เริ่มทำงาน

Recursion ทำงานอย่างไร

• factorial(5) เริ่มทำงาน
• ก่อน factorial(5) เสร็จ -> factorial(4) เริ่มทำงาน
• ก่อน factorial(4) เสร็จ -> factorial(3) เริ่มทำงาน
• ก่อน factorial(3) เสร็จ -> factorial(2) เริ่มทำงาน
• ก่อน factorial(2) เสร็จ -> factorial(1) เริ่มทำงาน

Recursion ทำงานอย่างไร

• factorial(5) เริ่มทำงาน
• ก่อน factorial(5) เสร็จ -> factorial(4) เริ่มทำงาน
• ก่อน factorial(4) เสร็จ -> factorial(3) เริ่มทำงาน
• ก่อน factorial(3) เสร็จ -> factorial(2) เริ่มทำงาน
• ก่อน factorial(2) เสร็จ -> factorial(1) เริ่มทำงาน

Recursion ทำงานอย่างไร

• factorial(1) เสร็จสิ้น
  • คืนค่า 1
• factorial(2) เสร็จสิ้น

Recursion ทำงานอย่างไร

• factorial(1) เสร็จสิ้น
  • คืนค่า 1
• factorial(2) เสร็จสิ้น
  • คืนค่า 2

Recursion ทำงานอย่างไร

• factorial(1) เสร็จสิ้น
  • คืนค่า 1
• factorial(2) เสร็จสิ้น
  • คืนค่า 2
• factorial(3) เสร็จสิ้น
  • คืนค่า 6

Recursion ทำงานอย่างไร

• factorial(1) เสร็จสิ้น
  • คืนค่า 1
• factorial(2) เสร็จสิ้น
  • คืนค่า 2
• factorial(3) เสร็จสิ้น
  • คืนค่า 6
• factorial(4) เสร็จสิ้น
  • คืนค่า 24

Recursion ทำงานอย่างไร

• factorial(1) เสร็จสิ้น
  • คืนค่า 1
• factorial(2) เสร็จสิ้น
  • คืนค่า 2
• factorial(3) เสร็จสิ้น
  • คืนค่า 6
• factorial(4) เสร็จสิ้น
  • คืนค่า 24
• factorial(5) เสร็จสิ้น
  • คืนค่า 120

Recursion ทำงานอย่างไร

• factorial(1) เสร็จสิ้น
  • คืนค่า 1
• factorial(2) เสร็จสิ้น
  • คืนค่า 2
• factorial(3) เสร็จสิ้น
  • คืนค่า 6
• factorial(4) เสร็จสิ้น
  • คืนค่า 24
• factorial(5) เสร็จสิ้น
  • คืนค่า 120

Dynamic programming

• เทคนิคการปรับให้เหมาะสม
• ใช้กับ recursion เป็นหลัก
• ลดความซับซ้อนของอัลกอริทึมแบบ recursive ได้
• ใช้กับ:
  • ปัญหาที่แบ่งเป็นปัญหาย่อยได้
  • ปัญหาย่อยมีส่วนซ้อนทับกัน
• บันทึกผลลัพธ์ของปัญหาย่อยไว้ ไม่ต้องคำนวณซ้ำ
  • Memoization

มาฝึกกันเถอะ!

โครงสร้างข้อมูลและอัลกอริทึมใน Python