《Java軟件結(jié)構(gòu)：設(shè)計(jì)和使用數(shù)據(jù)結(jié)構(gòu)（第2版）》讀書(shū)筆記1－遞歸
大學(xué)的數(shù)據(jù)結(jié)構(gòu)和算法根本就是混過(guò)來(lái)的，某天在某某論壇里有個(gè)關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法到底在日常的編程到底有多大的用處。對(duì)于我來(lái)說(shuō)，我并不覺(jué)得我用上了那些講的數(shù)據(jù)結(jié)構(gòu)和算法。Java Collection Framework已經(jīng)跟我們做了這些。我已經(jīng)能非常熟練的使用Collection里面的類(lèi)庫(kù)。但是我們用的基本上都是那些線性集合（堆棧，隊(duì)列，列表，Set），非線性集合（樹(shù)，堆，散列和圖）我感覺(jué)比較少用到。我也主要是想對(duì)非線性集合做一些比較。線性集合比較簡(jiǎn)單。
第一章到第九章都是講線性集合， 也比較容易理解， 在這里就忽略掉。第十章是講遞歸算法。我對(duì)這章比較感興趣，用遞歸實(shí)現(xiàn)某個(gè)算法真的感覺(jué)非常優(yōu)雅，代碼短而少，許多非線性集合都是用遞歸來(lái)實(shí)現(xiàn)的。但也有他的缺點(diǎn)， 對(duì)方法的每次遞歸調(diào)用都會(huì)生成新的局部變量和局部參數(shù)。假如遞歸層次太多的話，就會(huì)消耗太多的stack。
任何遞歸定義都必須有一個(gè)非遞歸部分；這個(gè)非遞歸部分叫做基本情況，它使的遞歸跳出無(wú)窮循環(huán)遞歸。
Ex 1： 1~N的累加過(guò)程，數(shù)值1～N的累加可以看成是1～N－1的累加加上N。
public int sum(int num)
{
int result = 0;
if (num == 1){
return 1;
}
return result + num + sum(num - 1);
}
這里的基本情況就是但num＝＝1的時(shí)候。 當(dāng)然這個(gè)可以不用遞歸來(lái)處理，用一個(gè)for就行了（而且比用遞歸更直觀）。我們必須能判斷什么時(shí)候使用遞歸，什么時(shí)候不使用遞歸，所有問(wèn)題都可以使用迭代（for循環(huán)）解決問(wèn)題。不過(guò)有些情況下，迭代方式過(guò)于復(fù)雜，對(duì)某些問(wèn)題，遞歸可以寫(xiě)出短小而優(yōu)雅的代碼。
直接遞歸和間接遞歸，方法調(diào)用自己，這就是直接遞歸（如上個(gè)例子）。方法調(diào)用另一個(gè)方法，最終導(dǎo)致再調(diào)用原方法。這就是間接遞歸。
河內(nèi)塔問(wèn)題（Towers of Hanoi）（可以上網(wǎng)找找這個(gè)經(jīng)典問(wèn)題的描述）
規(guī)則：
l 一次只能移動(dòng)一張圓盤(pán)
l 不能將大盤(pán)放在小盤(pán)的上方
l 除了那張?jiān)谥又g搬動(dòng)的圓盤(pán)之外，所有圓盤(pán)都必須在某根柱子上
策略：
l 將最上方的N－1張圓盤(pán)從最初的柱子移到那根多處的柱子上
l 將最大的圓盤(pán)從最初的柱子移動(dòng)到最終的柱子上
l 再將那個(gè)多出柱子上的N－1張圓盤(pán)移到最終的柱子上
Code：
public class TowersOfHanoi{
private int totalDisks;
// ------------------------------------------------------
// Sets up the puzzle with the specified number of disks
// ------------------------------------------------------
public TowersOfHanoi(int disks){
this.totalDisks = disks;
}
// ----------------------------------------------------------
// Performs the initial call to moveTower to solve the puzzle.
// Moves the disks from tower 1 to tower 3 using tower 2
// ----------------------------------------------------------
public void solve(){
moveTower(totalDisks, 1, 3,2);
}
// -----------------------------------------------------------------
// Moves the specified number of disks from one tower to another by
// moving a subtower of n-1 disks out of the way, moving one disk,
// then moving the subtower back, Base case of 1 disk.
// -----------------------------------------------------------------
private void moveTower(int numDisks, int start, int end, int temp) {
if (numDisks == 1){
moveOneDisk(start, end);
}else{
moveTower(numDisks-1, start, temp, end);
moveOneDisk(start, end);
moveTower(numDisks-1, temp, end, start);
}
}
private void moveOneDisk(int start, int end) {
System.out.println("Move one disk from " + start + " to " + end);
}
}