RECURSIVE FUNCTION ติดจรวด

ภาพประกอบมีไว้เพื่อโฆษณาชวนเชื่อเท่านั้น ไม่ได้เข้าใจเร็วเท่าหมาวิ่งหรอก

บทความนี้จะเป็นบทความพิเศษ จะรวดเร็วอย่างที่ไม่เคยมีมาก่อน กระพริบตาครั้งเดียวก็จบแล้ว ถ่างตาอ่านให้ดี ๆ เพราะเราไม่มีเวลาอธิบายแล้ว!

ให้เจอหน้าก็พอรู้จัก

Recursive function (ฟังก์ชันเรียกตัวเอง ) หน้าตาเป็นยังไง? อยากให้เรานึกภาพตุ๊กตาอีสาว (Matryoshka) ดู

ขอขอบคุณภาพจาก https://giphy.com/gifs/dots-two-dots-nesting-dolls-matryoshka-doll-X8HbeXDF7nzaM

Recursive Function มีหน้าตาจำได้ง่าย ๆ แค่เห็นก็รู้ว่าใช่ คือ ในตัวฟังก์ชันจะมีชื่อฟังก์ชันของตัวเองทำงานอยู่

หน้าตาประมาณนี้

แล้วมีเจ้าตัวแบบนี้ทำไม?

Recursive function เป็นเจ้าตัวที่จิ๋วแต่แจ๋วมาก ๆ สามารถแก้ปัญหาบางปัญหาได้อย่างมีประสิทธิภาพทีเดียว แต่ยังไงไปดู เราไม่มีเวลาอธิบายแล้ว!

เหตุการณ์สมมติ

สมมติว่าเราต้องการจะทำฟังก์ชันการคำนวณค่า Factorial เราก็จะเขียนออกมาประมาณนี้

EZEZ

factorial of 5 is 120

จาก code ด้านบนจะเห็นว่าฟังก์ชัน factorial จะรับค่า n มาแล้ววนลูปและคูณไปเรื่อยจาก n จนถึง 1 ไปเรื่อย ๆ อธิบายเป็นภาพง่ายๆจากด้านล่าง

ผ่าม!!

แต่ฟังก์ชัน factorial นี้ยังไม่ใช่ Recursive function เลย แน่ล่ะ ยังไม่มีชื่อซ้ำเหมือนนายอ๊อดซะด้วยซ้ำ ดังนั้นเราจะทำให้ฟังก์ชันคำนวณ factorial ออกมาเป็น Recursive function ซะ ไปต่อกันเราต้องไวกว่านี้!

Recursive function Starter kit

การจะเขียน Recursive function ไม่ใช่ว่าเขียนแค่ชื่อซ้ำลงไปแล้วจะสามารถทำงานได้เลย เราจำเป็นต้องเข้าใจหลักการเพื่อสามารถเขียนให้ทำงานได้ตามที่ต้องการ และเพื่อให้เราเข้าใจเร็วกว่าหมา(วิ่ง) ผมจึงเตรียม Starter kit ไว้ให้ครับ

แปะๆ

อย่าพึ่งทำหน้าเหมือนเป็นนิ่วในไตเหมือนข้างบนนะครับ เดี๋ยวเราจะมาวางโครงสร้างไปด้วยกัน

ต่อจิ๊กซอว์ความคิดลงในกล่อง

อย่างแรกที่เราต้องทำก็คือการทำเงื่อนไขของ Starter kit ของเราให้สมบูรณ์เสียก่อน ซึ่งเรามีเงื่อนไขของเรา 3 อย่าง

1. Name(ชื่อ) : เราต้องเข้าใจว่าเราต้องการทำฟังก์ชันไปเพื่ออะไร
2. Ending(จุดจบ) : เราต้องกำหนดจุดจบของมันว่ามันจะไปจบที่ไหน
3. Next(จุดต่อไป) : ซึ่งต่อจากข้อ 2 เราต้องทำยังไงให้มันจบให้ได้

จากฟังก์ชันคำนวณ factorial จะสามารถใส่เงื่อนไขได้ดังนี้

เริ่มละ ๆ

เริ่มจากชื่อ เราก็ตั้งชื่อมันซะว่า factorial

จาก จุดจบ เราจะเห็นว่า factorial ไม่ว่าจะเป็นค่าจำนวนเต็มบวกใดๆก็จะคูณไปจนถึง 1เสมอ ดังนั้นจุดจบที่เหมาะสมกับฟังก์ชันนี้คือ 1

จุดต่อไป เราจะให้มันจบที่ 1 ดังนั้นเราจึงต้องให้มันทำฟังก์ชันนี้ตั้งแต่ n ถึง 1

นำ Starter kit ไปแปลงเป็น code

เมื่อได้เงื่อนไขครบทั้ง 3 แล้วก็นำเงื่อนไขที่ได้ไปต่อเป็น code ได้ดังข้างล่าง

ใกล้แล้ว ๆ

การกำหนดจุดจบจะขึ้นอยู่กับ ฟังก์ชันที่เราต้องการจะทำ อาจเป็นค่าคงที่อะไรก็ได้ ซึ่งฟังก์ชัน factorial ของเราจะมีจุดจบที่ 1 เราจึงให้มัน return 1

แต๊น

เมื่อเรามาดูจุดที่ฟังก์ชันต้องทำต่อไป จะเห็นว่า เราสามารถทำรูปแบบการทำงานมันให้เป็น n จนถึง 1 ได้แล้ว เหลือเพียงการทำให้มันสามารถคำนวณตามจำนวนรอบที่มีซึ่งการคำนวณในแต่ละรอบก็จะแบ่งย่อย เป็นรอบละ n คูณกับรอบต่อไปเรื่อยๆ นั่นคือ n * factorial(n-1) นั่นเอง

เอ็นอะไรก็ไม่อร่อยเท่าเอ็นไก่

ดังนั้นจุดสุดท้ายก็ใส่ return n * factorial(n-1) ก็เป็นอันสมบูรณ์

ตราเด็กสมบูรณ์

ผลที่ได้ก็จะเป็นเหมือนโค้ดด้านล่าง

factorial of 5 is 120

เหมือนเด๊ะ!!!

ร่ายมาทั้งหมด มันมีไว้ทำไม?

ตั้งแต่ที่เราผ่านมาด้วยกันทั้งหมด ก็คงจะเกิดคำถามว่าลูปก็มีทำไมต้องเรียนด้วย?

ถ้าเราลองเทียบโค้ดทั้ง2แบบดู จะเห็นได้ชัดเลยว่า Recursive function จะเขียนน้อยกว่าซึ่งสามารถประหยัดเวลาได้เยอะทีเดียว หากเราเข้าใจโครงสร้างเราอย่างดี

และนอกจากนี้ ยังสามารถใช้แก้ปัญหาเฉพาะบางประเภทที่มีประสิทธิภาพอีกด้วย เช่นการหาข้อมูลจากโครงสร้างต้นไม้ (Tree) ดังภาพด้านล่าง

มึนเลยทีเดียว

สำหรับวันนี้ก็ขอจบเพียงแค่นี้หวังว่าหลาย ๆ คนจะเข้าใจได้เร็วกว่าหมาวิ่ง หากชอบใจก็สามารถติดตามหัวข้อต่างๆได้ที่ blog นี้ครับ

ฟิ้ว