遞歸算法
了解遞歸算法
在程式設計中，要保證易讀性和正确性的最有效手段就是函數。執行一個邏輯操作（可以是非常長和複雜的操作）的一組指令可以用函數組織起來。
函數的名稱和它的變量可以看成是一個新的可用在其他程式中的指令。已知一個函數的輸入和輸出，我們甚至都不用知道它到底是如何完成任務的，隻需知道可以用這樣一個函數，這樣的函數定義意味着它被調用，執行然後将控制權還給調用它的那個程式的适當位置。
在這裡，函數有可能在結束執行之前調用它們自身（直接遞歸），或者調用其他反過來有可能調用它自身的函數（間接遞歸）。
遞歸算法實作漢諾塔問題
漢諾塔問題描述
漢諾塔問題發源于古老的梵天寺之塔儀式。傳說但世界誕生的時候，有一座摞了64個黃金的碟子的鑽石塔（記為A）。碟子按從小到大的次序自底向上地摞在塔上。除此之外，還有兩個鑽石塔（記為B和C）。從世界誕生之時起，梵天寺的僧侶就在通過塔B将碟子從塔A挪到塔C。因為碟子都非常重，一次隻能挪一塊。另外，然後時候都不能大碟子在上小碟子在下。根據傳說，當僧侶完成任務的時候就是世界的末日。
這個問題可以通過遞歸來解決，假設碟子數是n，為了将最大的碟子挪到C上，我們需要将剩下的n-1個碟子先挪到塔B，然後再将最大的碟子挪到塔C，最後将剩下的n-1個碟子挪到塔C最大碟子的上面，這樣就可以實作所有碟子由A到C了。下面我們需要解決的是如何将塔B上的n-1個碟子挪到塔C上。此時，塔C上的碟子是最大碟子，是以不影響任何碟子置于其上。于是，我們将問題轉換成了如何将塔B上的n-1個碟子通過塔A，全部挪到塔C上，通過相同的方法，變為塔A上的n-2個碟子如何通過塔B挪到塔C。依次遞進，直到一個碟子如何到另一個塔。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int n; //輸入n值
String A="A";
String B="B";
String C="C";
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
HanNt(n,'A','B','C'); //調用遞歸函數
}
public static void HanNt(int n,char A,char B,char C) {
if(n==1){
move(A,C); //執行A到C，傳進來的AC不确定,A可能是B,也可能是C,C也如此。在此參照形參與實參。
}else {
HanNt(n-1,A,C,B); //改變ABC位置，使得即便移動的是"A"和"C"，變為了移動A和B
move(A,C);
HanNt(n-1,B,A,C); //改變ABC位置，使得即便移動的是"A"和"C"，變為了移動B和C
}
}
public static void move(char A,char C) {
System.out.println(A+"-->"+C);
}
}
漢諾塔實作總結
通過此算法，我們實作了漢諾塔的移動，在編寫代碼過程中,我也對64個碟子以及世界末日産生了興趣，通過輸入3，4，5等等驗證了代碼的正确性之後，我輸入了64（其實在輸入6時，我已經察覺到了）；然後程式開始無限輸入下去，很久都沒有停止（盡管我知道等棧溢出之後它會停止）。于是我不得不強制關閉程式；然後百度，移64層的漢諾塔需2^64 -1=18,446,744,073,709,551,615步。如果是一秒一次的話，那麼就是18,446,744,073,709,551,615秒。也就是584,942,417,355年26天7小時15秒（以上是百度内容）。看來這個數字是真的龐大。是以回歸代碼，實作這個n=64時，代碼的時間複雜度（大于等于2^64）也是非常大的。回頭反思一下，遞歸算法是不斷調用自身函數的過程，而每一次函數調用，都需要在記憶體棧中配置設定空間以儲存參數、傳回位址以及臨時變量，而往棧中壓入資料和彈出資料都需要時間。遞歸中很多計算都是重複的，由于其本質是把一個問題分解成兩個或者多個小問題，多個小問題存在互相重疊的部分，則存在重複計算，而每一次函數調用會在記憶體棧中配置設定空間，而每個程序的棧的容量是有限的，當調用的層次太多時，就會超出棧的容量，進而導緻棧溢出。是以遞歸算法的缺陷也是顯而易見的。
遞歸算法實作真值表
問題描述
給定n個布爾變量X1，X2，------，Xn，我們想列印出它們所有可能的指派組合。例如，如果n=2，那麼一共有四種可能：真，真； 真，假： 假，真： 假，假。
對于此問題，我們對結果（為了友善表述，我們假設結果有2n個）分析，總是可以将其分為兩類，一類是真（T（1））開頭，一類是假（F（0））開頭，由此，問題分成了兩部分，在真開頭後，如何将真後的n-1個組合列出來。和在假開頭後，如何将假開頭後的n-1個組合列出來。此時，開頭的真假已确定，問題進而轉換為将兩個n-1個組合結果列出來，我們可以再次将其分為兩部分，直到最後輸出真假。
import java.util.Scanner;
public class Main{
public static void main(String[] args){
int n;
Scaner sc=new Scanner(System.in);
n=sc.nextInt(); //輸入n值
String a[]=new String[n]; //定義輸出數組，長度為n
int l=0; //定義l,用來檢測函數遞歸到了哪步
Tf(l,n,a);
}
public static void Tf(int x,int y,String a[]){
int i;
if(x==y){ //通過比較x(l),y(n)來确定是否到達輸出條件
for(i=0;i<y;i++){
System.out.println(a[i]); //輸出順序不變，算法中的各種指派步驟，導緻輸出結果的改變
}
System.out.println("\n");
return;
}
a[x]="T"; //将目前a[x]指派為T
Tf(x+1,y,a); //x+1進入遞歸函數
a[x]="F"; //将目前a[x]指派為F
Tf(x+1,y,a); //x+1進入遞歸函數
}
}
真值表實作總結
通過上述算法，我們得到了布爾變量為n的真值表。總結，我們剛開始問題分析的時候，說将問題分為開頭為TF兩部分，然後再分。直到最後。但通過我們對算法逐漸追蹤，以及結果分析。其結果（n=3舉例）為 TTT,TTF,TFT,TFF,FTT,FTF,FFT,FFF。我們發現該算法的實作并不是簡單的同步實作。也就是說實作FFF的代碼執行是在FFT完成的基礎上。代碼運作過程中，反複的進出函數的過程遠比我們想象的複雜。例如：TFT（第三個結果，分析簡單一點，大家體驗一下）就是實作TTF之後，代碼繼續執行将a[2]指派為F,進而實作TTF，之後傳回到x=1；将a[1]指派為F，然後再進入下面的遞歸函數，将a[2]指派為T，然後進入輸出循環，輸出TFT。而我們在想怎麼解決該問題時，似乎并沒發現函數運作的複雜程度。而是按照自己的想法将函數嵌套即可。這也正反應了遞歸算法的一大優點。在解決問題時，避免了其複雜的過程，使問題變得簡單，容易實作。
遞歸算法的總結
通過以上兩個問題，我想大家對遞歸算法應該有了一定的認識。總的來說，遞歸算法雖然使得解題過程變得簡單，理論上，遞歸算法可以替代循環。但其執行過程卻是異常複雜的，占用了大量的記憶體空間。在這裡說一下，遞歸算法能解決的問題，總能找的其他算法解決。是以，我還是建議大家多思考，想出别的算法更好。畢竟遞歸算法對計算機不太友好，作為程式員，當然應該考慮一下自己的“女朋友”。。。。。。嘻嘻嘻。