初次接觸java中的遞歸算法

一道關於兔子繁衍的編程題:

有一對兔子，從出生後第3個月起每個月都生一對兔子，小兔子長到第三個月後每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數為多少？

自己考慮了挺久,思路出現了問題,甚至連其中的規律都沒有搞清楚.查看網上的一些算法之後,發現一個之前沒有使用的思想:遞歸.目前對於遞歸的理解僅限於初級中的初級.

關於這道編程題,應該以這樣的思路來進行考慮:

每個月的兔子的來源是哪些?答:上個月的兔子的個數(不管是否具備繁殖能力) + 2個月前的兔子的個數  在第1和2個月的時候,只有最開始的一對兔子.

這樣想一想的話,就是用上個月的兔子個數 + 上上個月的兔子個數 ,就可以得到本月的兔子的個數.結果恰好是很著名的斐波那契數列.

1     public static int method(int month){
2         if(month == 1 || month == 2){
3             return 1;
4         }else{
5             int num =  method(month -1) + method(month -2);
6             return num;
7         }
8     }

思想就是結果= 上次程序的結果 + 上上次的程序的結果

後在網上查看有關遞歸的資料,看到另外兩個用遞歸思想解決的問題:爬樓梯問題和漢諾塔問題

爬樓梯問題

假設一個樓梯有 N 階台階，人每次最多可以跨 M 階，求總共的爬樓梯方案數。

分析:

台階數(走法) 方法數
1 1 1
2 11 2 2
3 111 12 21 3
4 1111 112 121 211 225

因此可知,這個問題和之前的兔子繁衍問題是一個道理.

 1 public static int f(int n) {
 2         if (n == 0) {
 3             return 0;
 4         } else if (n == 1) {
 5             return 1;
 6         } else if (n == 2) {
 7             return 2;
 8         } else {
 9 
10             return f(n - 1) + f(n - 2);
11         }
12     }

漢諾塔問題:

從左到右 A B C 柱 大盤子在下, 小盤子在上, 借助B柱將所有盤子從A柱移動到C柱,大盤子只能在小盤子下面.

這些問題我想起來比較吃力,但網上解析很多,幾乎涵蓋了我的所有的考慮了,因此,我在這裡只說以下較為簡單快捷的一種理解方式.

A,B,C三個針,假設有n個盤子,只需要分成三步,①將(n-1)個盤子從A移動到B,②將最大的盤子從A放到C,③將(n-1)個盤子從B移動到C

f(n) = (f(n-1)*2) + 1;

public static int method(int n){
        if(n == 1){
            return 0;
        }else if(n == 2){
            return 1;
        }else{
            return method(n-1)*2 + 1;
        }
    }

再舉個例子,使用遞歸的思想來打印9*9乘法表

正常若不使用迭代的話,可以這樣來實現代碼,使用兩層嵌套的for循環

1 public static void method_1(){
2         for(int i = 1;i <= 9;i++){
3             for(int j = 1;j <= i;j++){
4                 System.out.print(i + "*" + j + "=" + i*j + " ");
5             }
6             System.out.println();
7         }
8     }

若使用遞歸的話,問題就變成了:打印上一次的結果並打印新的一行

 1 public static void method_2(int i){
 2          if (i == 1) { 
 3              System.out.println("1*1=1 "); 
 4          } else { 
 5              method_2(i - 1); 
 6              for (int j = 1; j <= i; j++) { 
 7                  System.out.print(j + "*" + i + "=" + j * i + " "); 
 8              } 
 9              System.out.println(); 
10          } 
11     }  

關於遞歸的應用,大體上來說,就是需要發現並找到程序中的遞歸的情況,將問題簡化.