เข้าใจ Recursion ใน 1 นาที

“ณ ร้านอาหารแห่งหนึ่งคุณกำลังต่อคิวเพื่อที่จะซื้อข้าวเช้า แต่ด้วยความที่คิวยาวมาก คุณจึงอยากรู้ว่า ‘เราอยู่คิวที่เท่าไหร่?’”

คำถามคือเราจะแก้ปัญหานี้ยังไง?

วิธีการนึงเลยที่เราทำได้ก็คือการ “ถามคนข้างหน้าด้วยคำถามเดียวกัน” ครับว่า “อยู่คิวที่เท่าไหร่?” แล้วพอได้คำตอบมาก็ +1

…แต่ประเด็นคือคนข้างหน้าก็ไม่รู้เหมือนกัน ก็เลยถามคนด้านหน้าต่อไปอีกว่า “อยู่คิวที่เท่าไหร่?”

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

เราเชื่อว่าจากตัวอย่างข้างต้นทุกคนน่าจะเห็น pattern บางอย่างใช่ไหมครับ …ว่าคำตอบของคำถามของเรา ขึ้นอยู่กับคำตอบของ “คำถามเดียวกัน” ที่เราถามคนก่อนหน้า

หรือถ้าสรุปออกมาเป็นประโยคเดียวคงจะเขียนได้ว่า:

เรา ‘คิวที่เราไหร่?’ = คนก่อนหน้า ‘คิวที่เราไหร่?’ + 1

(และในกรณีที่คนหน้าสุดอยู่คิวแรก คำตอบของคำถามนี้ก็คือ “1”)

โดยสรุปแล้ว สิ่งนี้ก็คือ “recursive definition” ซึ่งประกอบไปด้วย

1. Recursive case คือเคสที่เรานิยามสิ่ง ๆ หนึ่งโดยอ้างอิงถึงอีกสิ่ง ‘ที่มีหน้าตาเหมือนตัวมันเองในเวอร์ชั่นก่อนหน้าหรือเวอร์ชั่นที่เล็กกว่า’
2. และ Base case คือเคสสิ้นสุด เป็นเคสที่นิยามของเรา ‘ไม่ได้ขึ้นอยู่กับสิ่งที่มีหน้าตาเหมือนกับตัวเองอีกแล้ว’

โดย “recursive definition” ก็คือประโยคที่เราใช้ในการอธิบาย “recursion” หรือ process ทั้งหมดที่เกิดขึ้นนั่นเอง