RECURSIVE FUNCTION (การเรียกทำซ้ำ)

 

RECURSION (การเรียกทำซ้ำ)

            ในส่วนของ Recursion หรืออาจจะเรียกได้อีกอย่างนึงว่า Recursive Function หากจะพูดให้เข้าใจง่ายๆ ก็คงอาจจะพูดได้ว่าเป็นฟังก์ชันที่เรียกใช้ตัวเองไปเรื่อยๆ จนกว่าจะถึง Base Case ยกตัวอย่างเช่น

นิยาม ให้ F(n) เป็นฟังก์ชันที่คืนค่า n! กลับมา หากเราลองดูดีๆ เราสามารถที่จะเขียน F(n) ให้อยู่ในรูปของ Recursive Function ได้เป็น F(n) = n x F(n-1) โดยมี F(0) = 1 เป็น Base Case หากเราอยากจะหาว่า F(5) เป็นเท่าไหร่เราก็จะใช้ความสัมพันธ์นี้แก้หาได้

            F(5) = 5 x F(4) = 5 x 4 x F(3) = 5 x 4 x 3 x F(2) = 5 x 4 x 3 x 2 x F(1) = 5 x 4 x 3 x 2 x 1 x F(0) = 5 x 4 x 3 x 2 x 1 x 1 = 120

ประโยชน์ของ Recursion นี้สามารถใช้ในการแก้ปัญหาเกี่ยวกับ Competitve Programming ได้ไม่ว่าจะเป็นการนำมาใช้กับ Dynamic Programming หรือไม่ว่าจะเป็นการแก้ปัญหาที่ต้องแตกกรณีออกเป็นกรณีย่อยๆ ยกตัวอย่างเช่น ปัญหาการแลกเหรียญ (Coin Change) 

Coin Change

            Coin Change เป็นหนึ่งในปัญหาที่ Classic อีกปัญหานึงที่เราสามารถใช้เรื่อง Recursion เข้ามาแก้ได้

โดยปัญหา Coin Change จะเป็นปัญหาเกี่ยวกับการที่เราจะแลกเหรียญเป็นเงินที่เราต้องการโดยใช้เหรียญที่น้อยที่สุดเท่าที่จะทำได้โดยให้เราคิดว่าเรามีเหรียญอย่างไม่จำกัด สามารถแลกเหรียญอะไรก็ได้ที่มีด้วยจำนวนเท่าไหร่ก็ได้

            ในการที่จะทำโจทย์ข้อนี้เราจะต้องคิดก่อนว่าเราจะกำหนด Parameter อะไรให้ฟังก์ชันของเราบ้าง และ Base Case ของฟังก์ชันของเราคืออะไร

            การที่จะแก้ปัญหานี้ขอกำหนดฟังก์ชัน F(n) โดยให้นิยามว่า F(n) จะเป็นฟังก์ชันที่คืนค่าจำนวนเหรียญที่ใช้น้อยที่สุดในการรวมกันเป็นเงิน n บาท

            ต่อมาจะเป็นในส่วนของ Base Case การที่เราจะคิด Base Case ได้ให้เราคิดในกรณีที่พื้นฐานที่สุดที่จะเป็นไปได้ ในที่นี้ก็คือถ้าหากสมมติว่าเราจะสร้างเงิน 0 บาท แสดงว่าเราจะใช้ 0 เหรียญ นั้นก็หมายความว่า Base Case ของเราจะคือ F(0) = 0

            ที่นี้หลังจากที่เราคิดในส่วนของ Base Case เสร็จเราก็จะมาคิดในส่วนของ Recurrence Relation หรือว่าความสัมพันธ์กันระหว่างเหตุการณ์ต่างๆ สมมติว่าให้ coin[i]  เก็บค่าของเหรียญที่ i และ ans แทนคำตอบของแต่ละเหตุการณ์ เพราะฉนั้นเราก็จะเขียน Recurrence Relation ได้ว่า ans = min(ans, F(n-coins[i])+1) ; สำหรับทุก coins[i] 

            นอกจากนี้นั้นยังมีปัญหาอื่นอีกมากมาย อย่างเช่น ปัญหาเกี่ยวกับ Subset หรือว่าจะเป็นปัญหาเกี่ยวกับการแตกกรณีย่อยๆจำนวนมาก