อัลกอริทึม Python

คำนวณแฟกทอเรียลแบบเรียกตัวเองใน Python

ในบทเรียนนี้ คุณจะเขียนฟังก์ชันเรียกตัวเองเพื่อคำนวณแฟกทอเรียล และเข้าใจบทบาทของกรณีฐาน

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

บทนำ

ปัญหาที่ต้องแก้

บางโจทย์อธิบายได้ง่ายที่สุดด้วยโจทย์แบบเดียวกันที่เล็กกว่า เช่น ในโฟลเดอร์มีโฟลเดอร์ย่อย ในแผนผังครอบครัวมีแผนผังครอบครัวที่เล็กกว่า และ n! คือ n คูณ (n - 1)! recursion (การเรียกซ้ำ) ช่วยให้เราเขียนโค้ดตามนิยามแบบนี้ได้ตรง ๆ

ลองนึกภาพแบบนี้

Recursion เหมือนคนที่ยืนต่อแถวกันแล้วส่งคำถามต่อ ๆ กันไป อยากรู้ค่า 6! คนแรกจะถามคนถัดไปว่า 5! เท่ากับเท่าไร แล้วยืนรอ คนนั้นก็ถามต่อเรื่อง 4! ไปเรื่อย ๆ จนถึงคนที่ถูกถามเรื่อง 1! ซึ่งตอบได้ทันที จากนั้นคำตอบจะถูกส่งย้อนกลับมาตามแถว และแต่ละคนก็คูณตัวเลขของตัวเองเข้าไป

จากคนต่อแถวสู่โค้ด
factorial(6)🙋 คนแรก: 6 × คำตอบที่กำลังรออยู่
number * factorial(number - 1)➡️ ถามคนถัดไปด้วยคำถามเดิม แต่ใช้เลขที่เล็กลง
if number <= 1: return 1🛑 คนสุดท้ายตอบได้ทันที: 1
720⬅️ คำตอบส่งย้อนกลับมาตามแถว: 720
การเรียกแต่ละครั้งรอคำตอบจากการเรียกที่เล็กกว่า จนกว่า base case จะตอบได้ทันที
สรุปในประโยคเดียว

ฟังก์ชันแบบเรียกซ้ำจะเรียกตัวเองด้วยอินพุตที่เล็กลงเรื่อย ๆ จนถึง base case (กรณีฐาน) ที่ตอบได้ทันที ในตัวอย่างนี้ factorial(n) = n × factorial(n - 1) และ factorial(1) = 1

ประเด็นสำคัญ

  1. if number <= 1: return 1 คือ base case ถ้าไม่มีบรรทัดนี้ การเรียกจะไม่มีวันหยุด
  2. return number * factorial(number - 1) เรียกฟังก์ชันเดิมด้วยตัวเลขที่เล็กลง
  3. factorial(6) รอ factorial(5) ซึ่งรอ factorial(4) ลงไปจนถึง factorial(1)
  4. raise ValueError(...) ไม่รับตัวเลขติดลบ เพราะถ้ารับไว้ จะไม่มีวันถึง base case

ใช้เมื่อไร?

  • โจทย์ที่นิยามด้วยโจทย์แบบเดียวกันที่เล็กกว่า เช่น ต้นไม้ โฟลเดอร์ ข้อมูลที่ซ้อนกัน
  • อัลกอริทึมแบบแบ่งแยกและเอาชนะ เช่น merge sort
  • เรียนรู้ว่า call stack ทำงานอย่างไร

เมื่อไรยังไม่จำเป็น

  • งานวนซ้ำง่าย ๆ อย่าง factorial ในโค้ดจริง: ลูปหรือ math.factorial เร็วกว่าและไม่มีขีดจำกัดความลึก
  • อินพุตที่ทำให้เรียกซ้อนลึกมาก: Python จะหยุดเมื่อเรียกซ้อนกันประมาณ 1,000 ชั้น และแจ้ง RecursionError

ดูการทำงาน

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

โค้ดตัวอย่าง

รันโค้ด →
main.py
def factorial(number):
    if number < 0:
        raise ValueError("Factorial is undefined for negative numbers")
    if number <= 1:
        return 1
    return number * factorial(number - 1)

print(factorial(6))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

720

อธิบายโค้ด

เมื่อ number เป็น 0 หรือ 1 ฟังก์ชันจะคืน 1 ทันที นี่คือกรณีฐานที่ป้องกันไม่ให้การเรียกตัวเองดำเนินไปไม่สิ้นสุด สำหรับค่าอื่น ฟังก์ชันคืน number คูณด้วย factorial(number - 1) การเรียกตัวเองแต่ละครั้งจะซ้อนอยู่บนสแตกการเรียก (call stack) ความลึกของการเรียกตัวเองจึงเป็น O(n)

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

ข้อผิดพลาดที่พบบ่อย

ลืม base case

ฟังก์ชันเรียกตัวเองไปเรื่อย ๆ จน Python แจ้ง RecursionError

ปัญหา
def factorial(number):
    return number * factorial(number - 1)
วิธีแก้
def factorial(number):
    if number <= 1:
        return 1
    return number * factorial(number - 1)

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด