基本算法之遞推算法

一.遞推算法基本思想

遞推算法是一種理性思維模式的代表，其根據已有的資料和關系，逐漸推導而得到結果。其大緻步驟如下:

1.根據已知結果和關系，求解中間結果。

2.判定是否達到要求，如果沒有達到，則繼續根據已知結果和關系求解中間結果；如果滿足要求，則表示找到一個正确的答案。

**小技巧：**遞推算法往往需要使用者知道答案和問題之間的關系。在許多數學問題中，都有着明确的計算公式可以遵循，是以往往可以采用遞推算法來實作。

二.遞推算法典型執行個體

數學裡面的斐波那契數列便是一個使用遞推算法的經典例子。13世紀意大利數學家斐波那契的《算盤書》中記載了典型的兔子産仔的問題：如果一對兩個月大的兔子以後每一個月都可以生一對小兔子，而一對新生的兔子出生兩個月後才可以生小兔子。 也就是說，1月份出生，3月份才可以産仔。那麼假設一年内沒有發生兔子死亡的事件，那麼一年後共有多少對兔子？

1.分析：

逐月分析每月的兔子對數

第一個月：一對兔子；

第二個月：一對兔子；

第三個月：兩對兔子；

第四個月：三對兔子；

第五個月：五對兔子；

…

從上述内容可以看出，從第三個月開始，每個月的兔子對數等于前兩個月兔子數的總和，對應的計算公式如下：

第N個月兔子總數Fn=F(n-2)+F(n-1)。

這裡，初始第一個月的兔子數為F1=1，第二個月的兔子數為F2=1。

2.參考代碼：

mport java.util.Scanner;

public class Fibonacci {
	public static int fibonacci(int m) {
		int t1,t2;
		if(m == 1 || m == 2) {
			return 1;
		}else {
			t1=fibonacci(m-1);     //遞歸調用
			t2=fibonacci(m-2);
			return t1+t2;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("遞推算法求兔子産子問題");
		System.out.println("輸入時間：");
		Scanner input = new Scanner(System.in);
		int m = input.nextInt();
		int num = fibonacci(m);
		System.out.println("經過"+m+"個月的時間，共繁殖了"+num+"對兔子！");
	}

}
           

3.結果展示：