บทความ IT เจ๋งๆ

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

ก่อนอื่น เรามาเริ่มต้นกันที่ function invocation หรือ การเรียกใช้งาน function กันก่อน

Function invocation

เมื่อเราเรียกใช้ function, execution context จะถูกวางไว้ใน execution stack

แต่ก่อนอื่นเรามาทำความรู้จัก stack กันก่อนว่า Stack คืออะไร? Stack เป็นโครงสร้างข้อมูล (Data Structure) ที่ทำงานแบบ "Last In, First Out" โดย item ต่างๆ จะถูกใส่เพิ่มไปบน stack เรื่อยๆ จากนั้น item จะถูกดึงออกจาก stack ดังนั้น การใช้ stack จึงเป็นวิธีการหนึ่งที่ใช้เพื่อจัดลำดับในการ execution นั่นเอง

คราวนี้กลับมาต่อกันว่า execution context คืออะไร execution context จะสร้างขึ้นจากการเรียกใช้ function ซึ่ง context นี้จะอยู่ใน execution stack ตามลำดับของการ operations โดย item แรกใน stack จะถือเป็น global execution context เสมอ ส่วน item ถัดๆ ไปจะเป็น contexts ที่ function สร้างขึ้น

หลักการของ recursion จะเป็นการรอ return value ที่มาจาก execution context อื่นๆ ซึ่ง contexts เหล่านี้จะอยู่ด้านบนของ stack เมื่อ item สุดท้ายบน stack ถูก execution เสร็จแล้ว context จะทำการ generate ตัว return value ซึ่ง return value นี้จะถูกส่งผ่านไปให้ยัง item ถัดไป จากนั้น execution context ก็จะถูกดึงออกไปจาก stack

Recursion คืออะไร

recursive function เป็น function ที่เรียกใช้ตัวเองจนกว่า "base condition" จะเป็น True แล้วถึงจะหยุดการ execution

กรณีที่ยังเป็น False อยู่ เราจะเก็บ execution contexts ไว้ด้านบนของ stack ก่อน ซึ่งเหตุการณ์นี้อาจนำไปสู่การเกิด “stack overflow” ได้ (stack overflow เกิดขึ้นเมื่อเราของใช้ memory จนเต็มนั่นเอง) โดยทั่วไป recursive function จะประกอบด้วยอย่างน้อย 2 ส่วนคือ base condition และ recursive case อย่างน้อย 1 case ซึ่งคุณสามารถลองดูได้จากตัวอย่างนี้:

Factorial

นี่เป็นการหาค่าของ 5! (5 factorial) นั่นเอง

เงื่อนไขแรก ระบุว่า "ถ้า parameter ส่งผ่านค่า 0 หรือ 1 เราจะออกจาก function และ return ค่า 1"

ต่อไป recursive case ระบุว่า: "ถ้า parameter ไม่ใช่ 0 หรือ 1 ก็จะส่งค่าจำนวนครั้งของ num และ return ค่าของการเรียกใช้ function นี้อีกครั้งด้วย num-1 เป็น argument

ดังนั้น ถ้าเราเรียก factorial(0) function จะ return ค่า 1 และไม่เข้ากรณีของ recursive case ซึ่งเป็นเช่นเดียวกับ factorial(1)

เราสามารถดูสิ่งที่เกิดขึ้นได้ หากเราแทรก debugger statement เข้าไปใน code และใช้ devtools เพื่อดูขั้นตอนทั้งหมดและดูการเรียกใช้ stack

1. execution stack ใส่ factorial() ด้วย 5 เป็น argument ที่ส่งผ่าน, base case เป็น False, ดังนั้นจึงเข้าสู่ recursive condition
2. execution stack ใส่ factorial() เป็นครั้งที่ 2 ด้วย num – 1 ซึ่งเท่ากับ 4 เป็น argument, base case เป็น False จึงเข้าสู่ recursive condition
3. execution stack ใส่ factorial() เป็นครั้งที่ 3 ด้วย num – 1 ซึ่งเท่ากับ 3 เป็น argument, base case เป็น False จึงเข้าสู่ recursive condition
4. execution stack ใส่ factorial() เป็นครั้งที่ 4 ด้วย num – 1 ซึ่งเท่ากับ 2 เป็น argument, base case เป็น False จึงเข้าสู่ recursive condition
5. execution stack ใส่ factorial() เป็นครั้งที่ 5 ด้วย num – 1 ซึ่งเท่ากับ 1 เป็น argument, base case เป็น True จึง return ค่า 1

ณ จุดนี้ เราได้ลด argument ลงทีละ 1 ในแต่ละการเรียกใช้ function จนกว่าจะเข้าเงื่อนไขที่ return ค่า 1

1. จากตรงนี้ execution context ล่าสุดเสร็จสิ้นแล้ว, num === 1, ดังนั้น function จึง returns 1
2. ถัดไปเป็น num === 2, ดังนั้น return value จึงเป็น 2 ซึ่งเกิดจาก (1×2)
3. ถัดไปเป็น num === 3, ดังนั้น return value จึงเป็น 6 ซึ่งเกิดจาก (2×3) ซึ่งจนถึงตอนนี้เรามี 1x2x3
4. ถัดไปเป็น num === 4, ดังนั้น return value จึงเป็น 24 ซึ่งเกิดจาก (6×4)
5. ท้ายสุด num === 5 ซึ่งเราจะได้ 120 โดยเกิดจาก 24x5 เป็นคำตอบสุดท้ายนั่นเอง

นอกจากนี้เราก็สามารถทำสิ่งเดียวกันกับ for หรือ while loop ได้ ซึ่งการใช้ recursion จะทำให้ได้ Solution ที่ดูงดงามแต่ขณะเดียวกันมันก็ยังอ่านได้ง่ายขึ้นด้วย ซึ่งนี่คือเหตุผลที่เราใช้ recursive ในการแก้ปัญหา

ในหลายๆ ครั้ง การที่เราแบ่งปัญหาให้เป็นส่วนต่างๆ ที่มีขนาดเล็กลงจะช่วยให้เราแก้ไขมันได้อย่างมีประสิทธิภทพมากขึ้น ดังนั้น recursion จึงเป็นการใช้รูปแบบ divide-and-conquer ในการแก้ไขปัญหา

• ปัญหาย่อยๆ สามารถแก้ไขได้ง่ายกว่า ปัญหาใหญ่ๆ
• ผลของการแก้ปัญหาย่อยๆ เมื่อนำมารวมกัน สามารถนำไปสู่การแก้ไขปัญหาใหญ่ได้

"Divide-and-chinhquer" มักถูกใช้งานบ่อย เพื่อสำรวจหรือค้นหา Data Structures เช่น binary search trees, graphs และ heaps นอกจากนี้ยังใช้หลายๆ sorting algorithms อีกด้วย เช่น quicksort และ heapsort

ลองดูการใช้งานผ่านตัวอย่างต่างๆ ต่อไปนี้ คุณสามารถใช้ devtools เพื่อดูให้เข้าใจเกี่ยวกับแนวคิดว่า เกิดอะไรขึ้น ที่ไหน และเมื่อใด รวมทั้งอย่าลืมใช้ debugger statements เพื่อดูขั้นตอนต่างๆ ในแต่ละ process ด้วย

Fibonacci

Recursive arrays

Reversing a string

Quicksort

การฝึกฝนการใช้ recursive เทคนิคนั้น ถือเป็นเรื่องสำคัญ เพราะสำหรับ nested data structures อย่างเช่น trees, graphs และ heaps แล้ว recursion ถือเป็นสิ่งที่สำคัญมาก

หากคุณสนใจอ่านเพิ่มเติมเกี่ยวกับ Recursion ลองดูจาก resource เหล่านี้:

Wikipedia

Software Engineering

Another good article

M.I.T. open courseware

ที่มา:  https://medium.freecodecamp.org/

รับตำแหน่งงานไอทีใหม่ๆ ด้วยบริการ IT Job Alert

อัพเดทบทความจากคนวงในสายไอทีทาง LINE ก่อนใคร
อย่าลืมแอดไลน์ @techstarth เป็นเพื่อนนะคะ

บทความที่เกี่ยวข้อง

• 4 เคล็ดลับ ช่วยทำให้ Security Incident Response ของคุณดีขึ้น
• เปิดตัว! หนังสือ PMBOKv6 ฉบับตีพิมพ์ภาษาไทย 
• 6 วิชาที่ยากที่สุดใน Computer Science