การเรียกซ้ำในโครงสร้างข้อมูล: มันทำงานอย่างไร ประเภท & เมื่อใช้

เผยแพร่แล้ว: 2020-05-22

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

สารบัญ

การเรียกซ้ำคืออะไร?

พูดง่ายๆ คือ การเรียกซ้ำคือการแก้ปัญหา และในบางกรณี เทคนิคการเขียนโปรแกรมที่มีคุณสมบัติพิเศษและพิเศษเฉพาะตัว ในการเรียกซ้ำ ฟังก์ชันหรือเมธอดมีความสามารถในการเรียกตัวเองเพื่อแก้ปัญหา กระบวนการเรียกซ้ำเกี่ยวข้องกับการแก้ปัญหาโดยเปลี่ยนให้เป็นปัญหาที่มีขนาดเล็กลง

กระบวนการที่ฟังก์ชันเรียกตัวเองอาจเกิดขึ้นโดยตรงและโดยอ้อม ความแตกต่างในการโทรนี้ทำให้เกิดการเรียกซ้ำประเภทต่างๆ ซึ่งเราจะพูดถึงในภายหลัง ปัญหาบางอย่างที่สามารถแก้ไขได้โดยใช้การเรียกซ้ำ ได้แก่ DFS ของกราฟ หอคอยแห่งฮานอย การข้ามต้นไม้ประเภทต่างๆ และอื่นๆ หากต้องการเรียนรู้เกี่ยวกับการเรียกซ้ำและแนวคิดด้านวิทยาศาสตร์ข้อมูลอื่นๆ โปรดดูหลักสูตรออนไลน์ด้านวิทยาศาสตร์ข้อมูลของ IIIT-B

อ่าน: 13 แนวคิดโครงการโครงสร้างข้อมูลที่น่าสนใจ

การเรียกซ้ำทำงานอย่างไร

แนวความคิดของการเรียกซ้ำเกิดขึ้นจากแนวคิดที่ว่าปัญหาสามารถแก้ไขได้ง่ายมากและใช้เวลาน้อยลงหากแสดงเป็นเวอร์ชันเดียวหรือเล็กกว่า การเพิ่มเงื่อนไขพื้นฐานเพื่อหยุดการเรียกซ้ำเป็นอีกหนึ่งส่วนสำคัญของการใช้อัลกอริทึมนี้ในการแก้ปัญหา

ไม่จำเป็นต้องมีประสบการณ์การเข้ารหัส การสนับสนุนด้านอาชีพ 360° PG Diploma in Machine Learning & AI จาก IIIT-B และ upGrad

ผู้คนมักเชื่อว่าเป็นไปไม่ได้ที่จะกำหนดเอนทิตีในแง่ของตัวมันเอง การเรียกซ้ำพิสูจน์ว่าทฤษฎีนั้นผิด และหากใช้เทคนิคนี้อย่างถูกวิธี ก็อาจให้ผลลัพธ์ที่ทรงพลังมาก ให้เราดูว่าการเรียกซ้ำทำงานอย่างไรด้วยตัวอย่างบางส่วน ประโยคคืออะไร? สามารถกำหนดเป็นประโยคตั้งแต่สองประโยคขึ้นไปรวมกันโดยใช้คำสันธาน ในทำนองเดียวกัน โฟลเดอร์อาจเป็นอุปกรณ์เก็บข้อมูลที่ใช้เก็บไฟล์และโฟลเดอร์ บรรพบุรุษอาจเป็นพ่อแม่ของคนหนึ่งและบรรพบุรุษของสมาชิกครอบครัวอีกคนในแผนภูมิลำดับวงศ์ตระกูล

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

การเรียกซ้ำยังเป็นเทคนิคการเขียนโปรแกรมที่ดีพอ รูทีนย่อยแบบเรียกซ้ำถูกกำหนดเป็นรูทีนที่เรียกตัวเองโดยตรงหรือโดยอ้อม การเรียกรูทีนย่อยมีความหมายโดยตรงว่านิยามของรูทีนย่อยมีคำสั่งเรียกของการเรียกรูทีนย่อยที่กำหนดไว้แล้ว

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

อ่านเพิ่มเติม: ภาษาการเขียนโปรแกรม 6 อันดับแรกที่ควรเรียนรู้

ประเภทของการเรียกซ้ำ

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

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

การเรียกซ้ำโดยตรงสามารถใช้เพื่อเรียกใช้ฟังก์ชันเดียวได้ด้วยตัวเอง ในทางกลับกัน การเรียกซ้ำทางอ้อมสามารถใช้เพื่อเรียกเมธอดหรือฟังก์ชันได้มากกว่าหนึ่งวิธีด้วยความช่วยเหลือของฟังก์ชันอื่น และหลายครั้งเช่นกัน การเรียกซ้ำทางอ้อมไม่ได้ทำให้เกิดโอเวอร์เฮดในขณะที่การเรียกซ้ำทางอ้อมเกิดขึ้น

การเรียกซ้ำใช้เมื่อใด

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

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

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

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

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

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

ตรวจสอบด้วย: 23 หลักสูตรการเขียนโปรแกรมคอมพิวเตอร์ที่ดีที่สุดในการรับงาน

บทสรุป

อย่างไรก็ตาม อาจมีสถานการณ์ที่การตัดสินใจอาจไม่ใช่เรื่องง่าย คุณต้องเลือกระหว่างประสิทธิภาพและความเรียบง่าย หากคุณเป็นนักออกแบบที่มีประสบการณ์ คุณจะรู้แน่ชัดว่าเมื่อใดควรให้ความสำคัญกับประสิทธิภาพมากกว่า และเมื่อเลือกความเรียบง่ายหรือความรัดกุมมากกว่านั้นคือหนทางที่จะไป

หากคุณอยากเรียนรู้เกี่ยวกับโครงสร้างข้อมูล วิทยาศาสตร์ข้อมูล ลองดูโปรแกรม Executive PG ของ IIIT-B และ upGrad ใน Data Science ซึ่งสร้างขึ้นสำหรับมืออาชีพที่ทำงานและมีกรณีศึกษาและโครงการมากกว่า 10 รายการ เวิร์กช็อปภาคปฏิบัติจริง การให้คำปรึกษากับภาคอุตสาหกรรม ผู้เชี่ยวชาญ ตัวต่อตัวกับที่ปรึกษาในอุตสาหกรรม การเรียนรู้มากกว่า 400 ชั่วโมงและความช่วยเหลือด้านงานกับบริษัทชั้นนำ

แอปพลิเคชั่น recursion ในชีวิตจริงที่พบบ่อยที่สุดคืออะไร?

การเรียกซ้ำเป็นกระบวนการที่ฟังก์ชันเรียกตัวเองโดยทางอ้อมหรือโดยตรงเพื่อแก้ปัญหา ฟังก์ชันที่ทำกระบวนการเรียกซ้ำเรียกว่าฟังก์ชันแบบเรียกซ้ำ มีปัญหาบางอย่างที่สามารถแก้ไขได้ค่อนข้างง่ายด้วยความช่วยเหลือของอัลกอริธึมแบบเรียกซ้ำ

การเรียกซ้ำในชีวิตจริงที่พบบ่อยที่สุดคือเมื่อคุณกำลังคำนวณจำนวนเงินที่คุณมีในกล่องที่เต็มไปด้วย Rs. 100 บันทึก หากมีโน้ตมากเกินไป คุณอาจขอให้เพื่อนของคุณทำสิ่งเดียวกันโดยแบ่งทั้งกองออกเป็นสองส่วน เมื่อคุณทั้งคู่เสร็จสิ้นการนับ คุณจะบวกผลลัพธ์ทั้งสองเพื่อให้ได้จำนวนเงินทั้งหมด

ฟังก์ชันแบบเรียกซ้ำต้องมีคุณสมบัติอะไรบ้าง?

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

1. เกณฑ์พื้นฐาน – ต้องมีเงื่อนไขพื้นฐานที่กำหนดไว้ล่วงหน้าหนึ่งเงื่อนไข เมื่อใดก็ตามที่เป็นไปตามเกณฑ์พื้นฐานนี้ ฟังก์ชันจะหยุดเรียกตัวเอง
2. วิธีการแบบโปรเกรสซีฟ – การเรียกซ้ำควรประกอบด้วยวิธีการแบบโปรเกรสซีฟ เมื่อใดก็ตามที่มีการเรียกซ้ำกับฟังก์ชัน ควรเข้าใกล้เงื่อนไขพื้นฐาน

ข้อดีและข้อเสียของการเรียกซ้ำคืออะไร?

ข้อดีบางประการของการเรียกซ้ำคือคุณเพียงแค่กำหนดเงื่อนไขพื้นฐานและกรณีแบบเรียกซ้ำในฟังก์ชันแบบเรียกซ้ำ ซึ่งทำให้โค้ดดูเรียบง่ายและสั้นเมื่อเทียบกับโค้ดแบบวนซ้ำ และปัญหาบางอย่าง เช่น Tree Traversal และ Graph มักเป็นแบบเรียกซ้ำ

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