Java递归函数
原文：http://blog.163.com/zhuliqing_001/blog/static/293340982010101046597/
1 、遞歸函數的定義：
答：遞歸函數即自調用函數，在函數體內直接或間接的調用自己，即函數的嵌套是函數本身。
2 、遞歸方式：遞歸調用有直接遞歸和間接遞歸兩種方式。
A ：直接遞歸：在函數中出現調用函數本身。
示例 1 ：下面代碼求斐波那契數列第 n 項，斐波那契數列第一和第二項是 1 ，后面每一項是前兩項之和，即 1 、 1 、 2 、 3 、 5 、 8 、 13 ．．．。
程序代碼：
public class Test {
? public static void main(String args[]) {
??? int x1 = 1;
??? int sum = 0;
??? int n = 7;
?
??? for (int i = 1; i <= n; i++) {
????? x1 = func(i);
????? sum = sum + x1;
??? }
??? System.out.println("sum=" + sum);
? }
?
? public static int func(int x) {
??? if (x > 2)
????? return (func(x - 1) + func(x - 2));
??? else
????? return 1;
? }
}
?
B ：間接遞歸：指函數中調用了其他函數，而該其他函數有調用了本函數。
示例 2 ：用間接遞歸來計算上述斐波那契數列。
程序代碼：
public class Test {
? public static void main(String args[]) {
??? int x1 = 1;
??? int sum = 0;
??? int n = 7;
?
??? for (int i = 1; i <= n; i++) {
????? x1 = func1(i);
????? sum = sum + x1;
??? }
??? System.out.println("sum=" + sum);
? }
? public static int func1(int a){
????? int b;
????? b=func2(a);
????????? return b;
? }
?
? public static int func2(int b) {
??? if (b> 2)
????? return (func1(b - 1) + func1(b - 2));
??? else
????? return 1;
? }
}
3 、為什么要用遞歸函數？遞歸函數的缺點是什么？
答：遞歸的目的是簡化程序設計，使程序易讀。
示例 3 ：下面不用遞歸函數繼續來計算上述斐波那契數列。
程序代碼：
public class Test {
? public static void main(String args[]) {
??? int n=7;
??? int a=1, b=1, temp;
??? int sum=2;
?
??? for(int i=3; i<=n; i++){
????? temp=a+b; a=b; b=temp;
?? ??????? sum=sum+temp;
??? }
??? System.out.println("sum=" + sum);???
? }
}
從上面例子我們可以發現雖然非遞歸函數效率高，但較難編程，可讀性較差。遞歸函數的缺點是增加了系統開銷，也就是說，每遞歸一次，棧內存就多占用一截。
?
4 、遞歸的條件：
答：需有完成任務的語句，需滿足遞歸的要求（減小而不是發散）。
5 、遞歸進階：
示例 4 ：
編程求解：若一頭小母牛，從出生起第四個年頭開始每年生一頭母牛，按次規律，第 n 年時有多少頭母牛？
?
程序代碼：
public class Test3 {
? public static void main(String args[]) {
??? int n=10;? // 要查看的年數
??? System.out.println(" 共有 "+cattle(n)+" 頭小母牛！ ");
? }
? public static int cattle(int n){
??? if(n<=0)
????? return 0;
??? if(n<=3)
????? return 1;
??? return cattle(n-1)+ cattle(n-3);// 此處是遞歸要好好理解。 ???
? }
}
?
規律：此類問題的遞歸函數為：
如果要求的是從出生起第四個年頭，則遞歸函數為 cattle(n-1)+ cattle(n-3) ，
如果要求的是從出生起第五個年頭，則遞歸函數為 cattle(n-1)+ cattle(n-4) ，
。。。。
依次類推。
（原代碼全部在 JBuilderX 下調試通過）
轉載于:https://www.cnblogs.com/zhaofei/p/3372859.html
總結
- 上一篇： java生成pdf文档
- 下一篇： WinRAR 命令行简体中文说明