Recursion คืออะไร — หลักการทำงาน ตัวอย่าง และ Base Case

Recursion ในคณิตศาสตร์หมายถึงการนิยามฟังก์ชัน ลำดับ หรือกระบวนการ โดยใช้กรณีที่เล็กกว่าของแนวคิดเดียวกัน นิยามแบบเวียนเกิดจะใช้ได้ก็ต่อเมื่อมี base case และมีกฎที่ทำให้แต่ละกรณีใหม่เคลื่อนไปหา base case นั้น

ถ้าต้องการใจความสำคัญที่สุด ก็คือ recursion จะหมดประโยชน์ทันทีเมื่อกฎการลดลงทีละขั้นไม่สามารถพาไปถึงจุดหยุดที่ถูกต้องได้

Recursion ในคณิตศาสตร์หมายถึงอะไร

นิยามแบบเวียนเกิดไม่ได้แจกแจงทุกกรณีแยกกันทั้งหมด แต่จะให้จุดเริ่มต้นและกฎสำหรับสร้างกรณีที่ใหญ่ขึ้นจากกรณีที่เล็กกว่า

สิ่งนี้ต่างจากสูตรแบบตรง สูตรแบบตรงให้คำตอบจากอินพุตได้ในนิพจน์เดียว ส่วนนิยามแบบเวียนเกิดจะค่อย ๆ ลดปัญหาทีละขั้นจนไปถึงกรณีที่รู้คำตอบอยู่แล้ว

ทำไมจึงต้องมี base case

base case คือจุดหยุด หากไม่มีมัน นิยามจะอ้างถึงกรณีที่เล็กลงเรื่อย ๆ โดยไม่มีวันจบ

นอกจากนี้ base case ยังต้องสอดคล้องกับกฎที่เลือกใช้ด้วย ถ้าขั้นตอนเวียนเกิดลดจาก $n$ ไปเป็น $n-1$ base case ก็ต้องเป็นกรณีที่เข้าถึงได้จากรูปแบบนั้นสำหรับอินพุตที่อนุญาต

ตัวอย่างแบบละเอียด: recursion ของแฟกทอเรียล

แฟกทอเรียลเป็นนิยามแบบเวียนเกิดมาตรฐาน สำหรับจำนวนเต็มไม่ลบ $n \ge 0$ นิยามแฟกทอเรียลได้ว่า

$$0! = 1$$

และสำหรับ $n \ge 1$,

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

ในที่นี้ $0! = 1$ คือ base case และ $n! = n(n-1)!$ คือขั้นตอนเวียนเกิด

ถ้าต้องการหา $4!$ ให้ลดรูปต่อไปจนกว่า base case จะปรากฏ:

$$4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!$$

จากนั้นใช้ base case $0! = 1$:

$$4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$$

นี่คือรูปแบบเต็มของ recursion: ลดไปสู่กรณีที่เล็กกว่า ไปถึง base case แล้วจึงคำนวณย้อนกลับไปยังคำถามเดิม

Recursion กับ recurrence relation ต่างกันอย่างไร

Recursion เป็นแนวคิดที่กว้างกว่า ส่วน recurrence relation คือกฎแบบเวียนเกิดสำหรับลำดับ โดยที่แต่ละพจน์ขึ้นอยู่กับพจน์ก่อนหน้า

ตัวอย่างเช่น ลำดับฟีโบนัชชีถูกกำหนดด้วย recurrence เพราะแต่ละพจน์นิยามจากพจน์ก่อนหน้า แฟกทอเรียลก็เป็นแบบเวียนเกิดเช่นกัน แต่โดยทั่วไปมักนำเสนอเป็นนิยามแบบเวียนเกิดของฟังก์ชัน มากกว่าจะเป็น recurrence ของลำดับ

ข้อผิดพลาดที่พบบ่อยเกี่ยวกับ recursion

ลืมใส่ base case

ถ้าไม่มี base case นิยามก็จะไม่สิ้นสุด

ใช้ขั้นตอนที่ไม่ได้ทำให้เล็กลง

ถ้าขั้นตอนเวียนเกิดไม่ได้พาเข้าใกล้ base case กระบวนการอาจวนไม่รู้จบ หรือไม่สามารถนิยามได้สำหรับอินพุตบางค่า

ลืมเงื่อนไขของกฎ

ในตัวอย่างแฟกทอเรียล กฎ $n! = n(n-1)!$ ใช้เมื่อ $n \ge 1$ เท่านั้น เงื่อนไขนี้สำคัญมาก หากไม่มีเงื่อนไขนี้ คุณอาจพยายามใช้กฎในจุดที่นิยามไม่ได้ตั้งใจให้ใช้

คิดว่า recursion เป็นเรื่องของการเขียนโปรแกรมเท่านั้น

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

เมื่อไร recursion จึงมีประโยชน์

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

มันมีประโยชน์เป็นพิเศษเมื่อกรณีที่เล็กกว่ายังคงมีโครงสร้างแบบเดียวกับปัญหาเดิม ถ้ากรณีที่เล็กกว่าไม่ได้เป็นปัญหาชนิดเดียวกันจริง ๆ recursion ก็มักไม่ใช่เครื่องมือที่เหมาะสม

วิธีทดสอบอย่างเร็วว่านิยามแบบเวียนเกิดสมเหตุสมผลหรือไม่

ให้ถาม 2 คำถาม:

1. ฉันมี base case หรือไม่?
2. แต่ละขั้นตอนเวียนเกิดพาเข้าใกล้มันมากขึ้นหรือไม่?

ถ้าคำตอบข้อใดข้อหนึ่งเป็นไม่ใช่ นิยามนั้นยังต้องแก้ไข

ลองทำโจทย์ที่คล้ายกัน

กำหนดลำดับโดย

$$a_1 = 2, \qquad a_n = a_{n-1} + 3 \quad \text{for } n \ge 2$$

จากนั้นหา $a_2$, $a_3$ และ $a_4$ นี่เป็นวิธีฝึกอย่างรวดเร็วในการสังเกต base case และขั้นตอนเวียนเกิดในบริบทใหม่