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

ในบทความนี้ จะกล่าวถึงสถานการณ์ว่า เมื่อใดควรใช้ Loop และเมื่อใดควรใช้ Recursion ซึ่งจะขอยกตัวอย่าง เป็นการใช้งานใน Python 3 แต่ก็สามารถนำไปปรับใช้ในภาษา Programming อื่น ๆ ได้เช่นกัน

ในการแก้ไขปัญหาเรื่องของการวน/การทำซ้ำ (Iteration) ของ Python จะกล่าวถึงการใช้ For หรือ While Loop ซึ่งเป็นเครื่องมือทั่วไปที่มักใช้กันในการแก้ไขปัญหาในภาษา Programming ต่าง ๆ การที่ Loop คือสิ่งที่ยอดเยี่ยมมาก ก็เพราะในหลาย ๆ ครั้ง การใช้งานของมันนั้นค่อนข้างง่ายและตรงไปตรงมา แต่บางครั้งที่มันอาจเป็นปัญหาในเรื่องของการอ่านและการทำความเข้าใจ

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

Loop คืออะไร

Loop ถูกใช้เพื่อแสดง Block ของ Code ที่เกิดขึ้นอย่างซ้ำ ๆ ใน Program

สำหรับ For Loop (อย่างที่แสดงในตัวอย่างด้านบน) เป็นการกระทำแบบซ้ำ ๆ โดยทั่วไปเราใช้ For Loop เมื่อเรารู้ว่า เราต้อง Execute Block ของ Code เป็นจำนวนกี่ครั้ง ในตัวอย่างข้างต้น เราเพียงแค่จำเป็นต้องทำในบรรทัดที่ 2 และ 3 สำหรับจำนวนชื่อใน name_list  

เมื่อเราจำเป็นต้องใช้ Loop กับจำนวนครั้งที่ระบุไม่ได้ หรือจนกว่าจะบรรลุเงื่อนไขบางอย่าง กรณีนี้เราอาจต้องใช้ While Loop

วิธีหนึ่งในการ Return ความยาวของ Linked List ที่ไม่มีการทำซ้ำ อาจเกี่ยวข้องกับการใช้ While Loop เพื่อสำรวจ Node ทั้งหมดเช่นในตัวอย่างด้านบน

แล้ว Recursion ล่ะ คืออะไร

ความแตกต่างที่สำคัญระหว่าง Recursion และ Iteration ก็คือ การสิ้นสุดของพวกมัน ขณะที่ Loop ทำการ Execute Block ของ Code อยู่ มันจะตรวจสอบทุกครั้งเพื่อดูว่า มันอยู่ในลำดับสุดท้ายหรือยัง แต่สำหรับ Recursive Code จะไม่มีลำดับที่สิ้นสุด นั่นหมายถึง อาจมี Recursive Function ที่ทำไปเรื่อย ๆ อย่างไม่มีที่สิ้นสุด โดยไม่มีเงื่อนไขที่จะทำให้มันหลุดออกจากการวนซ้ำได้เลย

Recursive Function ตามที่เห็นด้านบน ประกอบด้วย 2 ส่วนคือ Recursive Call และ Base Case

สำหรับ Base Case เป็นเงื่อนไขที่ตรวจสอบเพื่อดูว่า เราได้รับข้อมูลที่ทำให้เราสามารถออกจาก Function ได้หรือยัง และทุก ๆ Recursive Function ควรมีอย่างน้อย 1 Base Case (อาจมีได้มากกว่า 1) โดยจากตัวอย่างเรื่อง Factorial ที่คุณเห็นด้านบน เราจะพบกับจุดสิ้นสุดของ Recursive Calls เมื่อเราไปถึงหมายเลข 0

ส่วน Recursive Call คือเมื่อ Function มีการเรียกตัวเอง มันจะเพิ่มไปยัง Recursive Call Stack โดย Stack ก็คือ LIFO (Last In First Out) Objects ซึ่งหมายความว่า Item สุดท้ายที่ถูกเพิ่มมาที่ด้านบนของ Stack จะเป็น Item แรกที่จะถูก Remove ออกจาก Stack

เมื่อไรที่ควรใช้ Recursion

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

ตัวอย่างที่ดีของเรื่องนี้ คือการ Search ผ่าน File System คุณสามารถเริ่มต้นที่ Root Folder จากนั้นคุณสามารถ Search ทุก File และ Folder ทั้งหมดที่อยู่ภายใน Folder นั้น หลังจากนั้น คุณจะเข้าไปในแต่ละ Folder แล้ว Search ในแต่ละ Folder ที่อยู่ภายในนั้นอีก

Recursion ทำงานได้ดี สำหรับ Structure ประเภทนี้ เนื่องจากคุณสามารถ Search เส้นทางที่แตกกิ่งก้านสาขาไปได้มากมายได้โดยที่ไม่ต้องมาตรวจสอบและเช็คเงื่อนไขต่าง ๆ ที่เป็นไปได้

สำหรับคนที่คุ้นเคยกับ Data Structures คุณอาจสังเกตเห็นว่า ภาพด้านบนของ File System ดูเหมือนกับ Tree Structure เป็นอย่างมาก ซึ่ง Trees และ Graphs ก็เป็นอีกเรื่องที่เหมาะสมที่สุดกับการใช้ Recursion และเป็นวิธีที่ง่ายที่สุดในการสำรวจเส้นทาง (Traversal)

ควรใช้ Recursion เสมอไปหรือไม่

Recursion ดูเหมือนว่า จะมีประโยชน์มากก็จริง แต่เราควรจะใช้มันทุกครั้งหรือไม่?

Recursion เป็นเครื่องมือที่มีประโยชน์มาก แต่ขณะเดียวกัน มันก็เพิ่มการใช้งานของ Memory ได้เช่นกัน

เรากลับไปที่ภาพ Factorial Call Stack ที่ด้านบนกันอีกครั้ง ทุกครั้งที่เราเพิ่มการ Call ใหม่ไปยัง Stack นั่นหมายถึง เรากำลังเพิ่มจำนวนของ Memory ที่เราต้องใช้งาน หากเราวิเคราะห์ Algorithm โดยใช้ Big O Notation เราอาจสังเกตได้ว่า นี่เป็นการเพิ่ม Space Complexity ของเราอยู่

มีบางครั้ง ที่เราอาจต้องยอมให้เกิดสิ่งนี้เพื่อให้ได้ Algorithm ที่สั้นและมีประโยชน์ เช่นเดียวกับที่เราสำรวจ Tree นั่นเอง แต่บางทีก็อาจมีวิธีที่ดีกว่าและมีประสิทธิภาพมากกว่านี้ในการแก้ไขปัญหา

สำหรับ Project ขนาดเล็ก Call Stack จะไม่สร้างปัญหากับ Program ของคุณมากนัก อย่างไรก็ตามเมื่อ Program ของคุณเริ่มสร้าง Recursive Call ซ้ำหลาย ๆ ครั้ง คุณอาจต้องพิจารณาถึงผลกระทบที่อาจเกิดขึ้นจาก Call Stack ที่มีขนาดใหญ่ของคุณ

สิ่งที่ต้องพิจารณาอีกเรื่อง ก็คือ การทำความเข้าใจและอ่าน Code ของคุณ อาจง่ายกว่าการทำใน Iterative Solution

การใช้ Recursion เป็นสิ่งที่ดี เพราะมันจะทำให้เรามีปัญหาที่ถูกย่อยให้เล็กลงมากขึ้น แต่เมื่อคุณพยายามที่จะทำความเข้าใจกับปัญหาย่อยที่คุณกำลังแก้ไข และวิธีที่พวกมันกำลังแก้ไขอยู่ มันอาจจะคุ้มค่าที่จะใช้วิธี Iterative Solution มากกว่า หากนี่ไม่ใช่แนวทางที่เป็นไปได้ อย่างน้อยที่สุดก็ให้สร้างแผนภาพของ Recursive Process ภายใน Code ของคุณ เพื่อที่คุณจะได้เห็นมันได้ลึกซึ้งมากยิ่งขึ้น

ที่มา:  https://medium.com/