1 問題描述
最近兩天在思考如何使用蠻力法解決旅行商問題（此問題，說白了就是如何求解n個(gè)不同字母的所有不同排序的序列問題，即共有n!次不同排序）。
為此，我認(rèn)真看了一篇出自CSDN上的博客文章，其中有一段核心代碼就是在for循環(huán)里面添加一句遞歸調(diào)用語句，來實(shí)現(xiàn)n!次排序。因此，我對(duì)文章中的那段核心代碼苦苦不得其解——其執(zhí)行順序究竟是咋樣的呢？
附其簡(jiǎn)要代碼：
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 問題化簡(jiǎn)
剛開始學(xué)習(xí)遞歸時(shí)，課本上都會(huì)給出使用遞歸實(shí)現(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個(gè)斐波那契數(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("運(yùn)行結(jié)果："+temp.Fibonacci(4));
}
}
運(yùn)行結(jié)果：
第4次遞歸,結(jié)果：********第3次遞歸,結(jié)果：********第2次遞歸,結(jié)果： 第1次遞歸,結(jié)果： 第2次遞歸,結(jié)果： 第4次遞歸,結(jié)果：********第3次遞歸,結(jié)果：********第2次遞歸,結(jié)果： 第1次遞歸,結(jié)果： 第2次遞歸,結(jié)果： 運(yùn)行結(jié)果：3
此處是求解第4個(gè)斐波那契數(shù),看到運(yùn)行結(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ù)程序運(yùn)行結(jié)果做出的推測(cè)分析，如有錯(cuò)誤，歡迎各位圓友指正~）
（1）Fibonacci(4) = Fibonacci(3) + Fibonacci(2),此時(shí)會(huì)首先輸出數(shù)字4；
（2）接著執(zhí)行Fibonacci(3) = Fibonacci(2) + Fibonacci(1)，此時(shí)會(huì)首先輸出數(shù)字3；
（3）接著執(zhí)行（2）中Fibonacci（2），遞歸結(jié)束，此時(shí)會(huì)首先輸出數(shù)字2；
（4）接著執(zhí)行（2）中Fibonacci（1），遞歸結(jié)束，此時(shí)會(huì)首先輸出數(shù)字1；
（5）接著執(zhí)行（1）中Fibonacci（2），遞歸結(jié)束，此時(shí)會(huì)首先輸出數(shù)字2；
（6）上面（1）~（5）步中僅僅只完成了遞歸算法，并未完成求取Fibonacci（4）的具體值步驟，此時(shí)，正式開始回溯求取Fibonacci（4），即Fibonacci(4) = Fibonacci(3) + Fibonacci(2)，此時(shí)輸出數(shù)字4；
（7）回溯求取（6）中Fibonacci(3)= Fibonacci(2) + Fibonacci(1)，此時(shí)輸出數(shù)字3；
（8）回溯求?。?/span>7）中Fibonacci(2)值，其在（3）中已獲得為1，此時(shí)輸出數(shù)字2；
（9）回溯求?。?/span>7）中Fibonacci(1)值，其在（4）中已獲得為1，此時(shí)輸出數(shù)字1，此時(shí)求得（6）中Fibonacci(3) = 2；
（10）回溯求?。?/span>6）中Fibonacci(2)值，其在（5）中已獲得為1，此時(shí)輸出數(shù)字2，此時(shí)求得6）中Fibonacci(2) = 1；
（11）輸出最終結(jié)果Fibonacci(4) = 2+1 =3。
上述執(zhí)行步驟求取Fibonacci(4)簡(jiǎn)單示意圖：
2.2 定位輸出測(cè)試
由2.1中對(duì)于斐波那契數(shù)問題的執(zhí)行順序探討讓我明白了一條遞歸的實(shí)質(zhì)——先遞歸后回溯。在本文的問題中，還要謹(jǐn)記一點(diǎn)——遞歸的執(zhí)行順序遵循棧的特性——先進(jìn)后出。
先看本文所述問題具體測(cè)試代碼：
package com.liuzhen.chapterThree;public class TravelingSalesman {
public int count = 0; /*
* start為開始進(jìn)行排序的位置
* 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)備進(jì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);
}
}
運(yùn)行結(jié)果：
準(zhǔn)備進(jìn)入for循環(huán) 遞歸調(diào)用前： start值為0，i的值為0 準(zhǔn)備進(jìn)入for循環(huán) 遞歸調(diào)用前： start值為1，i的值為1 第1次走完一圈 準(zhǔn)備進(jìn)入for循環(huán) 遞歸調(diào)用后： start值為1，i的值為1 遞歸調(diào)用后： start值為0，i的值為0 遞歸調(diào)用前： start值為0，i的值為1 準(zhǔn)備進(jì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種不同排序，此處依照代碼及運(yùn)行結(jié)果來分析其具體執(zhí)行順序：
（1）
準(zhǔn)備進(jìn)入for循環(huán)：
遞歸調(diào)用前： start值為0，i的值為0（程序初始化值start為0，i等于start值為0）
（2）
準(zhǔn)備進(jì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)備進(jìn)入for循環(huán)：（此時(shí)，start值為2，即準(zhǔn)備開始回溯，執(zhí)行未完成的for循環(huán)）
遞歸調(diào)用后： start值為1，i的值為1（此處，對(duì)照棧的特性，開始進(jìn)行（2）中未完成的for循環(huán)，輸出此句后，將結(jié)束（2）中的for循環(huán)）
遞歸調(diào)用后： start值為0，i的值為0（此處，對(duì)照棧的特性，開始進(jìn)行（1）中未完成的for循環(huán)，i值將要加1）
遞歸調(diào)用前： start值為0，i的值為1（此處，進(jìn)行了（1）中一次for循環(huán)后，就要開始執(zhí)行一次遞歸語句，start值將要加1）
（4）
準(zhǔn)備進(jìn)入for循環(huán)：
遞歸調(diào)用前： start值為1，i的值為1（此處，是執(zhí)行（3）中遞歸語句的執(zhí)行輸出結(jié)果，此時(shí)也要開始執(zhí)行一次遞歸語句，start值將要加1）
（5）
第2次走完一圈（此時(shí)，start值有變成了2）
已完成?。?！
遞歸調(diào)用后： start值為1，i的值為1（此處，執(zhí)行步驟（4）中未完成for循環(huán)的回溯，進(jìn)行for循環(huán)）
遞歸調(diào)用后： start值為0，i的值為1（此處，執(zhí)行步驟（3）中未完成for循環(huán)的回溯，進(jìn)行for循環(huán)）
上述是對(duì)2！次不同排序的遞歸執(zhí)行順序分析，下面我們可以來看看對(duì)于3！次不同排序的遞歸執(zhí)行順序結(jié)果，看看其執(zhí)行順序是否滿足?！冗M(jìn)后出的特性，
PS：此處對(duì)上述代碼中定義數(shù)字進(jìn)行稍微修改，修改如下：
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);
}
具體運(yùn)行結(jié)果：
準(zhǔn)備進(jìn)入for循環(huán) 遞歸調(diào)用前： start值為0，i的值為0 準(zhǔn)備進(jìn)入for循環(huán)遞歸調(diào)用前： start值為1，i的值為1準(zhǔn)備進(jìn)入for循環(huán)遞歸調(diào)用前： start值為2，i的值為2第1次走完一圈 準(zhǔn)備進(jì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)備進(jìn)入for循環(huán) 遞歸調(diào)用前： start值為2，i的值為2 第2次走完一圈 準(zhǔn)備進(jì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)備進(jìn)入for循環(huán) 遞歸調(diào)用前： start值為1，i的值為1 準(zhǔn)備進(jìn)入for循環(huán) 遞歸調(diào)用前： start值為2，i的值為2 第3次走完一圈 準(zhǔn)備進(jìn)入for循環(huán) 遞歸調(diào)用后： start值為2，i的值為2 遞歸調(diào)用后： start值為1，i的值為1 遞歸調(diào)用前： start值為1，i的值為2 準(zhǔn)備進(jìn)入for循環(huán) 遞歸調(diào)用前： start值為2，i的值為2 第4次走完一圈 準(zhǔn)備進(jì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)備進(jìn)入for循環(huán) 遞歸調(diào)用前： start值為1，i的值為1 準(zhǔn)備進(jìn)入for循環(huán) 遞歸調(diào)用前： start值為2，i的值為2 第5次走完一圈 準(zhǔn)備進(jìn)入for循環(huán) 遞歸調(diào)用后： start值為2，i的值為2 遞歸調(diào)用后： start值為1，i的值為1 遞歸調(diào)用前： start值為1，i的值為2 準(zhǔn)備進(jì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
可以看出，運(yùn)行結(jié)果明顯滿足上述中2！次運(yùn)行結(jié)果的分析及推測(cè)結(jié)論。
