/ BasicKnowledge

[365 วันแห่งโปรแกรม #day73] Recursion (อีกครั้ง)

เมื่อตอนที่ 23 ผมเคยพูดเกี่ยวกับ Recursion ไปครั้งนึงแล้ว ซึ่งก็ได้ยกตัวอย่างเกี่ยวกับ Recursive Function เอาไว้ แต่ในครั้งนั้นไม่ได้ลงรายละเอียดอะไรมากเท่าไหร่ วันนี้ผมจะกลับมาเขียนเพิ่มเติมอีกครั้งเพื่อที่เนื้อหาจะได้สมบูรณ์ยิ่งขึ้น


Recursion เหมาะกับอะไรแน่?

ความเดิมตอนที่ 23 ผมบอกว่า Recursion หมายถึง การแก้ปัญหาโดยแบ่งปัญหาออกเป็นส่วนย่อยๆ ที่เหมือนกัน ทีนี้ถ้าถามว่า Recursion เหมาะกับอะไร ก็คงตอบได้แต่ว่าปัญหาที่สามารถแก้ด้วยวิธีการวนซ้ำ แต่ทำด้วย iteration แล้วซับซ้อนเกินไป ไม่ว่าจะเป็น Factorial, Fibonacci, Travelling Salesman, Graph Operate เป็นต้น

คิดแบบ Recursion

หัวใจหลักของ Recusrion มีอยู่ 2 ประการคือ

  1. ส่วนไหนทำซ้ำได้

  2. สิ้นสุดที่ตรงไหน

การที่จะเขียน Recursive Function ขึ้นมาได้ย่อมต้องรู้ว่าเราจะวนทำอะไร แล้วการทำงานจะจบลงได้อย่างไร แค่นี้เลยครับ

Fibonacci

Fibonacci เป็นอีกตัวอย่างหนึ่งที่ใช้ในการเรียนรู้เกี่ยวกับ Recursion ได้เป็นอย่างดี แล้ว Fibonacci คืออะไร? Fibonacci คือตัวเลขที่อยู่ใน integer sequence นี้

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...$

เมื่อพิจารณาแล้วจะพบว่า sequence ดังกล่างเกิดจากการนำตัวเลขก่อนหน้า 2 จำนวนมาบวกกัน ยกเว้น 2 ตัวแรกของ sequence ที่ถูกกำหนดไว้แต่แรก

$F_n = F_{n-1} + F_{n-2}$

$F_0 = 0$

$F_1 = 1$

จะเห็นว่าเลข Fibonacci ที่ตำแหน่ง n ใดๆ เกิดจากผลบวกของ Fibonacci ใน 2 ตัวแหน่งก่อนหน้า ตรงนี้คือส่วนที่เราจะใช้การทำซ้ำเพื่อคำนวณได้ แต่ในตำแหน่งที่ 0 และตำแหน่งที่ 1 แล้ว มีการกำหนดค่าที่ตายตัว ดังนั้น 2 ตำแหน่งนี้จะเป็นตำแหน่งสิ้นสุดของการทำซ้ำนั่นเอง

เดี๋ยวเราเราจะลองหา Fibonacci ที่ตำแหน่ง n ใดๆ ด้วยวิธีการ iterate กันดูครับ

หมายเหตุ ในตัวอย่างนี้เราจะคำนวณเฉพาะตัวเลข Fibonacci เทื่อ n เป็นจำนวนเต็มบวกเท่านั้น

จากโค้ดข้างต้นผมกำหนดให้ a และ b มีค่าเริ่มต้นเป็น 0 และ 1 ซึ่งก็คือค่าของ $F_0$ และ $F_1$ ตามลำดับ แล้วกำหนดให้ result เริ่มต้นเป็น 0 เนื่องจากที่ตำแหน่งแรก $F_0$ มีค่าเท่ากับ 0

ต่อมาผมทำการวนซ้ำ n-1 รอบ (เราเริ่มวนจริงคือตำแหน่งที่ 2 ไปถึง n) ในแต่ละรอบจะนำ a และ b มาบวกกัน แล้วเก็บใส่ตัวแปร result ตรงนี้มาจาก
$F_n = F_{n-1} + F_{n-2}$ เพราะ a และ b เป็นผลลัพธ์ของ 2 ตำแหน่งก่อนหน้า หลังจากนั้นเลื่อน a และ b ให้เก็บค่าของตำแหน่งถัดไปเพื่อใช้ในการวนซ้ำรอบหน้า (ถ้า i ยังอยู่ในเงื่อนไข)

สุดท้ายแล้วเมื่อเสร็จสิ้น foor-loop เราก็จะได้ตัวแปร result ซึ่งเป็นค่าของ Fibonacci ในตำแหน่ง n ที่เรากำหนด

ต่อมาเราจะมาลองทำสิ่งเดิมด้วย Recursive Function กันครับ

จะเห็นว่าคราวนี้โค้ดของเรานั้นสั้นกว่าเดิมมาก เริ่มต้นจากการเช็คก่อนเลยว่า n เป็น 0 หรือ 1 ไหม เพราะ 2 ตำแหน่งนี้มีค่าคงที่คือ 0 และ 1 ตามลำดับ ถ้าไม่ใช้ก็ให้นำค่า Fibonacci ของ n-1 และ n-2 มาบวกกัน ซึ่งตรงนี้แหละครับที่เกิดการเรียกตัวเอง เพราะเรายังไม่รู้ว่า Fibonacci ของ n-1 และ n-2 คืออะไร โปรแกรมมันก็จะไปคำนวนด้วยวิธีเดิมไปเรื่อยๆ จนปลายสุด n จะเป็น 0 หรือ 1 นั้นเอง เขียนแผนภาพได้ประมาณนี้ครับ

Fibonacci at position 5

โปรแกรมของเราจะแบ่งปัญหาออกเป็นส่วนย่อยๆ เช่นเราต้องการหา Fibonacci ในตำแหน่งที่ 5 โปรแกรมก็จะไปหาตำแหน่งที่น้อยกว่านั้นแล้วนำมารวมกันเรื่อยๆ ตามนิยามนั่นเอง อย่างไรก็ตามถ้าเราหา Fibonacci ในตำแหน่งที่ 5 นั้น จะมีการวนเรียกฟังก์ชัน F ถึง 15 ครั้งด้วยกัน ซึ่งสูงกว่าการวนซ้ำวิธีแรกที่เราทำเกือบ 4 เท่า และเมื่อพิจารณาแล้วพบว่าจำนวนการเรียกตัวเองที่ลึกที่สุดคือ 5 ชั้น ซึ่งทำให้เกิด 5 Stack Frame ซ้อนทับกัน

ทุกครั้งที่ฟังก์ชัน F ขึ้นมาทำงานนั้นจะเกิด Stack Frame ใหม่ใน Memory นั่นหมายความว่าถ้า n มีขนาดใหญ่มากก็มีโอกาสที่จำเกิดการ Overflow ขึ้นได้ แต่เหตุการณ์นี้จะไม่เกิดในวิธีแรกเพราะมีการเปิด Stack Frame เพียงครั้งเดียวเท่านั้น

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

*ไม่ดีสำหรับโจทย์ข้อนี้ เพราะการเขียนแบบ Recursion ไม่ควรมี Performance แย่กว่าแบบ Iteration

Tail Recursion & Tail Recursion & Tail Call Optimization

มีเทคนิดหนึ่งที่ทำให้เราสามารถ reuse Stack Frame เดิมในการเรียกฟังก์ชันอื่นได้ เทคนิคนี้เรียกว่า Tail Call Optimization (TCO) แต่การที่จะใช้งาน TCO ได้นั้น ฟังก์ชันที่เราจะเรียกต้องอยู่ที่ส่วน tail ของฟังก์ชันปัจจุบัน (Tail Call)

Tail Call

Tail Call แปลตรงตัวคือการ call ฟังก์ชันที่ tail ของอีกฟังก์ชัน โดยปกติแล้วการเรียกฟังก์ชันจะเป็นการเปิด Stack Frame ใหม่ขึ้นมา แต่หากฟังก์ชันของเรานั้นเป็น Tail Call คือ การทำงานสุดท้ายเป็นการเรียกฟังก์ชันอื่น แล้วจบหรือ return ทันที จะทำให้ Stack Frame ปัจจุบัน ไม่มีความจำเป็นอีกต่อไป (ไม่ต้องรอ result) เทคนิค TCO จะเข้ามาช่วยตรงนี้ โดยการทำให้ฟังก์ชันที่เราเรียกนั้นมาใช้ Stack Frame เดิมที่ไม่ได้ใช้แล้วนั่นเอง

จากตัวอย่าง ทั้ง g() และ f() ใน foo1() และ foo2() เป็น Tail Call เนื่องจากถูกเรียกตรงจุดที่จบการทำงานของฟังก์ชันพอดี และ return ค่ากลับไปทันทีไม่มีการนำค่าที่คำนวณได้มาใช้อีก

Tail Recursion

Tail Recursion ก็มาจากเรื่อง Tail Call คือเราต้องการลดการสร้าง Stack Frame ลง ก็เลยให้ไปเรียกตัวเองที่ tail ของฟังก์ชัน เพื่อที่จะได้ใช้ประโยชน์จาก TCO

นั่นหมายความว่าโค้ดที่แล้วของเราซึ่ง return F(n-1) + F(n-2); ไม่เป็น Tail Recursion เพราะหลังจากจบ F(n-1) และ F(n-2) แล้วมีการนำผลลัพธ์นำมาบวกกัน และไม่ได้ประโยชน์อะไรจาก Tail Call Optimization ด้วย

การแก้โค้ดใหม่คราวนี้เราต้องกำจัดปัญหาของเราที่มีการเรียกตัวเอง 2 ครั้งใน 1 รอบ แล้วยังนำค่าที่ได้มาบวกกันอีก ดังนั้นวิธีที่เป็นไปได้คือการส่งผลลัพธ์หรือ state ปัจจุบันเข้าไปตอนเรียกตัวเอง

หมายเหตุ มีแค่บางภาษาและบางคอมไพเลอร์เท่านั้นที่รองรับการทำ Tail Call Optimization

คราวนี้โค้ดของเราจะคล้ายๆ โค้ดแรกที่ใช้ iteration ครับ ตอนนี้ฟังก์ชัน F จะรับพารามิเตอร์ 3 ตัว คือ n เดิม a และ b คือค่า Fibonacci 2 ตัว ณ นั้นๆ กล่าวคือในรอบแรกนั้น a จะเท่ากับ 0 และ b จะเท่ากับ 1 พอเข้ารอบสอง a จะเลื่อนไปเป็น b เดิม แล้ว b จะนำมาบวกกับ a เพื่อให้เป็น b ใหม่ ดังภาพ

Tail Recursion params

จากภาพจะเห็นได้ว่าในรอบแรก (0) นั้น a = 0 และ b = 1 ดังนั้นเราน่าจะพออนุมานได้ว่า a คือค่าของ Fibonacci ในทำแหน่งที่ 0 พอวนซ้ำรอบที่ 2 (1) ปุ๊บ a (ค่าจาก b เดิม) กลายเป็น 1 และ b เป็น 1 เหมือนเดิม (a + b) ในรอบนี้ a จะเป็นค่าของ Fibonacci ในทำแหน่งที่ 1 นั่นเอง และก็วนซ้ำแบบนี้ไปเรื่อยๆ จนถึงรอบที่ n+1 ก็จะได้คำตอบของเรา

ในโค้ดผมใช้วิธีลดค่า n ลงเรื่อยๆ จนกว่าจะเหลือ 0 แล้วค่อยคืนค่า a แต่ก็ใช้เวลา n+1 รอบเช่นเดียวกัน

สรุปได้ว่าหัวใจหลักของ Tail Recursion จะเป็นการส่งคำตอบจากจุดที่ลึกที่สุดออกมาเรื่อยๆ โดยไม่มีการกระทำอะไรกับคำตอบนั้นอีก ดังนั้นแสดงว่าเราจำเป็นต้องส่ง state หรือ accumulator เข้าไปทุกครั้งเมื่อเรียกตัวเอง

Tail Call Optimization

ตอนนี้โค้ดของเราพร้อมที่จะทำ Tail Call Optimization เพื่อลดการเกิด Stack Frame แล้วครับ ในขั้นตอนนี้เราก็ทำแค่ไปกำหนดตอนคอมไพล์ว่าให้ Optimize ด้วยนะ (เช่น ใส่ flag ต่างๆ O1 O2 อะไรแบบนี้) ผลลัพธ์ของส่วนนี้จะเหมือนกับว่าเราวนทำซ้ำด้วยการใช้ goto เลย แต่เดี๋ยวก่อนไม่ใช่ว่าทุกภาษาหรือทุกคอมไพเลอร์นั้นจะรองรับการทำ Tail Call Optimization นี้

Count each element in array

ผมขอเสนออีกตัวอย่างสำหรับการใช้ Recursion ทำ foldr เพื่อนับความถี่ของ element ใน array ที่ส่งเข้าไป

กำหนดให้โจทย์นี้มี input เป็น array และ output เป็น dictionary<element,count> ดังนั้นจะได้ว่า

  1. วนซ้ำเพื่อเลื่อน cursor ไปยังตำแหน่งถัดไปใน array

  2. สิ้นสุดเมื่อถึง element สุดท้ายของ array

ก็น่าจะเขียนออกมาได้แบบนี้

จากตัวอย่างนี้จะเห็นว่าเราสามารถใช้องค์ประกอบอื่นในการกำหนดจุดสิ้นสุดของ Recursion ได้

Binary tree traversal with recursion

อีกตัวอย่างนึงที่เหมาะกับการใช้ Recursion นั่นก็คือเรื่อง Binary tree traversal เพราะเรื่องนี้นั้นซับซ้อนเกินกว่าที่จะเขียนแบบ Iteration

กำหนดให้ n เป็น node หนึ่งใน Binary tree ให้พิมพ์ค่า a ที่อยู่ใน node ทุก node ที่อยู่ใต้ n (รวมถึง n ด้วย)

Binary tree คือ Tree แต่ละ node จะมี child ไม่เกิน 2 ตัว

สมมติว่ามี Tree เป็นแบบนี้

ดังนั้นทุกครั้งที่เรา visit ที่ node ต่างๆ ของ tree เราจะต้องเช็คว่า มี leaf1 หรือ leaf2 อยู่หรือไม่ ถ้ามีก็ให้เข้าไปข้างด้วย แต่จะพิมพ์ค่า a ก่อนเข้าหรือหลังเข้าก็ได้ (อยู่ที่ว่าต้องการข้อมูลเรียงแบบไหน) แล้วพอลองเขียนโค้ดปุ๊บก็จะได้ประมาณนี้ครับ

จะเห็นว่าเพียงเท่านี้เราก็สามารถเข้าถึงทุก node ของ Tree ได้แล้วครับ

ถ้าไม่ return แล้วจะทำ Tail Recursion ได้ไหม

ตัวอย่างที่ผ่านมานั้นไม่มีการ return ค่า แต่พิมพ์ค่าบางอย่างออกมาบน console อย่างเดียว แล้วจะทำเป็น Tail Recursion ได้ไหมนะ? ต้องบอกว่าได้ครับ ไม่ได้มีข้อกำหนดว่าจะต้อง return แค่เรียกฟังก์ชันที่ tail ก็พอ

สรุปวันนี้

คงต้องจบเพียงเท่านี้ก่อนครับ เดี๋ยวจะยาวเกินไป ในวันนี้เราได้เรียนรู้เรื่องการทำ Recursion การคิดแบบ Recursion และเทคนิคการลดปริมาณ Stack Frame ผมขอย้ำอีกครั้งว่า Recursion นั้นควรใช้ต่อเมื่อการเขียนแบบ Iteration มันยุ่งยากและซับซ้อนเกินไป หรือไม่สื่อ เพราะการทำ Recursion นั้นอาจจะทำให้ Performance ดรอปลงมากหากไม่ Optimize Algorithm ให้ดี

References

Fibonacci Number - Wikipedia

Recursion - Wikipedia

Tail Call - Wikipedia

#‎day73 #365วันแห่งโปรแกรม ‪#‎โครงการ365วันแห่ง‬...