ความเข้าใจสมัยใหม่ของการเรียกซ้ำ: คำจำกัดความของฟังก์ชันและการเข้าถึงจากภายนอกและจากฟังก์ชันนี้ เป็นที่เชื่อกันว่าการเรียกซ้ำเกิดขึ้นโดยนักคณิตศาสตร์: การคำนวณแบบแฟกทอเรียล, อนุกรมอนันต์, เศษส่วน, เศษส่วนต่อเนื่อง … อย่างไรก็ตาม การเรียกซ้ำสามารถพบได้ทุกที่ กฎธรรมชาติเชิงวัตถุ “พิจารณา” การเรียกซ้ำเป็นอัลกอริธึมหลักและรูปแบบการแสดงออก (มีอยู่) ไม่ใช่วัตถุของโลกวัตถุมากนัก แต่โดยทั่วไปแล้ว อัลกอริธึมหลักของการเคลื่อนไหว
ผู้คนที่เชี่ยวชาญด้านต่างๆ ในสาขาวิทยาศาสตร์และเทคโนโลยีต่างๆ ใช้อัลกอริธึมแบบเรียกซ้ำ f (x) โดยที่ "x ~/=f (x)" ฟังก์ชันที่เรียกตัวเองว่าเป็นโซลูชันที่แข็งแกร่ง แต่การสร้างและทำความเข้าใจโซลูชันนี้เป็นงานที่ยากมากโดยส่วนใหญ่แล้ว
ในสมัยโบราณมีการใช้การเรียกซ้ำเพื่อเพิ่มพื้นที่พระราชวัง คุณสามารถสร้างเอฟเฟกต์เชิงพื้นที่สามมิติที่น่าทึ่งผ่านระบบกระจกที่หันเข้าหากัน แต่มันง่ายที่จะเข้าใจได้อย่างไรปรับกระจกเหล่านี้? ยิ่งยากที่จะระบุได้ว่าจุดใดในอวกาศสะท้อนผ่านกระจกหลายบาน
การเรียกซ้ำ อัลกอริธึมแบบเรียกซ้ำ: ความหมายและไวยากรณ์
ปัญหาซึ่งกำหนดขึ้นโดยการทำซ้ำลำดับของการดำเนินการสามารถแก้ไขได้แบบเรียกซ้ำ อัลกอริธึมอย่างง่าย (คำนวณสมการกำลังสอง สคริปต์เพื่อเติมข้อมูลในหน้าเว็บ อ่านไฟล์ ส่งข้อความ…) ไม่ต้องการการเรียกซ้ำ
ความแตกต่างหลักของอัลกอริทึมที่อนุญาตให้ใช้วิธีแก้ปัญหาแบบเรียกซ้ำ:
- มีอัลกอริธึมที่ต้องดำเนินการหลายครั้ง
- อัลกอริทึมต้องการข้อมูลที่เปลี่ยนแปลงทุกครั้ง
- อัลกอริทึมไม่จำเป็นต้องเปลี่ยนทุกครั้ง
- มีเงื่อนไขสุดท้าย: อัลกอริทึมเป็นแบบเรียกซ้ำ - ไม่สิ้นสุด
โดยทั่วไป ไม่อาจโต้แย้งได้ว่าการดำเนินการครั้งเดียวเป็นเงื่อนไขที่จำเป็นสำหรับการไม่มีเหตุผลในการเรียกซ้ำ คุณไม่สามารถกำหนดให้มีเงื่อนไขบังคับสุดท้ายได้: การเรียกซ้ำที่ไม่สิ้นสุดมีขอบเขตของตัวเอง
อัลกอริธึมเป็นแบบเรียกซ้ำ: เมื่อดำเนินการตามลำดับซ้ำๆ กับข้อมูลที่เปลี่ยนแปลงในแต่ละครั้งและให้ผลลัพธ์ใหม่ทุกครั้ง
สูตรวนซ้ำ
ความเข้าใจทางคณิตศาสตร์ของการเรียกซ้ำและแอนะล็อกในการเขียนโปรแกรมต่างกัน คณิตศาสตร์ แม้ว่าจะมีสัญญาณของการเขียนโปรแกรม แต่การเขียนโปรแกรมเป็นคณิตศาสตร์ของลำดับที่สูงกว่ามาก
อัลกอริธึมที่เขียนอย่างดีเปรียบเสมือนกระจกสะท้อนสติปัญญาของผู้แต่ง ทั่วไปสูตรการเรียกซ้ำในการเขียนโปรแกรมคือ "f(x)" โดยที่ "x ~/=f(x)" มีการตีความอย่างน้อยสองครั้ง ที่นี่ "~" คือความเหมือนหรือไม่มีผลลัพธ์ และ "=" คือการมีอยู่ของผลลัพธ์ของฟังก์ชัน
ตัวเลือกแรก: ไดนามิกของข้อมูล
- ฟังก์ชั่น "f(x)" มีอัลกอริธึมแบบเรียกซ้ำและไม่เปลี่ยนรูป
- "x" และผลลัพธ์ "f(x)" มีค่าใหม่ทุกครั้ง ผลลัพธ์ "f(x)" คือพารามิเตอร์ "x" ใหม่ของฟังก์ชันนี้
ตัวเลือกที่สอง: ไดนามิกโค้ด
- function "f(x)" มีอัลกอริธึมหลายอย่างที่ปรับแต่ง (วิเคราะห์) ข้อมูล;
- การวิเคราะห์ข้อมูล - ส่วนหนึ่งของโค้ดและการใช้งานอัลกอริธึมแบบเรียกซ้ำซึ่งดำเนินการตามที่ต้องการ - ส่วนที่สองของโค้ด
- ผลลัพธ์ของฟังก์ชัน "f(x)" ไม่ใช่
ไม่เห็นผลปกติ การเขียนโปรแกรมไม่ใช่คณิตศาสตร์ ผลลัพธ์ไม่จำเป็นต้องแสดงอย่างชัดเจนในที่นี้ ฟังก์ชันแบบเรียกซ้ำสามารถแยกวิเคราะห์ไซต์และเติมฐานข้อมูล หรือสร้างอินสแตนซ์ของวัตถุตามอินพุตที่เข้ามา
ข้อมูลและการเรียกซ้ำ
การเขียนโปรแกรมอัลกอริธึมแบบเรียกซ้ำไม่ได้เกี่ยวกับการคำนวณแฟกทอเรียล ซึ่งฟังก์ชันจะได้รับทุกครั้งที่มีค่าที่กำหนดซึ่งมากกว่าหนึ่งหรือน้อยกว่า - ตัวเลือกการใช้งานขึ้นอยู่กับความชอบของนักพัฒนา
แฟคทอเรียล "8!" ไม่สำคัญ,อัลกอริธึมที่ปฏิบัติตามสูตรนี้อย่างเคร่งครัด
การประมวลผลข้อมูลคือ "คณิตศาสตร์" ของลำดับที่ต่างไปจากเดิมอย่างสิ้นเชิง ฟังก์ชันแบบเรียกซ้ำและอัลกอริธึมทำงานบนตัวอักษร คำ วลี ประโยค และย่อหน้า แต่ละระดับถัดไปใช้ระดับก่อนหน้า
สตรีมข้อมูลที่ป้อนเข้าจะได้รับการวิเคราะห์ตามเงื่อนไขที่หลากหลาย แต่โดยทั่วไปแล้วกระบวนการวิเคราะห์จะเป็นแบบเรียกซ้ำ มันไม่สมเหตุสมผลเลยที่จะเขียนอัลกอริธึมเฉพาะสำหรับตัวแปรของสตรีมอินพุตทั้งหมด ควรมีฟังก์ชันเดียว ในที่นี้ อัลกอริธึมแบบเรียกซ้ำเป็นตัวอย่างของวิธีสร้างกระแสข้อมูลขาออกที่เพียงพอกับอินพุต นี่ไม่ใช่ผลลัพธ์ของอัลกอริทึมแบบเรียกซ้ำ แต่เป็นโซลูชันที่ต้องการและจำเป็น
นามธรรม เรียกซ้ำและ OOP
การเขียนโปรแกรมเชิงวัตถุ (OOP) และการเรียกซ้ำเป็นเอนทิตีที่แตกต่างกันโดยพื้นฐาน แต่จะเสริมซึ่งกันและกันได้อย่างสมบูรณ์แบบ สิ่งที่เป็นนามธรรมไม่ได้เกี่ยวข้องกับการเรียกซ้ำ แต่ผ่านเลนส์ของ OOP มันสร้างความเป็นไปได้ในการใช้การเรียกซ้ำตามบริบท
เช่น กำลังแยกวิเคราะห์ข้อมูลและเน้นตัวอักษร คำ วลี ประโยค และย่อหน้าแยกกัน เห็นได้ชัดว่าผู้พัฒนาจะจัดเตรียมสำหรับการสร้างอินสแตนซ์ของวัตถุทั้งห้าประเภทนี้และเสนอวิธีแก้ปัญหาของอัลกอริธึมแบบเรียกซ้ำในแต่ละระดับ
ในขณะเดียวกันหากในระดับตัวอักษร “ไม่มีประโยชน์ในการมองหาความหมาย” ความหมายก็จะปรากฏที่ระดับคำ คุณสามารถแบ่งคำเป็นกริยา คำนาม กริยาวิเศษณ์ คำบุพบท… คุณสามารถไปต่อและกำหนดกรณีได้
ที่ระดับวลี ความหมายเสริมด้วยเครื่องหมายวรรคตอนและตรรกะการผสมคำ ที่ระดับของประโยค จะพบระดับของความหมายที่สมบูรณ์ยิ่งขึ้น และย่อหน้าถือเป็นความคิดที่สมบูรณ์
การพัฒนาเชิงวัตถุกำหนดมรดกของคุณสมบัติและวิธีการล่วงหน้า และเสนอให้เริ่มลำดับชั้นของวัตถุด้วยการสร้างบรรพบุรุษที่เป็นนามธรรมโดยสมบูรณ์ ในเวลาเดียวกัน ไม่ต้องสงสัยเลย การวิเคราะห์ของลูกหลานแต่ละคนจะเป็นแบบเรียกซ้ำและจะไม่แตกต่างกันมากนักในระดับเทคนิคในหลายตำแหน่ง (ตัวอักษร คำ วลี และประโยค) ย่อหน้าเช่นความคิดที่สมบูรณ์อาจโดดเด่นจากรายการนี้ แต่ก็ไม่ใช่สาระสำคัญ
มันสำคัญที่อัลกอริธึมส่วนที่ท่วมท้นสามารถกำหนดได้ในระดับบรรพบุรุษที่เป็นนามธรรม ปรับแต่งที่ระดับของลูกหลานแต่ละคนด้วยข้อมูลและวิธีการเรียกจากระดับนามธรรม ในบริบทนี้ สิ่งที่เป็นนามธรรมจะเปิดโลกทัศน์ใหม่สำหรับการเรียกซ้ำ
คุณสมบัติทางประวัติศาสตร์ของ OOP
OOP มาถึงโลกของซอฟต์แวร์ถึงสองครั้ง แม้ว่าผู้เชี่ยวชาญบางคนอาจจะแยกแยะการเกิดขึ้นของคลาวด์คอมพิวติ้งและแนวคิดสมัยใหม่เกี่ยวกับออบเจกต์และคลาสเป็นรอบใหม่ในการพัฒนาเทคโนโลยีไอที
คำว่า "วัตถุ" และ "วัตถุประสงค์" ในบริบทสมัยใหม่ของ OOP มักมีสาเหตุมาจากยุค 50 และ 60 ของศตวรรษที่ผ่านมา แต่มีความเกี่ยวข้องกับปี 1965 และการเกิดขึ้นของ Simula, Lisp, Algol, Smalltalk.
ในสมัยนั้น การเขียนโปรแกรมไม่ได้พัฒนาขึ้นเป็นพิเศษและไม่สามารถตอบสนองแนวคิดที่ปฏิวัติวงการได้อย่างเพียงพอ การต่อสู้ของความคิดและรูปแบบการเขียนโปรแกรม (C / C ++ และ Pascal - ส่วนใหญ่) ยังห่างไกลและฐานข้อมูลยังคงก่อตัวตามแนวคิด
ในช่วงปลายยุค 80 และต้นยุค 90 วัตถุปรากฏใน Pascal และทุกคนจำชั้นเรียนในภาษา C / C ++ ซึ่งเป็นจุดสนใจรอบใหม่เกี่ยวกับ OOP และเมื่อถึงเวลานั้นเครื่องมือซึ่งส่วนใหญ่เป็นภาษาโปรแกรมก็กลายเป็นไม่ สนับสนุนเฉพาะแนวคิดเชิงวัตถุ แต่พัฒนาตามนั้น
แน่นอน ถ้าอัลกอริธึมแบบเรียกซ้ำก่อนหน้านี้เป็นเพียงฟังก์ชันที่ใช้ในโค้ดทั่วไปของโปรแกรม ตอนนี้การเรียกซ้ำอาจกลายเป็นส่วนหนึ่งของคุณสมบัติของอ็อบเจ็กต์ (คลาส) ซึ่งให้โอกาสที่น่าสนใจในบริบทของการสืบทอด
คุณลักษณะของ OOP สมัยใหม่
การพัฒนา OOP ในขั้นต้นประกาศอ็อบเจ็กต์ (คลาส) เป็นการรวบรวมข้อมูลและคุณสมบัติ (เมธอด) อันที่จริง มันเป็นเรื่องของข้อมูลที่มีรูปแบบและความหมาย แต่ก็เป็นไปไม่ได้ที่จะนำเสนอ OOP เป็นเครื่องมือสำหรับจัดการวัตถุจริง
OOP กลายเป็นเครื่องมือสำหรับจัดการวัตถุ "ธรรมชาติของคอมพิวเตอร์" สคริปต์ ปุ่ม รายการเมนู แถบเมนู แท็กในหน้าต่างเบราว์เซอร์เป็นวัตถุ แต่ไม่ใช่เครื่องจักร ผลิตภัณฑ์อาหาร คำหรือประโยค วัตถุจริงยังคงอยู่นอกการเขียนโปรแกรมเชิงวัตถุ และเครื่องมือคอมพิวเตอร์ได้ถือกำเนิดขึ้นใหม่
เนื่องจากความแตกต่างในภาษาโปรแกรมยอดนิยม ภาษาถิ่นของ OOP มากมายจึงเกิดขึ้น ในแง่ของความหมาย พวกมันเทียบเท่ากันในทางปฏิบัติ และการมุ่งเน้นไปที่ทรงกลมเครื่องมือและไม่ได้อยู่ที่วงประยุกต์ทำให้สามารถอธิบายรายละเอียดของวัตถุจริงได้มากกว่าอัลกอริธึมและให้แน่ใจว่า "การมีอยู่" ข้ามแพลตฟอร์มและข้ามภาษา
สแตกและกลไกการเรียกฟังก์ชัน
กลไกสำหรับการเรียกใช้ฟังก์ชัน (ขั้นตอน, อัลกอริธึม) กำหนดให้ส่งข้อมูล (พารามิเตอร์) ส่งคืนผลลัพธ์ และจดจำที่อยู่ของโอเปอเรเตอร์ที่ต้องได้รับการควบคุมหลังจากฟังก์ชัน (ขั้นตอน) เสร็จสิ้น
โดยปกติ สแต็กจะถูกใช้เพื่อจุดประสงค์นี้ แม้ว่าภาษาโปรแกรมหรือผู้พัฒนาเองสามารถให้ตัวเลือกที่หลากหลายสำหรับการถ่ายโอนการควบคุม การเขียนโปรแกรมสมัยใหม่ยอมรับว่าชื่อของฟังก์ชันไม่เพียงแต่เป็นพารามิเตอร์เท่านั้น แต่ยังสามารถเกิดขึ้นได้ระหว่างการดำเนินการของอัลกอริธึม สามารถสร้างอัลกอริธึมได้ในขณะที่รันอัลกอริธึมอื่น
แนวคิดของอัลกอริธึมแบบเรียกซ้ำเมื่อชื่อและเนื้อความของพวกมันสามารถกำหนดได้ในเวลาของการก่อตัวของงาน (การเลือกอัลกอริธึมที่ต้องการ) ขยายการเรียกซ้ำไม่เพียง แต่จะต้องทำสิ่งใด แต่ยังรวมถึงใครบ้างที่ควร ทำมัน. การเลือกอัลกอริธึมด้วยชื่อที่ "มีความหมาย" นั้นมีแนวโน้มที่ดี แต่ก็สร้างปัญหาได้
การเรียกซ้ำในชุดฟังก์ชัน
คุณไม่สามารถพูดได้ว่าอัลกอริธึมเป็นแบบเรียกซ้ำเมื่อเรียกตัวเองและแค่นั้นเอง การเขียนโปรแกรมไม่ใช่ความเชื่อ และแนวคิดของการเรียกซ้ำไม่ใช่ข้อกำหนดพิเศษในการเรียกตัวเองจากเนื้อหาของอัลกอริธึมของคุณเอง
การใช้งานจริงไม่ได้ให้วิธีแก้ปัญหาที่สะอาดเสมอไป บ่อยครั้งต้องเตรียมข้อมูลเบื้องต้น และผลการเรียกซ้ำต้องได้รับการวิเคราะห์ในบริบทของปัญหาทั้งหมด (อัลกอริทึมทั้งหมด) ในโดยรวม
อันที่จริง ไม่เพียงแต่ก่อนที่จะเรียกใช้ฟังก์ชันแบบเรียกซ้ำ แต่หลังจากเสร็จสิ้นแล้ว โปรแกรมอื่นสามารถหรือควรถูกเรียก หากไม่มีปัญหาพิเศษกับการเรียก: ฟังก์ชันเรียกซ้ำ A() เรียกใช้ฟังก์ชัน B() ซึ่งทำบางสิ่งและเรียก A() แสดงว่ามีปัญหากับการกลับมาของการควบคุมในทันที หลังจากเสร็จสิ้นการเรียกซ้ำแล้ว ฟังก์ชัน A() จะต้องได้รับการควบคุมเพื่อเรียก B() อีกครั้ง ซึ่งจะเรียกใช้อีกครั้ง การคืนการควบคุมตามที่ควรจะเป็นในสแต็กกลับไปที่ B() เป็นวิธีแก้ปัญหาที่ผิด
โปรแกรมเมอร์ไม่จำกัดตัวเลือกพารามิเตอร์และสามารถเติมชื่อฟังก์ชันได้ กล่าวอีกนัยหนึ่ง ทางออกที่ดีคือส่งชื่อของ B() ไปยัง A() และให้ A() เรียก B() เอง ในกรณีนี้ จะไม่มีปัญหากับการส่งคืนการควบคุม และการใช้งานอัลกอริธึมแบบเรียกซ้ำจะมีความโปร่งใสมากขึ้น
ความเข้าใจและระดับของการเรียกซ้ำ
ปัญหาในการพัฒนาอัลกอริธึมแบบเรียกซ้ำคือคุณต้องเข้าใจพลวัตของกระบวนการ เมื่อใช้การเรียกซ้ำในเมธอดอ็อบเจ็กต์ โดยเฉพาะอย่างยิ่งในระดับบรรพบุรุษที่เป็นนามธรรม จะมีปัญหาในการทำความเข้าใจอัลกอริธึมของคุณเองในบริบทของเวลาดำเนินการ
ปัจจุบันไม่มีข้อจำกัดเกี่ยวกับระดับการซ้อนของฟังก์ชันและความจุของสแต็กในกลไกการโทร แต่มีปัญหาในการทำความเข้าใจ: ณ เวลาใดที่ระดับข้อมูลหรือตำแหน่งใดในอัลกอริธึมทั่วไปที่เรียกว่าการเรียกซ้ำ ทำหน้าที่และเรียกตัวเองว่านางได้กี่คน
เครื่องมือดีบั๊กที่มีอยู่มักจะไม่มีอำนาจบอกโปรแกรมเมอร์ถึงวิธีแก้ปัญหาที่ถูกต้อง
วนซ้ำและวนซ้ำ
ถือว่าการดำเนินการแบบวนซ้ำเทียบเท่ากับการเรียกซ้ำ ในบางกรณี อัลกอริธึมแบบเรียกซ้ำสามารถนำมาใช้ในไวยากรณ์ของโครงสร้างแบบมีเงื่อนไขและแบบวนได้
อย่างไรก็ตาม หากมีความเข้าใจชัดเจนว่าฟังก์ชันเฉพาะต้องถูกใช้งานผ่านอัลกอริธึมแบบเรียกซ้ำ การใช้งานภายนอกของคำสั่งวนซ้ำหรือคำสั่งแบบมีเงื่อนไขควรละทิ้ง
ความหมายในที่นี้คือโซลูชันแบบเรียกซ้ำในรูปแบบของฟังก์ชันที่ใช้ตัวเองจะเป็นอัลกอริธึมที่สมบูรณ์และใช้งานได้จริง อัลกอริธึมนี้ต้องการให้โปรแกรมเมอร์สร้างมันขึ้นมาด้วยความอุตสาหะ ทำความเข้าใจไดนามิกของอัลกอริธึม แต่มันจะเป็นทางออกสุดท้ายที่ไม่ต้องการการควบคุมจากภายนอก
การรวมกันของตัวดำเนินการเงื่อนไขภายนอกและแบบวนซ้ำใดๆ จะไม่อนุญาตให้เราแสดงอัลกอริทึมแบบเรียกซ้ำเป็นฟังก์ชันที่สมบูรณ์
ฉันทามติซ้ำและ OOP
ในเกือบทุกรูปแบบของการพัฒนาอัลกอริธึมแบบเรียกซ้ำ แผนเกิดขึ้นเพื่อพัฒนาสองอัลกอริธึม อัลกอริธึมแรกสร้างรายการของอ็อบเจ็กต์ในอนาคต (อินสแตนซ์) และอัลกอริธึมที่สองจริงๆ แล้วเป็นฟังก์ชันแบบเรียกซ้ำ
ทางออกที่ดีที่สุดคือการจัดเรียงการเรียกซ้ำเป็นคุณสมบัติเดียว (เมธอด) ที่มีอัลกอริธึมแบบเรียกซ้ำจริงๆ และใส่งานเตรียมการทั้งหมดลงในตัวสร้างวัตถุ
อัลกอริธึมแบบเรียกซ้ำจะเป็นทางออกที่ถูกต้องเมื่อใช้งานได้ด้วยตัวเองเท่านั้น โดยปราศจากการควบคุมและการจัดการจากภายนอก อัลกอริธึมภายนอกสามารถให้สัญญาณทำงานได้เท่านั้น ผลลัพธ์ของงานนี้ควรเป็นวิธีแก้ปัญหาที่คาดไว้ โดยไม่มีการสนับสนุนจากภายนอก
การเรียกซ้ำควรเป็นวิธีการแก้ปัญหาแบบสแตนด์อโลนที่สมบูรณ์เสมอ
เข้าใจง่ายและใช้งานได้จริง
เมื่อการเขียนโปรแกรมเชิงวัตถุกลายเป็นมาตรฐานโดยพฤตินัย เป็นที่ชัดเจนว่าการจะเขียนโค้ดได้อย่างมีประสิทธิภาพ คุณต้องเปลี่ยนความคิดของคุณเอง โปรแกรมเมอร์ต้องเปลี่ยนจากไวยากรณ์และความหมายของภาษาไปเป็นไดนามิกของความหมายระหว่างการดำเนินการของอัลกอริทึม
ลักษณะของการเรียกซ้ำ: ใช้ได้กับทุกอย่าง:
- ขูดเว็บ
- การดำเนินการค้นหา;
- แยกวิเคราะห์ข้อความ;
- กำลังอ่านหรือสร้างเอกสาร MS Word;
- สุ่มตัวอย่างหรือวิเคราะห์แท็ก…
ลักษณะของ OOP: ทำให้สามารถอธิบายอัลกอริธึมแบบเรียกซ้ำที่ระดับบรรพบุรุษที่เป็นนามธรรมได้ แต่กำหนดให้ใช้เพื่ออ้างถึงทายาทที่ไม่ซ้ำกัน ซึ่งแต่ละรายการมีชุดข้อมูลและคุณสมบัติเป็นของตัวเอง
การเรียกซ้ำเหมาะอย่างยิ่งเพราะต้องการความสมบูรณ์ในการทำงานของอัลกอริทึม OOP ปรับปรุงประสิทธิภาพของอัลกอริธึมแบบเรียกซ้ำโดยให้สิทธิ์เข้าถึงลูกที่ไม่ซ้ำกันทั้งหมด
