TECHJAM 2018 — Code Incubation #1

Basics Revisited: Recursion

ทีมงาน TECHJAM ขอต้อนรับผู้อ่านทุกท่านสู่ blog entry แรกของกิจกรรม TECHJAM 2018 — Code Incubation ในกิจกรรมนี้ ทีมงาน TECHJAM และผู้เข้าแข่งขันรอบชิงชนะเลิศใน Code Squad จะมาผลัดกันแลกเปลี่ยนความรู้อันจะเป็นประโยชน์ต่อวงการเทคโนโลยีและการพัฒนาซอฟต์แวร์ในประเทศไทย

เนื่องจากนี่เป็น blog entry แรก เราจะย้อนไปพูดเรื่องที่เบสิกที่สุดของ Programming 101 ก็ว่าได้ นั่นก็คือ Recursion

การคำนวณอนุกรมเลขคณิต (Arithmetic series)

ก่อนอื่นเลย เราขอยกปัญหาเชิงคำนวณง่ายๆ มาลองพิจารณากัน สมมติว่าเราต้องการเขียน function เพื่อคำนวณอนุกรมเลขคณิต F(n) = 0 + 1 + 2 + 3 + … + n โดยที่ n เป็นจำนวนเต็มบวก

แน่นอนว่า หนึ่งในวิธีแก้ปัญหาที่โปรแกรมเมอร์หลายคนน่าจะนึกถึงคือโค้ดที่มีหน้าตาประมาณนี้

ซึ่งเป็นการใช้ loop iteration ที่เรียบง่ายที่สุด

หรือถ้าเป็นมุมมองของนักคณิตศาสตร์ จะมองอนุกรมเลขคณิต F(n) ในรูปแบบของความสัมพันธ์เวียนเกิด (Recurrence relation) ได้ว่า

และเราสามารถแปลงสมการข้างบนเป็นโค้ดคอมพิวเตอร์ได้ดังนี้

หากเราเปรียบเทียบโค้ดทั้ง 2 วิธี อาจจะมีบางคนกล่าวแย้งว่า

ในเมื่อเรามีวิธีแก้ปัญหาเดียวกัน 2 วิธี โดยที่วิธีหนึ่งใช้ loop iteration และอีกวิธีหนึ่งเขียนในรูปของ recursive function ในกรณีแบบนี้เราควรจะใช้ loop iteration หรือเปล่า? ในเมื่อเห็นชัดๆ ว่า
1. โค้ดอ่านง่ายกว่าด้วย
2. ป้องกันปัญหา stack overflow ที่อาจเกิดจาก Recursion depth สูงๆ อีกด้วย!

ซึ่งนั่นก็เป็นข้อสังเกตที่น่าคิดทีเดียว แต่ก่อนที่เราจะยอมรับข้อสังเกตนี้ เรามาลองดูอีกตัวอย่างกันก่อนดีกว่า

การค้นหาแบบทวิภาค (Binary search algorithm)

ทวนความจำกันนิดนึงว่า binary search algorithm คือขั้นตอนวิธีการหาค่า key ที่กำหนดให้จากอาร์เรย ์sorted_values ของข้อมูลที่เรียงลำดับจากน้อยไปมาก

เราสามารถเขียนขั้นตอนวิธีดังกล่าวได้ทั้งในรูปแบบของ loop iteration และ recursive function ได้ดังนี้ (หมายเหตุ: สมมติว่าเราสามารถเปรียบเทียบค่าสองค่าได้ด้วยเครื่องหมาย < และ > )

หากเปรียบเทียบ implementation ทั้งสองแบบข้างต้นนี้ แม้ว่าจะทำงานได้ผลลัพธ์เหมือนกัน แต่เวอร์ชันที่เขียนด้วย recursive function จะใกล้เคียงกับคำบรรยายอัลกอริทึมในภาษามนุษย์มากกว่า อีกทั้งยังสามารถเขียนพิสูจน์ทางคณิตศาสตร์ได้เข้าใจง่ายกว่าอีกด้วย

ฉะนั้นแล้วคำกล่าวว่า “โค้ดที่มีความหมายเดียวกันในรูปแบบ loop iteration นั้นอ่านง่ายกว่าแบบ recursive function” อาจไม่ถูกต้องเสมอไปก็ได้ โค้ดในรูปแบบใดที่อ่านแล้วเข้าใจง่ายกว่านั้นอาจจะแล้วแต่กรณี

“อย่างไรก็ดี หากเราตั้งเป้าว่าประสิทธิภาพการทำงานของโปรแกรมเป็นเรื่องสำคัญ เราจึงควรเลือกเขียนโค้ดในรูปแบบ loop iteration มากกว่าใช้ recursive function อยู่ดี หรือเปล่า?”

ไม่จำเป็นเสมอไปเช่นกัน

ขอแนะนำให้รู้จักกับ Tail call และ Tail call optimization/elimination

• สำหรับ function หนึ่งๆ Tail call คือเหตุการณ์ที่ function นี้ต้องการเรียกใช้งาน subprocedure อื่น โดยที่ subprocedure call นี้เป็น operation สุดท้ายของ function หลักพอดี
  ยกตัวอย่างเช่น recursive_binary_search ที่เป็น recursive call ทั้งสองบรรทัดในโค้ดข้างต้นนั้น ล้วนเป็น Tail call ทั้งสิ้น เพราะว่าเมื่อ subprocedure call ดังกล่าวทำงานเสร็จสิ้น จะเกิดการ return ออกจาก function ทันที จึงกล่าวได้ว่า recursive call เหล่านั้นเป็น operation สุดท้ายของ function หลักด้วย

• จุดสังเกตที่สำคัญของ Tail call คือ หลังจากที่มีการเรียก subprocedure call ซึ่งเป็น operation สุดท้ายของ function หลักแล้วนั้น จะไม่มีการประมวลผลที่ต้องใช้ข้อมูล stack frame ของ function ตั้งต้นอีกต่อไป
  ดังนั้นแล้ว function หลักนั้นสามารถคืนหน่วยความจำให้กับ process ของโปรแกรมได้ทันที ก่อน ที่จะมีการ สร้าง stack frame ใหม่สำหรับ subprocedure call นี้ ทำให้เราสามารถประหยัด stack memory โดยไม่เกิด stack overflow ได้เพราะไม่เกิดการสะสม memory ของ stack frame หลาย ๆ อันนั่นเอง
• feature ข้างต้นนี้ บ้างก็เรียกว่า Tail call optimization บ้างก็เรียก Tail call elimination ซึ่งเป็น feature ที่พบได้ในบาง language implementation ของภาษาโปรแกรม (Programming Language) บางภาษา เช่น สำหรับใน GNU Compiler Collection จะมี flag ชื่อว่า -foptimize-sibling-calls เพื่อเปิดใช้งาน feature นี้

ดังนั้นแล้วคำกล่าวที่ว่า “(2.) recursive function แย่กว่า loop iteration เพราะอาจเกิด stack overflow ได้” จึงไม่ถูกต้องเสมอไปเช่นกัน

อย่างไรก็ตาม ไม่ใช่ว่าทุก function จะสามารถใช้ Tail call optimization/elimination ได้ นั่นขึ้นอยู่กับโครงสร้างของ function แต่ละอันด้วยว่าจะเขียนในรูปของ Tail call ได้หรือไม่

โดยสรุปแล้ว การเขียนโปรแกรมในรูปแบบของ loop iteration vs. recursive function ไม่มีวิธีไหนที่รับประกันได้ว่าจะใช้งานได้ดีกว่าในทุกกรณี เราในฐานะโปรแกรมเมอร์จึงจำเป็นต้องเข้าใจรายละเอียดเหล่านี้ เพื่อเลือกใช้วิธีที่เหมาะสมที่สุด สำหรับงานแต่ละประเภทต่อไป

โจทย์สำหรับผู้เข้าแข่งขันรอบชิงชนะเลิศของ Code Squad

หัวข้ออื่น ๆ สำหรับผู้เข้าแข่งขันรอบชิงชนะเลิศของ Code Squad จะเขียน blog entry ตาม assignment ที่กำหนด โดยมีหัวข้อให้เลือกดังต่อไปนี้

• แง่มุมอื่นๆ ของ Recursion นอกเหนือจาก recursive function ซึ่งปรากฏอยู่ในภาษาโปรแกรมอื่นๆ หรือเป็นแง่มุมอื่นๆ ของ Recursion ที่มีประโยชน์ต่อการเขียนโปรแกรม
• การเปรียบเทียบ loop iteration vs. recursive function ด้วยมาตรวัดอื่นๆ ซึ่งนอกเหนือจาก code readability และ stack memory management
• บทพิสูจน์ว่าเหตุใด binary_search_recursive จึงทำงานได้อย่างถูกต้อง โดยบทพิสูจน์ดังกล่าวมีความรัดกุมทางคณิตศาสตร์แต่อ่านแล้วเข้าใจง่าย
• การลองเขียน recursive function เพื่อคำนวณอนุกรมเลขคณิต F(n) = 0 + 1 + 2 + 3 + … + n โดยปรับเปลี่ยนให้อยู่ในรูปของ Tail call
• concept ของ Tail call (รวมถึง Tail call optimization/elimination) ที่ปรากฏใน programming language implementation ต่างๆ
• concept ของ stack/heap memory ของ process ของโปรแกรม รวมถึงความสัมพันธ์กับ recursive function
• visualize การทำงานของ Tail call optimization/elimination
• ตัวอย่างของ optimization อื่นๆ ในแง่มุมของ programming language นอกเหนือจาก Tail call optimization/elimination
• ปัญหาอื่นๆ ที่นำ Recursion มาแก้ปัญหา และมีความน่าสนใจมากเป็นพิเศษ
• เนื้อหาอื่นๆ ที่ต่อยอดหรือมีความเกี่ยวข้องกับ blog entry นี้
• หัวข้อที่เป็นเรื่องพื้นฐานสำหรับโปรแกรมเมอร์ แต่นำมาเล่าใหม่ในมุมที่ลึกซึ้งมากขึ้น (เข้ากับธีม Basics Revisited)

แล้วมาพบกันใหม่ในโอกาสถัดไปครับ