1 問題描述
最近兩天在思考如何使用蠻力法解決旅行商問題（此問題，說白了就是如何求解n個不同字母的所有不同排序的序列問題，即共有n!次不同排序）。
為此，我認(rèn)真看了一篇出自CSDN上的博客文章，其中有一段核心代碼就是在for循環(huán)里面添加一句遞歸調(diào)用語句，來實現(xiàn)n!次排序。因此，我對文章中的那段核心代碼苦苦不得其解——其執(zhí)行順序究竟是咋樣的呢？
附其簡要代碼：
public int count = 0;
public void Arrange(int[] A,int start,int step,int n,int Max){ if(step == 2)
System.out.println("第"+(++count)+"次走完一圈");
if(count == Max)
System.out.println("已完成?。?！"); else{ for(int i = start;i < n;i++){
swapArray(A,start,i); Arrange(A,start+1,step+1,n,Max);
swapArray(A,i,start);
}
}
}
2 解決方案
2.1 問題化簡
剛開始學(xué)習(xí)遞歸時，課本上都會給出使用遞歸實現(xiàn)斐波那契數(shù)問題（PS：f(1) = 1,f(2) = 1,f(3) = 2,f(4) = 3,...,f(n) = f(n-1) + f(n-2),求解f(n)），那我們就先來探討使用遞歸法求解第n個斐波那契數(shù)的具體執(zhí)行順序：
先上代碼：
package com.liuzhen.chapterThree;public class Test { public int Fibonacci(int n){
System.out.println("第"+n+"次遞歸,結(jié)果："); if(n == 1 || n == 2) return 1;
System.out.println("********"); return Fibonacci(n-1) + Fibonacci(n-2);
}
public static void main(String[] args){
Test temp = new Test();
System.out.println("運行結(jié)果："+temp.Fibonacci(4));
}
}
運行結(jié)果：
第4次遞歸,結(jié)果：********第3次遞歸,結(jié)果：********第2次遞歸,結(jié)果： 第1次遞歸,結(jié)果： 第2次遞歸,結(jié)果： 第4次遞歸,結(jié)果：********第3次遞歸,結(jié)果：********第2次遞歸,結(jié)果： 第1次遞歸,結(jié)果： 第2次遞歸,結(jié)果： 運行結(jié)果：3
此處是求解第4個斐波那契數(shù),看到運行結(jié)果依次輸出數(shù)字4，3，2，1，2，4，3，2，1，2?？梢钥吹?，輸出的數(shù)字按照第一遍輸出的樣式重復(fù)輸出了一次。
此處遞歸語句：return Fibonacci(n-1) + Fibonacci(n-2);
為此先按照語句分析如下：（PS：經(jīng)網(wǎng)上相關(guān)資料提示：遞歸算法的本質(zhì)是先遞歸后回溯，從而求得最終結(jié)果。以下只是本人根據(jù)程序運行結(jié)果做出的推測分析，如有錯誤，歡迎各位圓友指正~）
（1）Fibonacci(4) = Fibonacci(3) + Fibonacci(2),此時會首先輸出數(shù)字4；
（2）接著執(zhí)行Fibonacci(3) = Fibonacci(2) + Fibonacci(1)，此時會首先輸出數(shù)字3；
（3）接著執(zhí)行（2）中Fibonacci（2），遞歸結(jié)束，此時會首先輸出數(shù)字2；
（4）接著執(zhí)行（2）中Fibonacci（1），遞歸結(jié)束，此時會首先輸出數(shù)字1；
（5）接著執(zhí)行（1）中Fibonacci（2），遞歸結(jié)束，此時會首先輸出數(shù)字2；
（6）上面（1）~（5）步中僅僅只完成了遞歸算法，并未完成求取Fibonacci（4）的具體值步驟，此時，正式開始回溯求取Fibonacci（4），即Fibonacci(4) = Fibonacci(3) + Fibonacci(2)，此時輸出數(shù)字4；
（7）回溯求取（6）中Fibonacci(3)= Fibonacci(2) + Fibonacci(1)，此時輸出數(shù)字3；
（8）回溯求?。?/span>7）中Fibonacci(2)值，其在（3）中已獲得為1，此時輸出數(shù)字2；
（9）回溯求取（7）中Fibonacci(1)值，其在（4）中已獲得為1，此時輸出數(shù)字1，此時求得（6）中Fibonacci(3) = 2；
（10）回溯求?。?/span>6）中Fibonacci(2)值，其在（5）中已獲得為1，此時輸出數(shù)字2，此時求得6）中Fibonacci(2) = 1；
（11）輸出最終結(jié)果Fibonacci(4) = 2+1 =3。
上述執(zhí)行步驟求取Fibonacci(4)簡單示意圖：
2.2 定位輸出測試
由2.1中對于斐波那契數(shù)問題的執(zhí)行順序探討讓我明白了一條遞歸的實質(zhì)——先遞歸后回溯。在本文的問題中，還要謹(jǐn)記一點——遞歸的執(zhí)行順序遵循棧的特性——先進后出。
先看本文所述問題具體測試代碼：
package com.liuzhen.chapterThree;public class TravelingSalesman {
public int count = 0; /*
* start為開始進行排序的位置
* step為當(dāng)前正在排序的位置
* n為需要排序的總位置數(shù)
* Max為n!值 */
public void Arrange(int[] A,int start,int step,int n,int Max){ if(step == 2)
System.out.println("第"+(++count)+"次走完一圈"); if(count == Max)
System.out.println("已完成?。?！"); else{
System.out.println("準(zhǔn)備進入for循環(huán)"); for(int i = start;i < n;i++){
swapArray(A,start,i);
System.out.println("遞歸調(diào)用前："+" start值為"+start+"，i的值為"+i); Arrange(A,start+1,step+1,n,Max);
System.out.println("遞歸調(diào)用后："+" start值為"+start+"，i的值為"+i);
swapArray(A,i,start);
}
}
}
public void swapArray(int[] A,int p,int q){ int temp = A[p];
A[p] = A[q];
A[q] = temp;
}
public static void main(String[] args){ int[] A = {0,1};
TravelingSalesman test = new TravelingSalesman();
test.Arrange(A,0,0,2,2);
}
}
運行結(jié)果：
準(zhǔn)備進入for循環(huán) 遞歸調(diào)用前： start值為0，i的值為0 準(zhǔn)備進入for循環(huán) 遞歸調(diào)用前： start值為1，i的值為1 第1次走完一圈 準(zhǔn)備進入for循環(huán) 遞歸調(diào)用后： start值為1，i的值為1 遞歸調(diào)用后： start值為0，i的值為0 遞歸調(diào)用前： start值為0，i的值為1 準(zhǔn)備進入for循環(huán) 遞歸調(diào)用前： start值為1，i的值為1 第2次走完一圈 已完成?。?！ 遞歸調(diào)用后： start值為1，i的值為1 遞歸調(diào)用后： start值為0，i的值為1
此處是求取數(shù)字0和1的不同排序，即有2！= 2種不同排序，此處依照代碼及運行結(jié)果來分析其具體執(zhí)行順序：
（1）
準(zhǔn)備進入for循環(huán)：
遞歸調(diào)用前： start值為0，i的值為0（程序初始化值start為0，i等于start值為0）
（2）
準(zhǔn)備進入for循環(huán)：
遞歸調(diào)用前： start值為1，i的值為1（執(zhí)行完一次遞歸后，start值變?yōu)?/span>1，i等于start值也為1）
（3）
第1次走完一圈（輸出此句，表示已經(jīng)執(zhí)行完兩次遞歸，start值變?yōu)榱?/span>2）
準(zhǔn)備進入for循環(huán)：（此時，start值為2，即準(zhǔn)備開始回溯，執(zhí)行未完成的for循環(huán)）
遞歸調(diào)用后： start值為1，i的值為1（此處，對照棧的特性，開始進行（2）中未完成的for循環(huán)，輸出此句后，將結(jié)束（2）中的for循環(huán)）
遞歸調(diào)用后： start值為0，i的值為0（此處，對照棧的特性，開始進行（1）中未完成的for循環(huán)，i值將要加1）
遞歸調(diào)用前： start值為0，i的值為1（此處，進行了（1）中一次for循環(huán)后，就要開始執(zhí)行一次遞歸語句，start值將要加1）
（4）
準(zhǔn)備進入for循環(huán)：
遞歸調(diào)用前： start值為1，i的值為1（此處，是執(zhí)行（3）中遞歸語句的執(zhí)行輸出結(jié)果，此時也要開始執(zhí)行一次遞歸語句，start值將要加1）
（5）
第2次走完一圈（此時，start值有變成了2）
已完成?。?！
遞歸調(diào)用后： start值為1，i的值為1（此處，執(zhí)行步驟（4）中未完成for循環(huán)的回溯，進行for循環(huán)）
遞歸調(diào)用后： start值為0，i的值為1（此處，執(zhí)行步驟（3）中未完成for循環(huán)的回溯，進行for循環(huán)）
上述是對2！次不同排序的遞歸執(zhí)行順序分析，下面我們可以來看看對于3！次不同排序的遞歸執(zhí)行順序結(jié)果，看看其執(zhí)行順序是否滿足?！冗M后出的特性，
PS：此處對上述代碼中定義數(shù)字進行稍微修改，修改如下：
if(step == 3)
System.out.println("第"+(++count)+"次走完一圈");public static void main(String[] args){ int[] A = {0,1,2};
TravelingSalesman test = new TravelingSalesman();
test.Arrange(A,0,0,3,6);
}
具體運行結(jié)果：
準(zhǔn)備進入for循環(huán) 遞歸調(diào)用前： start值為0，i的值為0 準(zhǔn)備進入for循環(huán)遞歸調(diào)用前： start值為1，i的值為1準(zhǔn)備進入for循環(huán)遞歸調(diào)用前： start值為2，i的值為2第1次走完一圈 準(zhǔn)備進入for循環(huán)遞歸調(diào)用后： start值為2，i的值為2遞歸調(diào)用后： start值為1，i的值為1遞歸調(diào)用前： start值為1，i的值為2（此處即將執(zhí)行一次遞歸）準(zhǔn)備進入for循環(huán) 遞歸調(diào)用前： start值為2，i的值為2 第2次走完一圈 準(zhǔn)備進入for循環(huán) 遞歸調(diào)用后： start值為2，i的值為2 遞歸調(diào)用后： start值為1，i的值為2 遞歸調(diào)用后： start值為0，i的值為0 遞歸調(diào)用前： start值為0，i的值為1 準(zhǔn)備進入for循環(huán) 遞歸調(diào)用前： start值為1，i的值為1 準(zhǔn)備進入for循環(huán) 遞歸調(diào)用前： start值為2，i的值為2 第3次走完一圈 準(zhǔn)備進入for循環(huán) 遞歸調(diào)用后： start值為2，i的值為2 遞歸調(diào)用后： start值為1，i的值為1 遞歸調(diào)用前： start值為1，i的值為2 準(zhǔn)備進入for循環(huán) 遞歸調(diào)用前： start值為2，i的值為2 第4次走完一圈 準(zhǔn)備進入for循環(huán) 遞歸調(diào)用后： start值為2，i的值為2 遞歸調(diào)用后： start值為1，i的值為2 遞歸調(diào)用后： start值為0，i的值為1 遞歸調(diào)用前： start值為0，i的值為2 準(zhǔn)備進入for循環(huán) 遞歸調(diào)用前： start值為1，i的值為1 準(zhǔn)備進入for循環(huán) 遞歸調(diào)用前： start值為2，i的值為2 第5次走完一圈 準(zhǔn)備進入for循環(huán) 遞歸調(diào)用后： start值為2，i的值為2 遞歸調(diào)用后： start值為1，i的值為1 遞歸調(diào)用前： start值為1，i的值為2 準(zhǔn)備進入for循環(huán) 遞歸調(diào)用前： start值為2，i的值為2 第6次走完一圈 已完成?。?！ 遞歸調(diào)用后： start值為2，i的值為2 遞歸調(diào)用后： start值為1，i的值為2 遞歸調(diào)用后： start值為0，i的值為2
可以看出，運行結(jié)果明顯滿足上述中2！次運行結(jié)果的分析及推測結(jié)論。
2.3 回顧總結(jié)
通過以上的分析及上機輸出測試，可以初步得出遞歸算法執(zhí)行順序滿足如下兩點：
（1）先執(zhí)行遞歸，后進行回溯；
（2）執(zhí)行順序滿足棧的特性——先進后出。
http://www.cnblogs.com/liuzhen1995/p/6368429.html
