模板
教程
環境
性能
功能
管理
什么是遞歸算法:對遞歸的理解(3)
private final static String to = "盤子C";
private final static String mid = "盤子A";
public static void main(String[] args) {
String input = JOptionPane.showInputDialog("請輸入你要移動的盤子數");
int num = Integer.parseInt(input);
Hanoi.move(num, from, mid, to);
}
private static void move(int num, String from2, String mid2, String to2) {
if (num == 1) {
System.out.println("移動盤子1 從" + from2 + "到" + to2);
} else {
move(num - 1, from2, to2, mid2);
System.out.println("移動盤子" + num + " 從" + from2 + "到" + to2);
move(num - 1, mid2, from2, to2);
}
}
}
因為漢諾塔的移動過程比較復雜，用圖片來表示是不現實的，我找到了一個用視頻做的顯示漢諾塔移動過程的實例，大家可以下載用瀏覽器打開：http://v.youku.com/v_show/id_XMzgzOTEzNjMy.html
還有很多的遞歸的例子，我會繼續更新。
三、遞歸算法轉換成非遞歸算法
遞歸算法實際上是一種分而治之的方法，它把復雜問題分解為簡單問題來求解。對于某些復雜問題(例如hanio塔問題)，遞歸算法是一種自然且合乎邏輯的解決問題的方式，但是遞歸算法的執行效率通常比較差。因此，在求解某些問題時，常采用遞歸算法來分析問題，用非遞歸算法來求解問題;另外，有些程序設計語言不支持遞歸，這就需要把遞歸算法轉換為非遞歸算法。將遞歸算法轉換為非遞歸算法有兩種方法，一種是直接求值，不需要回溯;另一種是不能直接求值，需要回溯。前者使用一些變量保存中間結果，稱為直接轉換法;后者使用棧保存中間結果，稱為間接轉換法，下面分別討論這兩種方法。
1. 直接轉換法
直接轉換法通常用來消除尾遞歸和單向遞歸，將遞歸結構用循環結構來替代。尾遞歸是指在遞歸算法中，遞歸調用語句只有一個，而且是處在算法的最后。例如求階乘的遞歸算法：
public long fact(int n)
{
if (n==0) return 1;
else return n*fact(n-1);
}
當遞歸調用返回時，是返回到上一層遞歸調用的下一條語句，而這個返回位置正好是算法的結束處，所以
，不必利用棧來保存返回信息。對于尾遞歸形式的遞歸算法，可以利用循環結構來替代。例如求階乘的遞歸算法
可以寫成如下循環結構的非遞歸算法：
public long fact(int n)
{
int s=0;
for (int i=1; i
s=s*i; //用s保存中間結果
return s;
}
單向遞歸是指遞歸算法中雖然有多處遞歸調用語句，但各遞歸調用語句的參數之間沒有關系，并且這些遞歸
調用語句都處在遞歸算法的最后。顯然，尾遞歸是單向遞歸的特例。例如求斐波那契數列的遞歸算法如下：
public int f(int n)
{
if (n= =1 | | n= =0) return 1;
else return f(n-1)+f(n-2);
}
對于單向遞歸，可以設置一些變量保存中間結構，將遞歸結構用循環結構來替代。例如求斐波那契數列的算
法中用s1和s2保存中間的計算結果，非遞歸函數如下：
public int f(int n)
{
int i, s;
int s1=1, s2=1;
for (i=3; i {
s=s1+s2;
s2=s1; // 保存f(n-2)的值
s1=s; //保存f(n-1)的值
}
return s;
}
2. 間接轉換法
該方法使用棧保存中間結果，一般需根據遞歸函數在執行過程中棧的變化得到。其一般過程如下：
將初始狀態s0進棧
while (棧不為空)
{
退棧，將棧頂元素賦給s;
if (s是要找的結果) 返回;
else {
尋找到s的相關狀態s1;
將s1進棧
}
}
間接轉換法在數據結構中有較多實例，如二叉樹遍歷算法的非遞歸實現、圖的深度優先遍歷算法的非遞歸實現等等，請讀者參考主教材中相關內容。
