程序设计中，有一种特殊的程序――递归程序，递归程序是直接调用自己或通过一系列的过程间接调用自己的程序。递归程序在程序设计中经常出现，因此应该学会使用递归程序求解问题，但递归程序运行的效率一般都比较低，因此应对递归程序进行优化。

　　下面结合旅行家问题谈谈递归的优化。

　　一．递归程序的实现

　　旅行家问题如下：旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是有名的n―p难题之一。在n很大时，并不采用本文所用的递归遍历方法，而是采用其他方法，如神经网络、遗传算法等，得到问题的解。

　　要得到n个城市依次经历的最短路径，应把各个对n个城市的经历所经过的路程相比较，选出其中的最小值作为返回结果。

　　用递归程序解决旅行家问题时，思路与循环方法一样：找出各种可能的经历顺序，比较在各个顺序下所走的路程，从中找出最短路程所对应的经历顺序。该问题中如何通过递归得到对所有可能路径的经历应作为重点，而对路程的计算、比较、更新与循环方法类似。在该问题的递归调用中，第n对第n-1层传递过来的已经经历的城市进行判断，以决定是否已经遍历，如果n个城市已经遍历，则计算、比较、更新路程，然后向上一层返回；如果没有遍历，则选择一个未经历的城市加入已经历的城市并一同传递给第n+1层。在这里，第n层调用传入的参数可以看成已经经历的城市和已确定的最短路程，返回的结果可以看成经更新的最短路程与经历顺序。

　　在java中定义一个类

class cities { private int[][] cities； //各城市表示为（x,y）x,y为0到99之间的值 private int[] shortestpath； //保存最短路程对应的经历顺序 private int num； //保存n（城市个数） private long shortestlength = 100000000；//n个城市遍历时可能最大路程 private long getlength(int[] tpath) {．．．} //计算以tpath为经历顺序的路程 public cities(int n) //构造n个城市的坐标，假设为0到99之间的随机数 { ．．． } public int[] getshortestpath() //获得最短路径 { int[] temppath = new int[num]； shortestpath = new int[num]； int[] citiestoured = new int[num]； //保存第i个城市是否已经经历 int citiesnum = 0； //已经经历城市的个数 for(int i=0； i<num； i++) citiestoured[i] = 0； gothrough(temppath, citiesnum, citiestoured)；//遍历各城市 for(int i=0； i<num； i++) temppath[i] = shortestpath[i]； //得到遍历顺序 return temppath； //返回结果 } private void gothrough(int[] tpath, int cnum, int[] ctoured) //遍历n个城市 { if (cnum == 0) //无经历城市时，选择第1个城市 { cnum++； tpath[0] = 0； ctoured[0] = 1； gothrough(tpath, cnum, ctoured)； } else if (cnum == num) //各个城市已经经历，结束 { long templength = getlength(tpath)；//计算此经历顺序所走的路程 if (templength < shortestlength) //比较路程 { shortestlength = templength； //更新最短路程及其经历顺序 for(int i=0； i<num； i++) shortestpath[i] = tpath[i]； } } else { for(int i=0； i<num； i++) if (ctoured[i] != 1) //选择未经历的城市 { ctoured[i] = 1； //加入已经历城市 tpath[cnum]= i； cnum++； //已经历城市个数+1 gothrough(tpath, cnum, ctoured)；//调用下一层 ctoured[i] = 0； //恢复本层的状态： cnum--； //已经历城市及个数 } //end if in for(i) } //end else } private long getlength(int[] tpath) //以指定顺序计算遍历路程 { long length = 0； //路程 int nowpoint = 0； //当前城市，第一次取0 for(int i=1； i<num； i++) { int j = tpath[i]； length+=(long)math.sqrt((cities[j][0]-cities[nowpoint][0])*(cities[j][0]-cities[nowpoint][0])+(cities[j][1]-cities[nowpoint][1])*(cities[j][1]-cities[nowpoint][1]))；//加上当前、下一城市间的距离 nowpoint = j； //更新当前城市 } length+=(long)math.sqrt((cities[0][0]-cities[nowpoint][0])*(cities[0][0]-cities[nowpoint][0]) +(cities[0][1]-cities[nowpoint][1])*(cities[0][1]-cities[nowpoint][1]))；//加上首尾城市间的距离 return length； } } // cities类定义结束

　　在这里使用递归，实现了对n可变时问题的求解。
　　二．递归程序的优化

　　递归程序的优化是程序优化的一种，具有程序优化的一般性，同时更应考虑它的特殊性。递归程序优化中应主要着眼尽快结束递归，避免无谓的调用，因为结束得越早，程序所付出的代价就越小。

　　在旅行家问题中，对城市的遍历gothrough函数是递归程序，下面讨论对它的优化。

　　ⅰ．该问题的第一次优化：各个城市之间的距离在cities类构造时就已经确定，而每一次遍历各个城市后，getlength函数都要计算一次相邻两城市及首尾城市间的距离，显然城市间距离的计算只要进行一次就可以了。因此可以定义一个函数initdistance，在构造函数cities()中调用，并重新定义getlength函数，直接对相邻及首尾城市的距离取和。如下：

　　1．类中增加属性private long[] distance； //在initdistance方法中构造

　　2．定义私有方法 private void initdistance() //计算各个城市之间的距离（由于仅计算一次，故未优化）

private void initdistance() { distance = new long[num][num]; for(int i=0；i<num； i++) for(int j=0；j<num；j++) { if (i == j) distance[i][j] = 0l； else distance[i][j]=(long)math.sqrt( (cities[i][0]-cities[j][0])*(cities[i][0]-cities[j][0]) +(cities[i][1]-cities[j][1])*(cities[i][1]-cities[j][1]))； } }

　　3．重新定义getlength

private long getlength(int[] tpath) { long length = 0l； for(int i=1；i<num； i++) length += distance[tpath[i-1]][tpath[i]]； length += distance[tpath[0]][tpath[num-1]]； return length； }

　　4．重新定义构造函数cities(int r)

public cities(int r) { ．．． initdistance()； //计算各个城市间的距离 }

　　ⅱ．该问题的第二次优化：考虑下面的情况，经历顺序为1―2―3―4―5―6―与1―2―3―4―6―5―二者中前四个城市经历顺序相同，可以定义一个变量来保存已经历的路程，只有在经历顺序改变的时候才对已经历的路程进行更新。进行如下优化：

　　1．增加private long touredlength属性并初始化为0，用来记录到“目前”为止所经历的路程。

　　2．重新定义gothrough

private void gothrough(int[] tpath, int cnum, int[] ctoured) { ．．． // 同上 else if (cnum == num) { long tl = touredlength + distance[tpath[num-1]] [tpath[0]]；▲// tl记录已经历的路程 （用▲标志改进点，下同） if (tl < shortestlength) { shortestlength = tl； for(int i=0; i<num; i++) shortestpath[i] = tpath[i]； } } else // 0< citiesnum <n { for(int i=0； i<num； i++) if (ctoured[i] != 1) //not toured { tpath[cnum]= i； ctoured[i] = 1； touredlength += distance[tpath[cnum-1]] [i]；▲ cnum++； gothrough(tpath, cnum, ctoured)； cnum--； touredlength -= distance[tpath[cnum-1]] [i]；▲ ctoured[i] = 0； } } }

　　3．去除getlength。

　　ⅲ．该问题的第二次优化：进一步考虑对路程的计算，设想下面的情况：n=5，已经历了2个城市，且旅行路程为200，目前已知的最短路程为260，而其他三个城市的任意两个城市之间的距离大于30。在这种情况下，再继续遍历只是徒劳，此时就可以结束调用返回。针对这种情况，如下优化：

　　1．增加属性 private long shortestdistance[]，来保存城市之间的最短距离，次最短距离，次次最短距离，．．．，并在initdistance中得到各距离的值。

private void initdistance() { ．．． shortestdistance = new long[num +1]； shortestdistance[0] = 0； for(int i=0； i<num； i++) { long dis = 10000l； for(int j=i+1； j<num； j++) if (distance[i][j] < dis) dis = distance[i][j]； shortestdistance[i+1] = shortestdistance[i] + dis； } }

　　2．更新gothrough

private void gothrough(int[] tpath, int cnum, int[] ctoured) { ．．． else if (cnum == num) { long tl = touredlength + distance[tpath[num-1]] [tpath[0]]； if (tl < shortestlength) { shortestlength = tl； for(int i=0； i<num； i++) shortestpath[i] = tpath[i]； } } else // 0< citiesnum <num { if (touredlength + shortestdistance[num - cnum] < shortestlength) ▲ //如果已经历的路程+可能的最短路程>已知的最短路程，则不再继续走下去 { for(int i=0； i<num； i++) if (ctoured[i] != 1) //not toured { tpath[cnum]= i； ctoured[i] = 1； touredlength += distance[tpath[cnum-1]] [i]； cnum++； gothrough(tpath, cnum, ctoured)； cnum--； touredlength -= distance[tpath[cnum-1]] [i]； ctoured[i] = 0； } } } }

　　比较各种优化方法的求解时间，得到下表的数据（windows 98，piii550，128m）：

方案	仅用citiestoured	引入distance改进getlength	引入touredlength,去除getlength	引入shortestdistance
问题规模
n=10	1850毫秒	390毫秒	100毫秒	不足1毫秒
n=12	220000毫秒	48200毫秒	1000毫秒	100毫秒

　　从以上数据可以得出结论：递归程序一般都有很大的优化空间，递归程序经过优化后，可以在很大程度上提高程序的效率。经过优化的程序既保留了递归程序简单易读的特点，又在一定程度上弥补了程序时间效率低的不足。

　　同时，也可以看出递归程序的先天缺陷，在现实中大规模的旅行商问题递归程序是无法解决的（在可以接受的时间内），普遍采用的是遗传算法来解决，因此应事先决定是否采用递归程序来解决自己的问题。即使如此，本文对于可以应用的递归程序来讲也具有一定的参考意义。