9 พฤษภาคม 2560

Published พฤษภาคม 09, 2560 by with 0 comment

Recursive Function กับ Python

รีเคอร์ซีฟฟังก์ชัน (recursive functions) คือ ฟังก์ชันที่เรียกตัวเอง โดยแต่ละครั้งที่ฟังก์ชันถูกเรียก จะเกิดตัวแปรอัตโนมัติชุดใหม่ที่ไม่เกี่ยวข้องกับชุดเดิม จึงเรียกอีกชื่อหนึ่งว่า "ฟังก์ชันแบบเวียนเกิด"
หลักการรีเคอร์ซีฟฟังก์ชัน คือ เขียนโปรแกรมวนซ้ำเพื่อลดปัญหาของโปรแกรมที่ซับซ้อน

ขั้นตอนการเขียนรีเคอร์ซีฟฟังก์ชัน

  • ทำความเข้าใจโจทย์

  • หาจุดวนกลับ โดยจะหาเมื่อการวนกลับยุติลงแล้วส่งค่ากลับไปคืนจุดที่เรียก

  • หาขั้นตอนที่ต้องเรียกซ้ำ

รูปแบบทั่วไปของรีเคอร์ซีฟฟังก์ชันมีรูปแบบดังนี้
def ฟังกชัน(พารามิเตอร์):
  if < เงื่อนไขที่ผลให้ยุติการเรียกซ้ำ (จุดวกกลับ หรือ base case) >:
    ส่งคำตอบคืน
  else:
    แยกปัญหาเป็นประเด็นย่อย ด้วยการเรียกซ้ำ (Recursive)

ข้อควรระวัง : ในการเขียนโปรแกรมด้วยรีเคอร์ซีฟฟังก์ชันต้องรอบคอบ และรีเคอร์ซีฟฟังก์ชันจำเป็นจะต้องมี if statement เพื่อตัดสินใจว่าควรเรียกตัวเองต่อไปหรือไม่

ตัวอย่างเช่น โปรแกรม Python หาแฟกทอเรียลได้
โดยนิยามของแฟกทอเรียฟังก์ชัน คือ
n!  =  n*(n-1)!  if  n < 0

เอานำมาหา 5!
5! = 5*4*3*2*1 = 5*4!
4! =   4*3*2*1 =   4*3!
3! =     3*2*1 =     3*2!
2! =       2*1 =       2*1!
1! =         1 =          1
0! =         1 นี่คือ จุดวกกลับ หรือ base case

สามารถเขียนโปรแกรม Python หาแฟกทอเรียลในรีเคอร์ซีฟฟังก์ชันได้ดังนี้
ผลลัพธ์
6
120

ในทางกลับกัน เราสามารถนำรีเคอร์ซีฟฟังก์ชันมาเขียนเป็นฟังก์ชันลูปได้เช่นกัน

ผลลัพธ์
6
120

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

ข้อควรระวังการใช้งานรีเคอร์ซีฟฟังก์ชัน คือ ปัญหา Stack Overflow และในสถานการณ์ทั่วไป รีเคอร์ซีฟฟังก์ชันทำงานช้ากว่าลูป เพราะต้องเสียเวลาสร้าง Call Stack ในทุกครั้งที่เรียก

เมื่อนำรีเคอร์ซีฟฟังก์ชันไปสร้างเป็นไฟล์ factorial1.py แล้วนำฟังก์ชันลูปไปสร้างเป็นไฟล์ factorial2.py
ทำการทดสอบด้วยโค้ด python -m profile ไฟล์.py
ผลลัพธ์
ไฟล์ factorial1.py

ไฟล์ factorial2.py

จะเห็นได้ว่า ในภาษา Python รีเคอร์ซีฟฟังก์ชันทำงานช้ากว่าฟังก์ชันลูป และมีการเรียกใช้ function calls มากกว่า

ถ้าหากขาดตกบกพร่องเนื้อหาตรงไหน สามารถแจ้งได้ใต้ความคิดเห็นนี้ครับ
ขอบคุณครับ

0 ความคิดเห็น:

แสดงความคิดเห็น

แสดงความคิดเห็นได้ครับ :)