1、遞歸函數(shù)的定義：
答：遞歸函數(shù)即自調(diào)用函數(shù)，在函數(shù)體內(nèi)直接或間接的調(diào)用自己，即函數(shù)的嵌套是函數(shù)本身。
2、遞歸方式：遞歸調(diào)用有直接遞歸和間接遞歸兩種方式。
A：直接遞歸：在函數(shù)中出現(xiàn)調(diào)用函數(shù)本身。
示例1：下面代碼求斐波那契數(shù)列第n項，斐波那契數(shù)列第一和第二項是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：間接遞歸：指函數(shù)中調(diào)用了其他函數(shù)，而該其他函數(shù)有調(diào)用了本函數(shù)。
示例2：用間接遞歸來計算上述斐波那契數(shù)列。
程序代碼：
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、為什么要用遞歸函數(shù)？遞歸函數(shù)的缺點是什么？
答：遞歸的目的是簡化程序設(shè)計，使程序易讀。
示例3：下面不用遞歸函數(shù)繼續(xù)來計算上述斐波那契數(shù)列。
程序代碼：
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);
}
}
從上面例子我們可以發(fā)現(xiàn)雖然非遞歸函數(shù)效率高，但較難編程，可讀性較差。遞歸函數(shù)的缺點是增加了系統(tǒng)開銷，也就是說，每遞歸一次，棧內(nèi)存就多占用一截。
4、遞歸的條件：
答：需有完成任務(wù)的語句，需滿足遞歸的要求（減小而不是發(fā)散）。
5、遞歸進階：
示例4：
編程求解：若一頭小母牛，從出生起第四個年頭開始每年生一頭母牛，按次規(guī)律，第n年時有多少頭母牛？
程序代碼：
public class Test3 {
public static void main(String args[]) {
int n=10; //要查看的年數(shù)
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);//此處是遞歸要好好理解。
}
}
規(guī)律：此類問題的遞歸函數(shù)為：
如果要求的是從出生起第四個年頭，則遞歸函數(shù)為cattle(n-1)+ cattle(n-3)，
如果要求的是從出生起第五個年頭，則遞歸函數(shù)為cattle(n-1)+ cattle(n-4)，
。。。。
