?才畢業(yè)的開發(fā)小白纠俭，最近在使用node沿量、php和vue，有興趣的小伙伴可以加群 134246716冤荆，大家一起學(xué)習(xí)欧瘪，這是一個新建群，有興趣的初學(xué)者可以來一起學(xué)習(xí)哦匙赞。
I. 遞歸簡論
-
遞歸的概念
當(dāng)一個函數(shù)用它自己來定義時(shí)就稱為是遞歸(recursive)的。 -
遞歸的基本法則
當(dāng)編寫遞歸程序時(shí)妖碉，關(guān)鍵是要牢記遞歸的四條基本法則:
1.基準(zhǔn)情形 (base case)涌庭。必須總要有某些基準(zhǔn)情形，它無需遞歸就可以解出欧宜。
2.不斷推進(jìn) (making progress)坐榆。對于那些需要遞歸的求解的情形，每一次遞歸調(diào)用都必須要使情況朝向一種基準(zhǔn)情形推進(jìn)冗茸。
3.設(shè)計(jì)法則 (design rule)席镀。假設(shè)所有的遞歸調(diào)用都能運(yùn)行。
4.合成法則 (compound interest rule)夏漱。在求解一個問題的同一實(shí)例時(shí)豪诲，切勿在不同的遞歸調(diào)用中做重復(fù)性的工作。
?使用遞歸計(jì)算諸如斐波那契數(shù)之類簡單數(shù)學(xué)函數(shù)的值的想法一般來說不是一個好主 意挂绰，其道理正是根據(jù)第四條法則屎篱。
II. 遞歸與數(shù)學(xué)歸納法
-
數(shù)學(xué)歸納法的思想
?一般地，證明一個與自然數(shù) n 有關(guān)的命題 P(n)葵蒂，有如下步驟:
(1) 證明當(dāng) n 取第一個值 n0 時(shí)命題成立;
(2) 假設(shè)當(dāng)n=k(k?n0)時(shí)命題成立交播，證明當(dāng)n=k+1時(shí)命題也成立。
綜合(1)(2)践付，對一切的自然數(shù) n(n ? n0)秦士，命題 P(n) 都成立。
其實(shí)永高，數(shù)學(xué)歸納法利用的是遞推的原理隧土，可以形象地叫做多米諾原理。 數(shù)學(xué)歸納法的關(guān)鍵就是如何證明當(dāng) n = k + 1 時(shí)命題也成立命爬。 -
遞歸的思想
? 很明顯次洼，遞歸也是用了遞推的思想。
(1) 首先遇骑，我們需要一個遞歸的出口卖毁，即 base case;
(2) 其次，是遞歸體的設(shè)計(jì)，即對于一個一般的情況如何向 base case 靠近亥啦，把它化解成為一個更小的炭剪，同樣結(jié)構(gòu)的問題。
遞歸的關(guān)鍵就是將問題轉(zhuǎn)化成一個更小規(guī)模的同樣結(jié)構(gòu)的問題翔脱。
III. 遞歸的經(jīng)典例子
-
n!的遞歸算法
? 求解 n! 是最經(jīng)典入門的遞歸算法奴拦。根據(jù)前面的知識我們知道用遞歸解決這個問題，需要兩個要點(diǎn)届吁。首先错妖，如何將一個大的問題轉(zhuǎn)化成一個小規(guī)模的問題?我們知道，n! = n(n ? 1)!疚沐， 那么根據(jù)這個公式暂氯，我們就可以輕易地將求解 n! 轉(zhuǎn)化為求解 (n ? 1)!(將問題的規(guī)模變小了，并且是同樣的問題)亮蛔。其次痴施，如何找到 base case，即遞歸的出口呢?在該問題里面也是很明顯的究流，最后求 1! 時(shí)辣吃，就不需要在遞歸了。所以芬探，該遞歸算法可以寫為:
int factorial(int n){
if (n == 1)
return 1; // base case
return n * factorial(n ? 1); // making progress
}
-
漢諾塔的遞歸算法
? 如下圖所示神得，從左到右 A、B偷仿、C 三根柱子循头，其中 A 柱子上面有從小疊到大的 n 個圓盤。 現(xiàn)要求將 A 柱子上的圓盤移到 C 柱子上去炎疆，期間只有一個原則:一次只能移到一個盤子且大盤子不能在小盤子上面卡骂，求移動的步驟和移動的次數(shù)。
漢諾塔示意圖.png
1. 算法分析:
? 當(dāng) A 柱子上只有一個盤子時(shí)形入，可以直接把盤子移到 C 柱子上;當(dāng) A 柱子上有兩個盤子時(shí)全跨，需要借助 B 盤子，先將上面的小盤子移到 B 柱子上亿遂，再將大盤子移到 C 柱子上浓若，再將小盤子移到 C 柱子上。那對于更一般的情況蛇数，當(dāng)有 n 個盤子的時(shí)候怎么遞歸呢?當(dāng)有 n 個盤子時(shí)挪钓，我們可以將盤子看成兩個部分。第 n 個盤子和上面 n ? 1 個盤子耳舅，如圖中的顏色區(qū)分碌上。就像是操作兩個盤子(把前 n ? 1 個盤子看成一個整體):先把前 n ? 1 個盤子從 A 盤放到 B 盤倚评，再把第 n 個盤子從 A 盤放到 C 盤，最后再把前 n ? 1 個 盤子從 B 盤放到 C 盤馏予。這樣我們就把問題的規(guī)奶煳啵縮小到 n ? 1 了。
2. 算法的Java實(shí)現(xiàn):
/**
* @Author: 落腳丶
* @Date: 2017/10/14
* @Time: 下午8:33
* @ClassName: HanoiTower
* @Description: 漢諾塔的遞歸算法
*/
import java.util.Scanner;
public class HanoiTower {
private static int step = 0; // 記錄步數(shù)
public static void main(String[] argus){
Scanner scanner = new Scanner(System.in);
System.out.println("請輸入盤子的個數(shù):");
int count = scanner.nextInt();
hanoi(count, 'A', 'B', 'C');
}
/**
* @Date: 2017/10/14
* @Time: 下午9:27
* @Method: hanoi
* @Description:
* 將n個盤子從a塔移動到c塔霞丧，需要借助中間塔b呢岗。
* 最后一個塔只需要直接移動即可
*
*/
private static void hanoi(int n, char a, char b, char c){
/**
* n為需要移動的盤子數(shù)；
* a是最開始放盤子的塔蛹尝；
* b是中間中轉(zhuǎn)的塔后豫；
* c是最終需要放盤子的塔。
*/
if (n == 1) {
// 遞歸的base case 只有一個盤子的時(shí)候突那，直接把盤子從a塔移到c塔
move(1, a, c);
}else {
/**
* 對于遞歸的一般情況挫酿，把前n-1個塔看做是一個整體，整體移動陨收，
* 那么現(xiàn)在就相當(dāng)于兩個塔，
* 注意：hanoi(n, a, b, c)方法的含義就是利用中間塔b鸵赖，
* 把n個盤子從a塔移到c塔务漩！
* 我們只需要下面三步：
* 1. 把前n-1個盤子，從a塔移到b塔它褪，需要借助中間塔c饵骨；
* 2. 把第n個盤子從a塔移到c塔；
* 3. 把前n-1個盤子從b塔移到c塔茫打，需要借助中間塔a居触。
*/
hanoi(n - 1, a, c, b);
move(n, a, c);
hanoi(n - 1, b, a, c);
}
}
private static void move(int number,char origin, char target){
System.out.println("第" + ++step + "次移動：" + number +
"號盤子，" + origin + " ----> " + target);
}
}
/**
* 以3個盤子為例的輸出：
*
* 請輸入盤子的個數(shù):
* 3
* 第1次移動：1號盤子老赤，A ----> C
* 第2次移動：2號盤子轮洋，A ----> B
* 第3次移動：1號盤子，C ----> B
* 第4次移動：3號盤子抬旺，A ----> C
* 第5次移動：1號盤子弊予，B ----> A
* 第6次移動：2號盤子，B ----> C
* 第7次移動：1號盤子开财，A ----> C
*/
