recursion เป็นกระบวนการของการกำหนดบางสิ่งในแง่ของตัวเอง เนื่องจากเกี่ยวข้องกับการเขียนโปรแกรม Java การเรียกซ้ำเป็นแอ็ตทริบิวต์ที่อนุญาตให้เมธอดเรียกตัวเอง วิธีการที่เรียกตัวเองว่าเป็นแบบเรียกซ้ำและ Java รองรับการเรียกซ้ำ
ในตอนแรกนี่อาจดูเหมือนวนรอบไม่สิ้นสุดและดูเหมือนว่าวิธีการของเราจะไม่จบ นี่อาจเป็นจริงในบางกรณี แต่ในทางปฏิบัติเราสามารถตรวจสอบเพื่อดูว่าเงื่อนไขบางอย่างเป็นจริงและในกรณีนั้นทางออก (กลับจาก) วิธีการของเรา กรณีที่เรายุติการสอบถามซ้ำของเราเรียกว่า กรณีฐาน. นอกจากนี้เช่นเดียวกับในวงเราต้องเปลี่ยนค่าบางอย่างและเพิ่มขึ้นใกล้กับกรณีฐานของเรา
การสอบถามซ้ำทุกครั้งควรมีลักษณะดังต่อไปนี้:
- เคสพื้นฐานแบบง่าย ๆ ที่เรามีทางออกให้และคืนค่า
- วิธีที่ทำให้ปัญหาของเราใกล้เคียงกับกรณีพื้นฐานมากขึ้น เช่นวิธีการแยกส่วนของปัญหาเพื่อให้ได้ปัญหาที่ค่อนข้างง่ายขึ้น
- การเรียกซ้ำที่ส่งผ่านปัญหาที่ง่ายกว่ากลับเข้าสู่วิธีการ
ข้อดี
หลักในการเรียกซ้ำวิธีคือพวกเขาสามารถใช้ในการสร้างอัลกอริทึมหลายรุ่นที่ชัดเจนและเรียบง่ายกว่าญาติซ้ำของพวกเขา ตัวอย่างเช่นอัลกอริทึมการเรียงลำดับ QuickSort นั้นค่อนข้างยากที่จะนำไปใช้ในทางวนซ้ำ
ข้อเสีย
เวอร์ชันเรียกซ้ำของรูทีนจำนวนมากอาจดำเนินการช้ากว่าการทำซ้ำเล็กน้อยเนื่องจากค่าใช้จ่ายที่เพิ่มเข้ามาของการเรียกฟังก์ชันเพิ่มเติม การเรียกแบบเรียกซ้ำหลายครั้งไปยังเมธอดอาจทำให้สแตกที่เกิน เนื่องจากหน่วยเก็บสำหรับพารามิเตอร์และตัวแปรโลคัลเป็นไปได้ที่สแต็กอาจถูกใช้จนหมด หากสิ่งนี้เกิดขึ้นระบบรันไทม์ของ java จะทำให้เกิดข้อยกเว้น อย่างไรก็ตามคุณอาจไม่ต้องกังวลเกี่ยวกับเรื่องนี้เว้นแต่ว่ากิจวัตรเรียกซ้ำจะทำงานอย่างดุเดือด
ตัวอย่างเช่น:
int myFactorial(int integer) {
if( integer == 1) {
return 1;
}
else {
return(integer*(myFactorial(integer-1);
}
}การเรียกซ้ำแบบหางถูกกำหนดเป็นสิ่งที่เกิดขึ้นเมื่อการเรียกซ้ำแบบเรียกซ้ำจะอยู่ท้ายการเรียนการสอนแบบเรียกซ้ำ นี่ไม่ใช่กรณีด้วยโซลูชันแฟคทอเรียลของฉันด้านบน มันจะมีประโยชน์ที่จะสังเกตเห็นเมื่ออัลกอริทึมที่ใช้เรียกซ้ำหางเพราะในกรณีเช่นนี้อัลกอริทึมสามารถเขียนใหม่เพื่อใช้ซ้ำได้ ในความเป็นจริงคอมไพเลอร์จะ (หรืออย่างน้อยควร) แปลงโปรแกรมเวียนซ้ำเป็นโปรแกรมซ้ำ สิ่งนี้จะช่วยลดปัญหาที่อาจเกิดขึ้นจากการล้นสแต็ก
นี่ไม่ใช่กรณีที่มีการเรียกซ้ำหัวหน้าหรือเมื่อฟังก์ชั่นนี้เรียกตัวเองซ้ำ ๆ ในสถานที่ต่าง ๆ เช่นในโซลูชันหอคอยแห่งฮานอย แน่นอนแม้ในกรณีเหล่านี้เราสามารถลบการสอบถามซ้ำโดยใช้สแต็กของเราเองและจำลองการทำงานของการเรียกซ้ำ
ในตัวอย่างของแฟคทอเรียลด้านบนคอมไพเลอร์จะต้องเรียกใช้ฟังก์ชันเรียกซ้ำก่อนที่จะทำการคูณเนื่องจากต้องแก้ไขค่า (คืน) ของฟังก์ชันก่อนที่จะทำการคูณได้ ดังนั้นคำสั่งของการดำเนินการจะเป็นการเรียกซ้ำแบบ“ head” เช่นการเรียกซ้ำเกิดขึ้นก่อนการดำเนินการอื่น
ในการแปลงเป็น tail recursion เราต้องได้การคูณทั้งหมดเสร็จสิ้นและได้รับการแก้ไขก่อนที่จะเรียกใช้ฟังก์ชันซ้ำ เราจำเป็นต้องบังคับลำดับของการดำเนินการเพื่อที่เราจะไม่รอการคูณก่อนกลับ ถ้าเราทำเช่นนี้เฟรมสแต็กสามารถทำให้เป็นอิสระขึ้น
ก่อนหน้านี้คุณเคยเห็นโปรแกรม Java ของเราเพื่อคำนวณแฟคทอเรียลของจำนวนเต็ม
วิธีที่เหมาะสมในการทำแฟกทอเรียลแบบเรียกซ้ำคือ:
int factorial(int number) {
if(number == 0) {
return 1;
}
factorial_i(number, 1);
}
int factorial_i(int currentNumber, int sum) {
if(currentNumber == 1) {
return sum;
} else {
return factorial_i(currentNumber - 1, sum*currentNumber);
}
}สังเกตว่าในการโทรกลับfactorial_i (currentNumber - 1, รวม * currentNumber); พารามิเตอร์ทั้งสองสามารถแก้ไขได้ทันที เราสามารถคำนวณว่าแต่ละพารามิเตอร์คืออะไรโดยไม่ต้องรอการเรียกฟังก์ชันเรียกซ้ำเพื่อส่งกลับ นี่ไม่ใช่กรณีของแฟกทอเรียลรุ่นก่อนหน้า การทำให้เพรียวลมนี้ช่วยให้คอมไพเลอร์ลดการใช้สแต็กน้อยที่สุดตามที่อธิบายไว้ข้างต้น
คุณยังสามารถใช้หมายเลขจากผู้ใช้เป็นอาร์กิวเมนต์บรรทัดคำสั่ง
โปรแกรม Java Recursion
class Factorial{
int fact(int n){
int result;
if ( n ==1)
return 1;
result = fact (n-1) * n;
return result;
}
}
class Recursion{
public static void main (String args[]){
Factorial f =new Factorial();
System.out.println("Factorial of 3 is " + f.fact(3));
System.out.println("Factorial of 4 is " + f.fact(4));
System.out.println("Factorial of 5 is " + f.fact(5));
}
}เอาท์พุต
คำอธิบายของรหัส Java & ผลผลิต
หากคุณไม่คุ้นเคยกับวิธีแบบเรียกซ้ำการดำเนินการของ ความเป็นจริง () อาจดูสับสนเล็กน้อย นี่คือวิธีการทำงาน เมื่อไหร่ ความเป็นจริง () ถูกเรียกด้วยอาร์กิวเมนต์ 1 ฟังก์ชันจะส่งคืนค่า 1 มิฉะนั้นจะส่งคืนผลิตภัณฑ์ของ ความเป็นจริง (n-1) * n เพื่อประเมินการแสดงออกนี้ ความเป็นจริง () เรียกว่าด้วย n-1. กระบวนการนี้ซ้ำจนกระทั่ง n เท่ากับ 1 และการเรียกไปยังเมธอดเริ่มส่งคืน
เพื่อให้เข้าใจถึงวิธีการ ความเป็นจริง () วิธีการทำงานให้ผ่านตัวอย่างสั้น ๆ เมื่อคุณคำนวณแฟคทอเรียลของ 3 การโทรครั้งแรกถึง ความเป็นจริง () จะทำให้เกิดการโทรครั้งที่สองที่มีอาร์กิวเมนต์เป็น 2 การเรียกใช้นี้จะทำให้เกิด ความเป็นจริง () ถูกเรียกเป็นครั้งที่สามโดยมีอาร์กิวเมนต์เป็น 2 การโทรนี้จะส่งคืน 1 ซึ่งจะถูกเรียกเป็นครั้งที่สามโดยมีอาร์กิวเมนต์เป็น 1 การโทรนี้จะส่งกลับ 1 ซึ่งจะถูกคูณด้วย 2 แล้ว (มูลค่าของ n ในการร้องขอครั้งที่สอง) ผลลัพธ์นี้ (ซึ่งคือ 2) จะถูกส่งกลับไปยังการร้องขอเริ่มต้นของ ความเป็นจริง () และคูณด้วย 3 (ค่าดั้งเดิมของ n) นี่ให้คำตอบที่ 6 คุณอาจพบว่ามันน่าสนใจที่จะใส่ println () งบเข้า ความเป็นจริง () ซึ่งจะแสดงระดับการโทรแต่ละครั้งและคำตอบระดับกลางคืออะไร
เมื่อวิธีการเรียกตัวเองตัวแปรท้องถิ่นใหม่และพารามิเตอร์ได้รับการจัดสรรพื้นที่เก็บข้อมูลบนสแต็กและรหัสวิธีการจะดำเนินการกับตัวแปรใหม่เหล่านี้ตั้งแต่เริ่มต้น การเรียกซ้ำจะไม่ทำสำเนาวิธีการใหม่ ข้อโต้แย้งใหม่เท่านั้น เมื่อการเรียกซ้ำแบบเรียกคืนแต่ละครั้งตัวแปรและพารามิเตอร์ในเครื่องเก่าจะถูกลบออกจากสแต็กและการดำเนินการจะดำเนินการต่อที่จุดของการโทรภายในเมธอด
ต่อไปเราจะเรียนรู้วิธีจัดการกับ Array ใน Java.
ชำระเงินบทเรียนที่มีประโยชน์มากขึ้นและแนวทางที่ชัดเจนในการเขียนโปรแกรม Java ที่นี่
ความคิดเห็น