RECURSIVE FUNCTION ติดจรวด

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

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


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

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

ขอบคุณภาพจาก https://giphy.com/gifs/loop-dolls-matryoshka-v3HJ7AfxfZ1hS

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 นี้ครับ

ฟิ้ว

Ming Ruengjaruwatana

Written by

Computer Engineering Student at PSU

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade