คำนำ
ฉันเห็นเนื้อหานี้เมื่อเร็ว ๆ นี้เมื่อฉันอ่านหนังสือและฉันรู้สึกว่าค่อนข้างคุ้มค่า การวนซ้ำใช้ลูป (สำหรับในขณะที่ทำ ... wile) หรือตัววนซ้ำซึ่งจะออกเมื่อไม่ตรงกับเงื่อนไขการวนซ้ำ การเรียกซ้ำโดยทั่วไปเป็นฟังก์ชันการเรียกซ้ำซึ่งสามารถเรียกได้ด้วยตัวเองหรือโดยการโทรที่ไม่ใช่ทิศทางนั่นคือวิธีการเรียกวิธีการโทร B และวิธีการเรียกวิธี B ในทางกลับกันและเงื่อนไขสำหรับการออกซ้ำเป็นคำสั่ง IF และอื่น ๆ และออกเมื่อเงื่อนไขตรงตามพื้นฐาน
ข้างต้นเป็นลักษณะทางไวยากรณ์ของการทำซ้ำและการเรียกซ้ำ อะไรคือความแตกต่างระหว่างพวกเขาใน Java? มาเรียนรู้เพิ่มเติมเกี่ยวกับบทความนี้ด้านล่าง
1. การเรียกซ้ำ
เมื่อพูดถึงการทำซ้ำเราต้องพูดถึงการแสดงออกทางคณิตศาสตร์: n!=n*(n-1)*(n-2)*...*1
มีหลายวิธีในการคำนวณแฟคทอเรียล ใครก็ตามที่มีรากฐานทางคณิตศาสตร์บางอย่างรู้ n!=n*(n-1)! ดังนั้นการใช้รหัสสามารถเขียนได้โดยตรงเป็น:
รหัส 1
int factorial (int n) {ถ้า (n == 1) {return 1; } else {return n*factorial (n-1); - เมื่อดำเนินการรหัสข้างต้นเครื่องจะต้องทำการคูณชุด: factorial(n) → factorial(n-1) → factorial(n-2) →…→ factorial(1) ดังนั้นจึงจำเป็นต้องติดตาม (ติดตามผลลัพธ์ของการคำนวณครั้งสุดท้าย) และการคูณการโทรเพื่อทำการคำนวณ (สร้างห่วงโซ่การคูณ) การดำเนินการประเภทนี้ที่เรียกตัวเองอย่างต่อเนื่องเรียกว่าการเรียกซ้ำ การเรียกซ้ำสามารถแบ่งออกเป็นการเรียกซ้ำเชิงเส้นและการเรียกซ้ำตัวเลข จำนวนข้อมูลเพิ่มขึ้นเชิงเส้นด้วยอินพุตของอัลกอริทึม การเรียกซ้ำเรียกว่าการเรียกซ้ำเชิงเส้น คำนวณ n! (โรงงาน) เป็นการเรียกซ้ำเชิงเส้น เพราะเมื่อ N เพิ่มขึ้นเวลาที่ต้องใช้ในการคำนวณจะเพิ่มขึ้นเป็นเส้นตรง ข้อมูลประเภทอื่นที่เติบโตแบบทวีคูณเมื่อเพิ่มอินพุตเรียกว่าการเรียกซ้ำของต้นไม้
2. การวนซ้ำ
อีกวิธีหนึ่งในการคำนวณ N! IS: แรกคำนวณ 1 คูณด้วย 2 จากนั้นคูณผลลัพธ์ด้วย 3 จากนั้นคูณผลลัพธ์ด้วย 4 ... และคูณจนกระทั่ง N. ในระหว่างการใช้งานโปรแกรมสามารถกำหนดตัวนับได้ แต่ละครั้งจะทำการคูณตัวนับจะเพิ่มขึ้นหนึ่งครั้งจนกว่าค่าของตัวนับจะเท่ากับ N รหัสมีดังนี้:
รหัสสอง
int factorial (int n) {int product = 1; สำหรับ (int i = 2; i <n; i ++) {ผลิตภัณฑ์ *= i; } return product;}เปรียบเทียบกับรหัสหนึ่งรหัสสองไม่ได้สร้างห่วงโซ่การคูณ เมื่อทำการคำนวณแต่ละขั้นตอนคุณจะต้องทราบผลลัพธ์ปัจจุบัน (ผลิตภัณฑ์) และค่าของ i รูปแบบการคำนวณนี้เรียกว่าการวนซ้ำ มีหลายเงื่อนไขสำหรับการทำซ้ำ: 1. มีตัวแปรที่มีค่าเริ่มต้น 2. กฎที่อธิบายว่าค่าตัวแปรได้รับการอัปเดตอย่างไร 3. เงื่อนไขสิ้นสุด (องค์ประกอบสามประการของลูป: ตัวแปรลูป, ร่างกายลูปและเงื่อนไขการเลิกจ้างลูป) เช่นเดียวกับการเรียกซ้ำ ความต้องการเวลาที่กลายเป็นเส้นตรงเมื่ออินพุตเติบโตเป็นเส้นตรงสามารถเรียกว่าการวนซ้ำเชิงเส้น
3. การทำซ้ำกับการเรียกซ้ำ
หลังจากเปรียบเทียบทั้งสองโปรแกรมเราสามารถพบว่าพวกเขามีลักษณะเหมือนกันเกือบเหมือนกันโดยเฉพาะอย่างยิ่งในแง่ของฟังก์ชั่นทางคณิตศาสตร์ของพวกเขา เมื่อคำนวณ n! ขั้นตอนการคำนวณของพวกเขาจะเป็นสัดส่วนกับค่าของ n อย่างไรก็ตามหากเราใช้มุมมองของโปรแกรมและพิจารณาว่าพวกเขาทำงานอย่างไรอัลกอริทึมทั้งสองนั้นแตกต่างกันมาก
(หมายเหตุ: ข้อความต้นฉบับไม่เกี่ยวข้องเล็กน้อยเกี่ยวกับความแตกต่างดังนั้นฉันจะไม่แปลที่นี่ต่อไปนี้เป็นบทสรุปของผู้เขียนเอง)
ก่อนอื่นวิเคราะห์การเรียกซ้ำ ในความเป็นจริงสิ่งที่ยิ่งใหญ่ที่สุดเกี่ยวกับการเรียกซ้ำคือการย่อยสลายอัลกอริทึมที่ซับซ้อนเป็นขั้นตอนที่ทำซ้ำได้หลายขั้นตอน ดังนั้นการใช้การเรียกซ้ำเพื่อใช้ตรรกะการคำนวณมักจะต้องใช้รหัสสั้น ๆ เท่านั้นในการแก้ปัญหาและรหัสดังกล่าวง่ายต่อการเข้าใจ อย่างไรก็ตามการเรียกซ้ำหมายถึงการเรียกใช้ฟังก์ชันจำนวนมาก เหตุผลที่สถานะท้องถิ่นของการเรียกใช้ฟังก์ชันถูกบันทึกโดยใช้สแต็ก ดังนั้นสิ่งนี้อาจเสียพื้นที่มากและหากการเรียกซ้ำนั้นลึกเกินไปอาจทำให้สแต็คล้น
ถัดไปวิเคราะห์การวนซ้ำ ในความเป็นจริงการเรียกซ้ำสามารถแทนที่ด้วยการทำซ้ำ อย่างไรก็ตามเมื่อเปรียบเทียบกับความเรียบง่ายและความเข้าใจในการเรียกซ้ำการวนซ้ำจะเข้มงวดและเข้าใจยากมากขึ้น โดยเฉพาะอย่างยิ่งเมื่อเผชิญกับสถานการณ์ที่ซับซ้อนมากขึ้น อย่างไรก็ตามความยากลำบากในการทำความเข้าใจรหัสยังนำมาซึ่งจุดที่ชัดเจนยิ่งขึ้น ประสิทธิภาพของการทำซ้ำสูงกว่าการเรียกซ้ำและยังมีขนาดค่อนข้างเล็กในการบริโภคอวกาศ
จะต้องมีการวนซ้ำในการเรียกซ้ำ แต่อาจไม่มีการเรียกซ้ำในการวนซ้ำและส่วนใหญ่สามารถแปลงกันได้
หากคุณสามารถใช้การวนซ้ำได้อย่าใช้การเรียกซ้ำ ฟังก์ชั่นการโทรซ้ำไม่เพียง แต่เสียพื้นที่ แต่ยังสามารถทำให้สแต็คล้นได้อย่างง่ายดายหากการเรียกซ้ำนั้นลึกเกินไป
4. การเรียกซ้ำของตัวเลข
ดังที่ได้กล่าวไว้ก่อนหน้านี้จำนวนข้อมูลที่ต้นไม้เรียกซ้ำเพิ่มขึ้นแบบทวีคูณเมื่อเพิ่มอินพุต ลำดับ Fibonacci เป็นตัวอย่างทั่วไป:
ในคำอธิบายข้อความผลรวมของตัวเลขสองตัวแรกในลำดับ Fibonacci เท่ากับหมายเลขที่สาม: 0, 1, 1, 2, 3, 5, 8, 13, 21 ...
รหัสการใช้งานแบบเรียกซ้ำมีดังนี้:
int fib (int n) {ถ้า (n == 0) {return 0; } อื่นถ้า (n == 1) {return 1; } else {return fib (n-1) + fib (n-2); - ในระหว่างกระบวนการคำนวณเพื่อคำนวณ fib(5) โปรแกรมจะต้องคำนวณ fib(4) และ fib(3) ก่อน ในการคำนวณ fib(4) โปรแกรมยังต้องคำนวณ fib(3) และ fib(2) ก่อน FIB (3) คำนวณสองครั้งในระหว่างกระบวนการนี้
จากกระบวนการคำนวณที่วิเคราะห์ข้างต้นเราสามารถสรุปได้: มีการคำนวณซ้ำซ้อนสำหรับการใช้ลำดับ Fibonacci โดยใช้การเรียกซ้ำ
ดังที่ได้กล่าวไว้ข้างต้นอัลกอริทึมแบบเรียกซ้ำโดยทั่วไปสามารถนำไปใช้โดยการวนซ้ำและสิ่งเดียวกันนั้นเป็นจริงสำหรับการคำนวณลำดับ Fibonacci
int fib (int n) {int fib = 0; int a = 1; สำหรับ (int i = 0; i <n; i ++) {int temp = fib; FIB = FIB + A; A = อุณหภูมิ; } return fib;}แม้ว่าจะมีการคำนวณซ้ำซ้อนในวิธีการเรียกซ้ำ แต่ก็สามารถแทนที่ด้วยการทำซ้ำ แต่นี่ไม่ได้หมายความว่าการเรียกซ้ำสามารถเปลี่ยนได้อย่างสมบูรณ์ เพราะการเรียกซ้ำมีความสามารถในการอ่านได้ดีขึ้น
สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่าเนื้อหาของบทความนี้จะเป็นประโยชน์กับทุกคนในการเรียนรู้หรือใช้ Java หากคุณมีคำถามใด ๆ คุณสามารถฝากข้อความไว้เพื่อสื่อสาร