ขั้น ตอน วิธี Algorithm ใน ข้อ ใด ทำให้ เกิด การ สลับ ค่าของ ตัวแปร x กับ ตัวแปร y

ฟังก์ชันเวียนบังเกิด (recursive function) คือ ฟังก์ชันที่เรียกตัวเอง
หลักการฟังก์ชันเวียนบังเกิดคือ เขียนโปรแกรมวนซ้ำเพื่อลดปัญหาของโปรแกรมที่ซับซ้อน

สารบัญ Show

• วิธีการเขียน recursive แบบง่าย ๆ คือ
• การนำไปใช้
• Depth First Search
• Divide and Conquer
• โจทย์ปัญหา
• Balanced Parentheses Problem
• The Maze Problem
• Pass by Value and Pass by Reference
• สรุป

พูดง่าย ๆ แบบให้คนทั่วไปเข้าใจคือ การเขียนฟังก์ชันมาตัวนึง ถ้ายังหาคำตอบไม่ได้ก็ให้เรียกตัวเองซ้ำไปเรื่อย ๆ จนกว่าจะเจอคำตอบ

วิธีการเขียน recursive แบบง่าย ๆ คือ

• ทำความเข้าใจโจทย์
• หาจุดวนกลับ (Initial condition หรือบางคนเรียก Base case)
• หาขั้นตอนที่ต้องเรียกซ้ำ

ส่วนตัวไม่เคยเขียน recursive function จะเขียนเป็น Iterative ตลอด ดังนั้นผมจะ
ยกตัวอย่างการเขียน recursive กับ Iterative ให้ดูในการเขียนฟังก์ชันหา Fibonacci
(ทั้งหมดจะเขียนด้วย Python นะครับ)

ในกรณีตัวอย่างคือเมื่อ n = 0 และ n = 1 ทำให้ fibonacci ที่ 0,1 เป็นค่า 0,1 ตามลำดับ หากต้องการแก้ให้ fibonacci ที่ 0 เป็นค่า 1 ก็ทำการ return เป็น 1 แทน การทำแบบนี้ทำให้ฟังก์ชันนี้ไม่วนลูป infinity และสามารถได้คำตอบออกมา

การเขียน Iterative ก็เหมือนกับการเขียนโปรแกรมทั่ว ๆ ไป คือเขียนตามเงื่อนไขที่ต้องการได้เลย อย่างในตัวอย่างนี้ก็ใช้การวนลูป

การนำไปใช้

ในบางปัญหานั้นการเขียนแบบ Iterative เพื่อหาผลลัพธ์นั้นยุ่งยากจนเกินไป การเขียน recursive สามารถลดความยุ่งยากเหล่านั้นได้ โดยตอนนี้มีอัลกอริทึมหลายอย่างที่ใช้ recursive ในการหาคำตอบ เช่น Depth First Search, Divide and Conquer

Depth First Search

การค้นหาแบบลึกก่อน(Depth first search) (DFS) เป็นการค้นหาที่กําหนดทิศทางจากรูปของโครงสร้างต้นไม้ ที่เริ่มต้นจากโหนดราก (Root node) ที่อยู่บนสุด แล้วเดินลงมาให้ลึกที่สุด เมื่อถึงโหนดล่างสุด (Terminal node) ให้ย้อนขึ้นมาที่จุดสูงสุดของกิ่งเดี่ยวกันที่มีกิ่งแยกและยังไม่ได้เดินผ่าน แล้วเริ่มเดินลงจนถึงโหนดลึกสุดอีก ทําเช่นนี้สลับไปเรื่อยจนพบโหนดที่ต้องการหาหรือสํารวจครบทุกโหนด

Divide and Conquer

Divide คือการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อย ๆ อย่างน้อย 2 ส่วน
(ใช้เทคนิค Recursive)

Conquer คือการนำเอา solution ของแต่ละส่วนที่ได้นั้นมารวมกัน เพื่อให้ได้ solution สุดท้าย

ถ้าให้ยกตัวอย่าง Divide and Conquer ก็คงจะเป็น Merge sort, Quick sort หลาย ๆคนคงรู้จักกันเป็นอย่างดี

Merge Sort

Merge sort เป็นการ sort ข้อมูล ด้วยการแบ่ง ข้อมูลออกเป็นสองส่วนแล้วจึง sort ข้อมูลในแต่ละส่วน หลังจากนั้นจึงเอาข้อมูลทั้งสองส่วนมารวมกันตามตำแหน่งที่เหมาะสมของข้อมูลแต่ละตัว (merge) ทำการแบ่งและ merge ไปจนกว่าข้อมูลอยู่ในตำแหน่งที่ถูกต้อง

จะเห็นได้ว่ามี 2 ส่วนการทำงานคือ แบ่งตัวเลขออกเป็น 2 ส่วนไปเรื่อย ๆ จนถึงตัวสุดท้าย (ใช้หลักการ DFS) กับ การจัดเรียงตัวเลข

ฟังก์ชัน mergeSort คือส่วนของ Divide ทำหน้าที่แบ่งครึ่ง
ฟังก์ชัน popmin คือส่วนของ Conquer ทำหน้าที่เรียงตัวเลขจากน้อยไปมาก

Diagram แสดงการทำงานโดยประมาณนะครับ โดย recursion แบ่งครึ่งจนเหลือแค่หลักเดียวแล้วถึงทำการเรียงลำดับจากน้อยไปมากไปเรื่อย ๆ

Quick Sort

Quick Sort ก็คือแบ่งข้อมูลออกเป็นสองส่วนแล้วเรียกตัวเองขึ้นมา sort ข้อมูลสองส่วนนี้ Quick sort จะเลือกข้อมูลหนึ่งตัว (pivot) สำหรับใช้ในการแบ่งข้อมูล ถ้าข้อมูลตัวหนึ่งซึ่งเมื่อนำมาเปรียบเทียบข้อมูลที่เลือกไว้นี้มีค่าน้อยกว่าเราจะเก็บข้อมูลนี้ไว้ใน sub-array ตัวหนึ่ง (left) แต่ถ้ามากกว่าเราก็เก็บไว้อีกตัวหนึ่ง (right) แล้วก็ sort ข้อมูลเหล่านี้จนกว่าข้อมูลใน sub-array ทุกตัวอยู่ในตำแหน่งที่เหมาะสม

กำหนด 3 ค่าคือ low(ค่าแรก), pivot(ค่ากลาง), high(ค่าสุดท้าย) เมื่อเรียงในรอบครึ่งหนึ่งเสร็จ 1 รอบก็จะมีการกำหนดค่า pivot ใหม่เรียก recursive function เช็คทั้งครึ่งซ้ายและขวา

ตัวอย่างนี้มีการเกิด Divide and Conquer ทุกครั้งที่จบในครึ่งใดครึ่งหนึ่งต่อการเรียกใช้ recursion รอบหนึ่งและทำไปเรื่อย ๆ จนค่าเรียงน้อยไปมาก

โจทย์ปัญหา

หลังจากลองแก้ปัญหาด้วย recursive function แล้ว ต่อไปลองโจทย์ที่ยากขึ้นมาอีกระดับหนึ่งกับโจทย์ Balanced parentheses problem, The Maze problem

Balanced Parentheses Problem

โจทย์คือให้หาคำตอบของทุกความเป็นไปได้ที่ทำให้วงเล็บเปิด-ปิดมีจำนวน n ทั้งเปิด-ปิด และต้องให้วงเล็บหันเข้าหากัน

ก่อนจะเขียนโปรแกรม มาทำความเข้าใจก่อนว่าจะเขียนออกมาในแบบ recursive ออกมาได้ยังไงด้วยการสร้าง Diagram ของผลลัพธ์มาซักตัวอย่าง

เอามาเขียนโค้ดก็จะได้ประมาณนี้

The Maze Problem

หาเส้นทางไปยังเป้าหมาย โดยให้ได้ผลลัพธ์ทุกความเป็นไปได้ของการไปยังเป้าหมาย

• 0 คือเส้นทางที่สามารถเดินได้
• 1 คือกำแพงไม่สามารถข้ามได้
• 2 คือเส้นทางที่เดิน
• 3 คือ เป้าหมาย
• 4 คือ จุดเริ่มต้น

ถ้าสังเกตจากโค้ดจะเห็นว่าผมใช้ copy.deepcopy(maze) ในการเพิ่มผลลัพธ์จากการ recursion หลังจากที่พบ 1 เส้นทาง เนื่องจากเป็นการเพิ่มค่าของ List นั้นเป็น Pass by Referenceดังนั้นผมขอนอกเรื่องไปพูดถึง Pass by Value และ Pass by Reference

Pass by Value and Pass by Reference

Pass by Value คือ การ copy ค่าที่ผู้เรียกใช้ฟังก์ชันส่งให้กับฟังก์ชัน ไปยังตัวแปรแบบ local ในฟังก์ชัน
Primitive Data Type เป็นการ Pass by Value

Pass by Reference คือ การส่งค่าไปยังฟังก์ชั่นที่ถูกเรียกใช้โดยส่งเป็นค่าตำแหน่งที่อยู่ (Address) ของตัวแปรไปซึ่งหากภายในฟังก์ชันมีการเปลี่ยนแปลงค่าของอาร์กิวเมนต์ที่ส่งไป ก็จะมีผลทำให้ค่าของ อาร์กิวเมนต์นั้นในโปรแกรมที่เรียกใช้เปลี่ยน ไปด้วย
Reference Type อย่าง Object เป็นการ Pass by Reference (บางภาษา Pass by Value)

มีการส่งตัวแปร maze ไปทุกครั้งที่เกิด recursion อย่างที่บอกว่า List คือ Object ชนิดหนึ่งมันจึงเป็นการ Pass by reference ดังนั้นหากเกิด recursion อีก ตัวแปร maze เปลี่ยนค่าภายใน นั่นหมายความว่าค่า maze ที่ส่งเก็บไว้ในตัวแปร result ก็เปลี่ยนไปด้วยเช่นกัน

สรุป

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

จบแล้วนะครับ หวังว่าจะช่วยให้เข้าใจเรื่อง recursive function มากขึ้น หากข้อมูลตรงไหนผิดพลาดก็บอกได้ครับ จะทำการแก้ไขทันที