Tail call recursion — More example
TECHJAM 2018 — Code Incubation #1
โดย wizard of skn
หลังจากเราได้ทำความรู้จัก Tail call recursion ใน blog ของ @techjamthailand มาแล้ว วันนี้เรามาลองดูตัวอย่างเพิ่มเติมของการเขียน Tail call recursion กันครับ โดยเราจะเริ่มจากการเขียน recursion แบบปกติก่อน แล้วจึงค่อยแปลงไปเป็นแบบ Tail call ครับ
อนุกรมเลขคณิต
โจทย์
หาผลลัพธ์ของ 1 + 2 + 3 + … + N
Normal recursion
ก่อนอื่นเลย เรามาลองเขียนเวอร์ชั่นปกติกันก่อน เขียนออกมาแล้วก็จะได้หน้าตาประมาณนี้
Tail call recursion
เมื่อลองพิจารณาดูแล้ว จุดที่เป็นปัญหาคือการ + n เข้าไปกับผลลัพธ์ของ seriesSum(n-1) ซึ่งเราต้องทำการกำจัดการ + n นี้ออกไป เพื่อให้ operation สุดท้ายของ function นี้คือการ recursive function call
ปัญหาเกิดจากการที่เราหาเป็นผลรวม ทำให้ต้องรู้ค่าของ seriesSum(n-1) ก่อน ถึงจะหาผลรวมของ seriesSum(n) ได้
ทางแก้ทางหนึ่งคือการใช้ global variable เข้าช่วย ในที่นี้เราก็เก็บ sum ไว้ข้างนอก แล้วใน function ก็ให้ทำการ + n เข้าไปที่ sum ก่อน แล้วค่อยเรียก recursion
แต่ถ้าใช้ global ก็อาจจะดูไม่เป็น recursive มากนัก และจะไม่ถือเป็น function ที่เป็น functional เพราะมี side effect
เมื่อกลับมาพิจารณาดูดี ๆ แล้ว จะพบว่า เราก็สามารถเพิ่ม parameter sum เข้าไปใน function ได้เลย
fibonacci
คราวนี้เรามาลองดูปัญหาอีกข้อนึงที่คล้าย ๆ กันดีกว่า
โจทย์
จงหา fibonacci ลำดับที่ N โดยที่นิยามของ fibonacci(n) คือ
- fibonacci(0) = 0
- fibonacci(1) = 1
- fibonacci(n) = fibonacci(n-2) + fibonacci(n-1)
Normal recursion
ปัญหาอย่างหนึ่งของการทำ fibonacci แบบนี้คือการคำนวณจะใช้เวลาเป็น exponential
การที่ใช้เวลาเป็น exponential เพราะว่า fib(n) นี้จะไปเรียก fib(n-1) และ fib(n-2) ซึ่งจะได้ว่า
T(n) = T(n-1) + T(n-2)
T(1) = T(0) = 1พบว่า time complexity ของ fib(n) จะประมาณได้เป็น fib(n) นั้นเอง ซึ่งจริง ๆ แล้วลำดับ fibonacci ที่ n มีสูตร closed-form อยู่ในรูปของ ยกกำลัง n
Tail call recursion
เราสามารถใช้หลักการคล้ายกับข้อที่แล้วได้ โดยเพิ่ม parameter เข้าไปใน function
เมื่อจะมาทำ Tail call recursion แล้ว ปัญหาอย่างหนึ่งคือ fib(n) นั้นจะทำการแตกออกเป็น 2 function คือ fib(n-1) และ fib(n-2) แล้วค่อยเอามาบวกกัน ซึ่งเราไม่สามารถจะทำให้เป็น Tail call recursion ได้
เมื่อพิจารณา fib(n) แล้ว จะพบว่าการที่เราจะรู้ fib(n) ได้ เราจะต้องรู้ fib(n-1) และ fib(n-2) ก่อน ซึ่งทางแก้ก็คือทำเป็นแบบ bottom-up แทน คือเริ่มคิดจาก fib(2), fib(3) ไปเรื่อย ๆ จนถึง fib(n) เพราะว่าถ้าเราเริ่มจาก fib(2) เราก็สามารถรู้ได้ทันทีจาก fib(1)+fib(0) ซึ่งเป็น base case และพอมาคิด fib(3) เราก็ใช้คำตอบที่เราได้ก่อนหน้ามาหาต่อได้เลย
ดังนั้นเราก็ส่ง fib(n-1) และ fib(n-2) เข้ามาเป็น parameter ของ function เพื่อทำการหา fib(n)
การเขียนแบบนี้นอกจากจะทำ Tail call recursion ได้แล้ว ยังช่วยลด time complexity ลงได้อีกด้วย ซึ่งเป็นผลมาจากการทำแบบ bottom-up เพราะตอนแรกที่ทำแบบ top-down นั้นเกิด overlapping subproblem แต่เราไม่ได้ทำการเก็บคำตอบไว้ ทำให้ต้องคำนวณซ้ำหลายรอบ แต่การทำ bottom-up นั้น เรามีคำตอบของ subproblem ที่เราต้องการเป็น parameter เสมอ (fi_1 และ fi_2)
สรุป
การเขียน Tail call recursion นั้น มีความจำเป็นในภาษาที่เป็น functional ซึ่งนอกจากการใช้ Tail call recursion จะช่วยลด stack memory usage แล้ว ยังสามารถช่วยลด time complexity ในบางกรณีได้อีกด้วย
