คำนวณแฟกทอเรียลแบบเรียกตัวเองใน Python
ในบทเรียนนี้ คุณจะเขียนฟังก์ชันเรียกตัวเองเพื่อคำนวณแฟกทอเรียล และเข้าใจบทบาทของกรณีฐาน
บทนำ
ปัญหาที่ต้องแก้
บางโจทย์อธิบายได้ง่ายที่สุดด้วยโจทย์แบบเดียวกันที่เล็กกว่า เช่น ในโฟลเดอร์มีโฟลเดอร์ย่อย ในแผนผังครอบครัวมีแผนผังครอบครัวที่เล็กกว่า และ n! คือ n คูณ (n - 1)! recursion (การเรียกซ้ำ) ช่วยให้เราเขียนโค้ดตามนิยามแบบนี้ได้ตรง ๆ
ลองนึกภาพแบบนี้
Recursion เหมือนคนที่ยืนต่อแถวกันแล้วส่งคำถามต่อ ๆ กันไป อยากรู้ค่า 6! คนแรกจะถามคนถัดไปว่า 5! เท่ากับเท่าไร แล้วยืนรอ คนนั้นก็ถามต่อเรื่อง 4! ไปเรื่อย ๆ จนถึงคนที่ถูกถามเรื่อง 1! ซึ่งตอบได้ทันที จากนั้นคำตอบจะถูกส่งย้อนกลับมาตามแถว และแต่ละคนก็คูณตัวเลขของตัวเองเข้าไป
factorial(6)🙋 คนแรก: 6 × คำตอบที่กำลังรออยู่number * factorial(number - 1)➡️ ถามคนถัดไปด้วยคำถามเดิม แต่ใช้เลขที่เล็กลงif number <= 1: return 1🛑 คนสุดท้ายตอบได้ทันที: 1720⬅️ คำตอบส่งย้อนกลับมาตามแถว: 720ฟังก์ชันแบบเรียกซ้ำจะเรียกตัวเองด้วยอินพุตที่เล็กลงเรื่อย ๆ จนถึง base case (กรณีฐาน) ที่ตอบได้ทันที ในตัวอย่างนี้ factorial(n) = n × factorial(n - 1) และ factorial(1) = 1
ประเด็นสำคัญ
if number <= 1: return 1คือ base case ถ้าไม่มีบรรทัดนี้ การเรียกจะไม่มีวันหยุดreturn number * factorial(number - 1)เรียกฟังก์ชันเดิมด้วยตัวเลขที่เล็กลงfactorial(6)รอfactorial(5)ซึ่งรอfactorial(4)ลงไปจนถึงfactorial(1)raise ValueError(...)ไม่รับตัวเลขติดลบ เพราะถ้ารับไว้ จะไม่มีวันถึง base case
ใช้เมื่อไร?
- โจทย์ที่นิยามด้วยโจทย์แบบเดียวกันที่เล็กกว่า เช่น ต้นไม้ โฟลเดอร์ ข้อมูลที่ซ้อนกัน
- อัลกอริทึมแบบแบ่งแยกและเอาชนะ เช่น merge sort
- เรียนรู้ว่า call stack ทำงานอย่างไร
เมื่อไรยังไม่จำเป็น
- งานวนซ้ำง่าย ๆ อย่าง factorial ในโค้ดจริง: ลูปหรือ
math.factorialเร็วกว่าและไม่มีขีดจำกัดความลึก - อินพุตที่ทำให้เรียกซ้อนลึกมาก: Python จะหยุดเมื่อเรียกซ้อนกันประมาณ 1,000 ชั้น และแจ้ง RecursionError
ดูการทำงาน
กด ทีละขั้น เพื่อติดตามแต่ละการเรียก การเรียกใหม่จะถูกวางบน call stack และแต่ละการเรียกจะส่งค่ากลับไปยังผู้เรียก
โค้ดตัวอย่าง
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))
ผลลัพธ์จากการรัน
720
อธิบายโค้ด
เมื่อ number เป็น 0 หรือ 1 ฟังก์ชันจะคืน 1 ทันที นี่คือกรณีฐานที่ป้องกันไม่ให้การเรียกตัวเองดำเนินไปไม่สิ้นสุด สำหรับค่าอื่น ฟังก์ชันคืน number คูณด้วย factorial(number - 1) การเรียกตัวเองแต่ละครั้งจะซ้อนอยู่บนสแตกการเรียก (call stack) ความลึกของการเรียกตัวเองจึงเป็น O(n)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
ลืม 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
- แฟกทอเรียล คูณจำนวนเต็มบวกทั้งหมดตั้งแต่ 1 ถึง n ง่าย
- ยกกำลังแบบเวียนเกิด (Recursive Power) คำนวณการยกกำลังด้วยวิธีเวียนเกิดโดยการหารเลขชี้กำลังครึ่งหนึ่งในแต่ละรอบ ปานกลาง