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項(xiàng),，斐波那契數(shù)列第一和第二項(xiàng)是1,，后面每一項(xiàng)是前兩項(xiàng)之和，即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：用間接遞歸來計(jì)算上述斐波那契數(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ù)的缺點(diǎn)是什么,？

答：遞歸的目的是簡化程序設(shè)計(jì),，使程序易讀。

示例3：下面不用遞歸函數(shù)繼續(xù)來計(jì)算上述斐波那契數(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ù)的缺點(diǎn)是增加了系統(tǒng)開銷,，也就是說，每遞歸一次,，棧內(nèi)存就多占用一截,。

4、遞歸的條件：

答：需有完成任務(wù)的語句,，需滿足遞歸的要求（減小而不是發(fā)散）。

5,、遞歸進(jìn)階：

示例4：

編程求解：若一頭小母牛,，從出生起第四個(gè)年頭開始每年生一頭母牛，按次規(guī)律,，第n年時(shí)有多少頭母牛,？

程序代碼：

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ù)為：

如果要求的是從出生起第四個(gè)年頭,，則遞歸函數(shù)為cattle(n-1)+ cattle(n-3)，

如果要求的是從出生起第五個(gè)年頭,，則遞歸函數(shù)為cattle(n-1)+ cattle(n-4),，

。,。,。。