Recursion ของดี แต่ทำไมไม่ควรใช้

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

Recursion คืออะไร ?

สั้น ๆ ง่าย ๆ Recursion คือ การที่เราเรียก Function ตัวเอง เพื่อที่จะแก้ปัญหา

# Factorial using Recursion
def factorial (n:int) :
    if n == 1 :
      return 1
    else :
      return n * factorial(n-1)

ตัวอย่าง Classic ที่สุด น่าจะเป็นการหา Factorial ซึ่งการหามันง่ายมาก ๆ คือ เราแค่เอา จำนวนคูณกันลงไปเรื่อย ๆ เช่น 4! จะเกิดจากการเอา 4 x 3 x 2 x 1 ทำให้ผลลัพธ์เป็น 24 หรือจริง ๆ มันก็คือ Factorial ตัวก่อนหน้า คูณกับตัวมันเอง แต่จริง ๆ เราสามารถคิดอีกแบบได้เหมือนกันคือ จริง ๆ มันก็คือ ตัวเอง คูณ กับ Factorial ของตัวก่อนหน้า เช่น 4! มันก็คือ 4 x 3! นั่นเอง ให้เราคิดภาพง่าย ๆ ว่ามันคือตุ๊กตาแม่ลูกดกที่มันมีตัวใหญ่ แล้วค่อย ๆ ซอยลงไปเป็นตัวเล็กลงไปเรื่อย ๆ นั่นเอง

ขั้นตอนของมันง่ายมากคือ เราเปิดหยิบตุ๊กตาตัวบนสุดขึ้นมา และถ้าเรามีตัวที่เล็กกว่านั้น เราก็เปิดไล่ลงไปเรื่อย ๆ เราเรียกขั้นตอนตรงนี้ว่า Recursive Step จนสุดท้าย เราเปิดจนไม่สามารถเปิดได้แล้ว เราก็จะหยุดเปิด เราเรียกว่า Base Case

นั่นแปลว่า ในทุก ๆ Recursive Function จะต้องมี 2 ส่วนด้วยกันคือ Base Case เป็นเงื่อนไขง่าย ๆ ที่จะหยุด หรือก็คือ การบอกว่า ตุ๊กตาตัวไหนที่จะไม่มีตัวที่เปิดต่อได้แล้ว หากเราไม่กำหนด หรือกำหนดไม่ถูกต้อง Function มันก็จะรันไปเรื่อย ๆ ไม่มีที่สิ้นสุดไปสักที และสุดท้ายคือ Recursive Step คือส่วนที่มันจะเรียกตัวเองลงไป โดยเราจะเรียกให้มันใกล้กับ Base Case มากขึ้นเรื่อย

จากตัวอย่างการหา Factorial ส่วนของ Recursion มันคือตรงที่เราเรียก Function Factorial ไล่ลงไป และส่วนที่เป็น Base Case เรารู้ว่า Factorial ของ 1 คือ 1 แน่ ๆ แล้ว ดังนั้นเราใช้เงื่อนไขอันนี้แหละเป็น Base Case ได้เลย

# Factorial using Loop
def factorial (n:int) :
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

ซึ่งโปรแกรมส่วนใหญ่บนโลก เราสามารถแก้ไขจาก Version ที่เป็น Recursion ให้กลายเป็น Loop หรือกลับไปกลับมาได้หมด ตัวอย่างด้านบน คือ Factorial ที่เราเขียนในตอนแรก แค่เปลี่ยนมาใช้ Loop ไล่คูณไปเรื่อย ๆ

ทำไมนักพัฒนา ถึงพยายามเลี่ยงการใช้ Recursion

หากเราไปคุยกับนักพัฒนาหลาย ๆ คนจะบอกว่า เขาพยายามที่จะไม่ใช้ Recursion ในโปรแกรมที่ใช้ทำงานจริง ๆ แต่จากประสบการณ์ของเรา เรารู้สึกว่า มันไม่ได้แย่ขนาดนั้น แต่เราจะต้องเข้าใจข้อดีข้อเสียของมัน

อย่างแรกคือ มันเสี่ยงต่อการเกิด Stack Overflow เพราะเวลาเราเรียก Recursion Function ลงไปครั้งนึง มันจะ Push การเรียกนั้นเข้าไปใน Call Stack เพิ่มขึ้นเรื่อย ๆ มันอาจจะถึงจุดนึงที่ Call Stack นั้นยาวเกินจนมันเต็ม เราก็เรียกอาการนี้ว่า Stack Overflow นั้นเอง ซึ่งเหตุการณ์ลักษณะนี้ ไม่ได้เกิดจากการเขียนโปรแกรมผิดพลาดเท่านั้น แต่อาจจะเกิดจากการเรียก Recursion ที่ยาวมาก ๆ เช่น factorial(1000000000) เป็นต้น ทำให้ หากรู้ว่า เราอาจจะมีเหตุการณ์ลักษณะนี้เกิดขึ้น เราควรจะไปเขียนเป็น Loop น่าจะปลอดภัยมากกว่ากันเยอะมาก

อย่างที่ 2 คือ Overhead ในการทำงานที่สูง เพราะต้องบอกว่า การทำ Function Call แต่ละครั้งมันมีราคาของมัน เช่นจากเมื่อกี้คือ เราจะต้อง Push ข้อมูลลงไปใน Call Stack ยังไม่นับว่า ขาขึ้น เราจะต้องไล่ Pop Stack นั้นออกมาอีก ทำให้หลาย ๆ ครั้ง หาก Code ชุดไหนเขียนโดยใช้ Recursive มักจะช้ากว่าการเขียนแบบ Loop อยู่พอสมควรเลย

และสุดท้าย เป็นเรื่องของมนุษย์ละ คือ Readability และ Debugging ลองเลื่อนกลับไปอ่าน Factorial Function ด้านบน ที่เขียนด้วย Recursive เทียบกับอันที่เขียนด้วย Loop ดูได้ เราว่า อันที่เขียนด้วย Loop น่าจะอ่านเข้าใจได้ง่ายกว่ากันเยอะมาก และ เวลามันเกิดปัญหาขึ้น เราจะมา Debugging ยังไงการ Debug Loop Function มันทำงานได้ง่ายกว่าเยอะเลยละ อย่างน้อยสุด ๆ Call Stack เราไม่ยาวเป็นหางว่าวเลยละ

เมื่อไหร่ที่เราจะใช้ Recursion

ถึงเราจะบอกข้อเสียของมันมาเยอะขนาดนี้ เราจะเรียนไปทำไมกันนะ แต่เอาเข้าจริง ๆ แล้วเราว่า มันมีหลายปัญหามาก ๆ ที่ถ้าเราเขียนด้วย Recursive ออกมาแล้วมันจะอ่านเข้าใจง่ายกว่ามาก ๆ

ตัวอย่างปัญหาอย่างการทำ Traversal สมมุติว่า เราจะทำ Graph Traversal เพื่อ Search ข้อมูลสักอย่าง ถ้าเราใช้ Loop มันก็จะดูเขียนยากกว่ากันมาก ๆ แต่ถ้าเราใช้ Recursive ในส่วนของ Recursive Step เราก็แค่ไล่ลงไปตามวิธีการ เช่น DFS หรือ BFS เป็นต้น และ Base Case คือ เราเช็คว่า มันมีลูกของมันอีกมั้ย หรือเราเจอข้อมูลที่เราต้องการ

หรืออีกปัญหานึงคือ Divide and Conquer เราว่าการเขียนเป็น Recursive น่าจะเขียนได้ง่ายกว่า เช่น การทำ Merge Sort ที่เราจะซอยมันออกทีละครึ่ง แล้วค่อย ๆ Recursive เพื่อ Sort อีกครึ่งนั้นไปเรื่อย ๆ แล้วซอยลงไปเรื่อย ๆ อีกจนกว่าเราจะเหลือแค่ 2 ตัวเพื่อให้เราสลับเองได้

สรุป

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