遞歸函數之JAVA演繹

2019-11-18 13:53:07

字體：大中小

來源：轉載

供稿：網友

　　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[]) {

上一篇：端口掃描程序java實現

下一篇：第1個簡單java程序