1. ฟังก์ชันแบบเรียกซ้ำ ในแง่คนธรรมดา หมายความว่าฟังก์ชันนั้นเรียกตัวเองว่า...
เช่น: n!=n(n-1)!
คุณกำหนดฟังก์ชัน f(n)=nf(n-1)
และ f(n-1) เป็นฟังก์ชันของนิยามนี้ - นี่คือการเรียกซ้ำ
2. เหตุใดจึงต้องใช้การเรียกซ้ำ: จุดประสงค์ของการเรียกซ้ำคือเพื่อทำให้การออกแบบโปรแกรมง่ายขึ้น และทำให้โปรแกรมอ่านง่ายขึ้น
3. ข้อเสียของการเรียกซ้ำ: แม้ว่าฟังก์ชันที่ไม่เรียกซ้ำจะมีประสิทธิภาพสูง แต่ก็เป็นเรื่องยากที่จะโปรแกรมและอ่านได้ไม่ดี ข้อเสียของฟังก์ชันแบบเรียกซ้ำคือการเพิ่มโอเวอร์เฮดของระบบ กล่าวคือ ทุกครั้งที่มีการเรียกซ้ำ หน่วยความจำแบบสแต็กจะใช้พื้นที่มากขึ้น
4. เงื่อนไขสำหรับการเรียกซ้ำ: ต้องมีคำสั่งเพื่อให้งานสำเร็จ และต้องเป็นไปตามข้อกำหนดสำหรับการเรียกซ้ำ (ลดมากกว่าแยกออก)
5. ความก้าวหน้าแบบเรียกซ้ำ:
1. ใช้การเรียกซ้ำเพื่อคำนวณแฟกทอเรียลของ n:
วิเคราะห์: n!=n*(n-1)*(n-2)...*1
สาธารณะ int dReturn (int n) { if (n = = 1) { return 1; } else { return n * dReturn (n-1);2. ใช้ฟังก์ชันเรียกซ้ำเพื่อคำนวณการสะสมจาก 1 ถึง n: 1+2+3+4+..+n
สาธารณะ int dReturn (int n) { if (n = = 1) { return 1; } อื่น ๆ { return n + dReturn (n-1); 3. จำเป็นต้องส่งออกลำดับ: 1,1,2,3,5,8,11... (แต่ละตัวเลขคือผลรวมของตัวเลขสองตัวก่อนหน้า และจำเป็นต้องมีฟังก์ชันแบบเรียกซ้ำ)
ใช้การเรียกซ้ำของ Java เพื่อแสดงฟังก์ชัน: F(n)=F(n-1)+F(n-2);F(0)=1;F(1)=1;
วิเคราะห์: X1=1; X2=1; X3=X1+X2;
สาธารณะ int F(int n){ if(n==1){ return 1; }else if(n==2){ return 1; }else{ return F(n-1)+F(n-2); } }4.Java ใช้วิธีการเรียกซ้ำเพื่อพิมพ์แต่ละองค์ประกอบในอาร์เรย์จำนวนเต็มแบบย้อนกลับ
โมฆะคงที่สาธารณะ printAll (ดัชนี int [] arr) { System.out.println (arr [ดัชนี]); if (ดัชนี > 0) { printAll (--index, arr); } โมฆะคงที่สาธารณะ main (String [] args){ int[] arr={1,2,3,4,5}; printAll(arr.lenth-1,arr); }5. วิธีแก้ปัญหาการเขียนโปรแกรม: หากวัวสาวออกลูกทุกปีโดยเริ่มตั้งแต่ปีที่สี่หลังคลอด ในปีที่ n จะมีวัวกี่ตัว?
วัว int สาธารณะ (int n) { if (n <= 0) { return 0; } else if (n <= 3) { return 1; } else { return วัว (n-1) + วัว (n-3) ; } } public static void main(String[] args){ int n=10; System.out.println(n+"จะมีจำนวนทั้งหมด "+cattle(n)+"cows" }แนวคิดของการเรียกซ้ำ การเรียกซ้ำเชิงเส้น และการเรียกซ้ำส่วนท้ายมีอะไรบ้าง
การเรียกใช้ฟังก์ชันแบบเรียกซ้ำใน Java - การค้นหาแฟกทอเรียลของตัวเลข
ไม่พิจารณาโอเวอร์โฟลว์ โดยทั่วไปจะคำนวณได้เฉพาะแฟกทอเรียลของ 69 เท่านั้น...
หมายเหตุ: แฟกทอเรียลของ 0 คือ 0! =1
การแทนค่าแฟกทอเรียลของจำนวนธรรมชาติใดๆ ที่มากกว่า 1:
น!=1×2×3×……×n
หรือ n!=n×(n-1)!
การค้นหาแฟกทอเรียลเป็น 0 จะแสดงเครื่องคิดเลขออนไลน์ขึ้นมา ซึ่งมีประโยชน์มาก! -
การทดสอบแพ็คเกจนำเข้า java.util.Scanner; public class DiGui {public static void main(String[] args) {// TODO วิธีการสร้างอัตโนมัติ stubSystem.out.println("Enter an integer:");Scanner scan = new สแกนเนอร์(System.in);int x = scan.nextInt();int ผลลัพธ์ = digui(x);System.out.println(result);}//ฟังก์ชันแบบเรียกซ้ำ public static int digui(int x){if(x<=0){return 1;}else{return x*digui(x-1 );}}}การเรียกซ้ำ: กระบวนการหรือฟังก์ชันมีวิธีการเรียกตัวเองทั้งทางตรงและทางอ้อมในคำจำกัดความหรือคำอธิบาย โดยปกติแล้วจะเปลี่ยนปัญหาใหญ่และซับซ้อนให้เป็นปัญหาเล็กลงคล้ายกับปัญหาเดิมที่ต้องแก้ไข กรณีนี้แสดงให้เห็นอย่างชัดเจนว่าการเรียกซ้ำสามารถเปลี่ยนปัญหาที่ซับซ้อนให้กลายเป็นปัญหาเล็กๆ ที่ต้องแก้ไขได้อย่างไร ต่อไปนี้เป็นตัวอย่างเล็กๆ เพื่อแสดงหลักการของการเรียกซ้ำ
/*** @fileName Test.java* @description ??????????* @date 2555-11-25* @time 17:30* @author wst*/public class Test { static int multiply( int n) { int factorial; // ?? if ((n == 1) || (n == 0)) { factorial = n; } else { แฟกทอเรียล = n * คูณ (n - 1); ; } สาธารณะคงโมฆะหลัก (สตริง [] args) { System.out.println (คูณ (5) }} เมื่อเรียกใช้ฟังก์ชัน พื้นที่สำหรับตัวแปรจะถูกสร้างขึ้นบนรันไทม์สแต็ก ตัวแปรของฟังก์ชันที่เรียกก่อนหน้านี้ยังคงอยู่ในสแต็ก แต่จะถูกบดบังด้วยตัวแปรของฟังก์ชันใหม่ ดังนั้นจึงไม่สามารถเข้าถึงได้
ฟังก์ชันในโปรแกรมมีตัวแปรสองตัว: พารามิเตอร์ n และตัวแปรเฉพาะที่ แฟกทอเรียล ไดอะแกรมต่อไปนี้แสดงสถานะของสแต็ก โดยมีตัวแปรที่สามารถเข้าถึงได้ในปัจจุบันอยู่ที่ด้านบน ตัวแปรที่ถูกเรียกอื่นๆ ทั้งหมดจะเป็นสีเทาเพื่อระบุว่าไม่สามารถเข้าถึงได้โดยฟังก์ชันที่กำลังดำเนินการอยู่
สมมติว่าเราเรียกฟังก์ชันแบบเรียกซ้ำด้วยค่า 5 เนื้อหาของสแต็กมีดังนี้ โดยด้านบนของสแต็กอยู่ด้านล่าง:
n คูณ(n) แฟคทอเรียล 5 คูณ(5) 5*คูณ(4) // เรียกครั้งแรก 4 คูณ(4) 4*คูณ(3) //เรียกครั้งที่สอง 3 คูณ(3) 3*คูณ(2 ) //การ โทรครั้งที่สาม 2 คูณ (2) 2*คูณ (1) // โทรครั้งที่สี่ 1 คูณ (1) 1 // โทรครั้งที่ห้า
จากข้อมูลข้างต้น จะเห็นได้ง่ายว่าการเรียกซ้ำจะค่อยๆ ลดปัญหาให้เหลือน้อยที่สุดได้อย่างไร เริ่มต้นจากการเรียกเมธอด ผลลัพธ์แฟคทอเรียลจะถูกพุชไปยังสแต็กจนกว่าการเรียกเมธอดจะสิ้นสุด และสุดท้ายผลลัพธ์จะถูกส่งกลับทีละรายการ จากด้านบนของสแต็ก หลังจากเปลี่ยนทีละตัวผลลัพธ์จะเป็นดังนี้:
n=1 1 ส่งคืน 1 ขึ้นไป
n=2 2*คูณ(1) คืนค่า 2*1=2 ขึ้นไป
n=3 3*คูณ(2) ส่งกลับ 3*(2*1)=6 ขึ้นไป
n=4 4*คูณ(3) ส่งกลับ 4*(3*(2*1))=24 ขึ้นไป
n=5 5*คูณ(4) ส่งกลับขึ้นไป 5*(4*(3*(2*1)))=120
หมายเหตุ: เนื่องจากการคูณ (1) หรือคูณ (0) จะส่งกลับค่า 1
จึงมี 2*คูณ(1)=2*1=2
และเนื่องจากการคูณ(2) ตรงตามเงื่อนไขการเรียกซ้ำ จึงสามารถแปลงเป็น 2*คูณ(1) ได้หลังจากการเรียกซ้ำ
จึงมี 3*คูณ(2)=3*(2*คูณ(1))=3*(2*1)=6
เนื่องจากการคูณ (3) สามารถลดลงเหลือ 3* คูณ (2) ได้หลังจากการเรียกซ้ำ
ดังนั้น คูณ(4)=4*คูณ(3)=4*(3*คูณ(2))=4*(3*(2*1))=24
โดยการเปรียบเทียบ ให้คูณ(5)=5*คูณ(4)
สามารถลดลงเหลือ 5*(4*คูณ(3))=5*(4*3*(คูณ(2)))=5*(4*(3*(2*1)))=120
มาดูข้อมูลรหัสไบต์กันดีกว่า:
การทดสอบคลาสสาธารณะขยาย java.lang.Object{ การทดสอบสาธารณะ (); รหัส: 0: aload_0 1: เรียกใช้พิเศษ #1; //Method java/lang/Object"<init>":()V 4: คืนค่า int แบบคงที่ (int); รหัส: 0: iload_0 1:iconst_1 //กด int ประเภทค่าคงที่ 1 ลงบนสแต็ก 2: if_icmpeq 9 //เปรียบเทียบค่าประเภท int สองค่า หากเท่ากัน ให้ข้ามไปที่ตำแหน่ง 9 นี่คือฟังก์ชันลัดวงจรของ ||5: iload_0 //การดำเนินการนี้เมื่อเงื่อนไขแรกไม่คงอยู่ โดยเริ่มจากตัวแปรโลคัล 0 โหลด ค่าประเภท int (กดค่า n ลงบนสแต็ก) 6: ifne 14 //เปรียบเทียบ ถ้าไม่เท่ากับ 0 ให้ข้ามไปที่ตำแหน่ง 14 หมายเหตุ: เนื่องจากค่าเริ่มต้นที่นี่ถูกเปรียบเทียบกับ 0 จึงไม่จำเป็นต้องเปลี่ยน ค่าคงที่เป็น 0 กด 9: iload_0 // ถ้าไม่มีการข้ามไปที่ ifne ให้โหลดค่าประเภท int จากตัวแปรโลคัล 0 (กดค่า n ลงบนสแต็ก) 10: istore_1 // เก็บค่าประเภท int ลงในตัวแปรโลคัล 1 (ป๊อปค่าที่ด้านบน ของสแต็ก) นั่นคือค่าของตัวแปรโลคัล 0 จะถูกผลักลงบนสแต็กแล้วเก็บไว้ในตัวแปรโลคัล 1) 11: ไปที่ 23 // ข้ามไปยังตำแหน่ง 23 โดยไม่มีเงื่อนไข 14: iload_0 //เปรียบเทียบที่ตำแหน่ง 6 หากไม่เท่ากับ 0 ให้รันคำสั่งนี้และโหลดค่าประเภท int จากตัวแปรโลคัล 0 (กดค่า n ลงบนสแต็ก) 15: iload_0 //โหลดค่าประเภท int จากโลคัล ตัวแปร 0 (พุชค่า n ลงบนสแต็ก) พุชค่า n ลงบนสแต็ก) 16:iconst_1 //พุชค่าคงที่ประเภท int 1 ลงบนสแต็ก ค่าคงที่ 1 คือ 1 ของ n-1 ในโค้ด 17: isub //ดำเนินการลบ n-1 18: involvestatic #2; คูณ:(I)I วิธีการเรียก คูณ 21: imul //ดำเนินการคูณ n * คูณ(n - 1) 22: istore_1 //เก็บค่าประเภท int ในตัวแปรโลคัล 1, factorial=... 23: iload_1 / /โหลดค่าประเภท int จากตัวแปรโลคัล 1 (พุชผลลัพธ์ของแฟกทอเรียลลงบนสแต็ก) 24: ireturn //วิธีการคืนค่าโมฆะคงที่สาธารณะ main(java.lang.String[]); รหัส: 0: getstatic #3; //ฟิลด์ java/lang/System.out:Ljava/io/PrintStream; 3: Iconst_5 4: เรียกใช้แบบคงที่ #2; // วิธีการคูณ: (I) I 7: เรียกใช้เสมือน #4; /PrintStream.println:(I)V 10: กลับ }