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

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

　　一．递归程序的实现

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

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

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

　　在java中定义一个类

　　classcities

　　{
　　
　　privateint[][]cities；//各城市表示为（x,y）x,y为0到99之间的值
　　
　　privateint[]shortestpath；//保存最短路程对应的经历顺序
　　
　　privateintnum；//保存n（城市个数）
　　
　　privatelongshortestlength=100000000；//n个城市遍历时可能最大路程
　　
　　privatelonggetlength(int[]tpath){．．．}//计算以tpath为经历顺序的路程
　　
　　publiccities(intn)//构造n个城市的坐标，假设为0到99之间的随机数
　　
　　{
　　
　　．．．
　　
　　}
　　
　　publicint[]getshortestpath()//获得最短路径
　　
　　{
　　
　　int[]temppath=newint[num]；
　　
　　shortestpath=newint[num]；
　　
　　int[]citiestoured=newint[num]；//保存第i个城市是否已经经历
　　
　　intcitiesnum=0；//已经经历城市的个数
　　
　　for(inti=0；i<num；i++)
　　
　　citiestoured[i]=0；
　　
　　gothrough(temppath,citiesnum,citiestoured)；//遍历各城市
　　
　　for(inti=0；i<num；i++)
　　
　　temppath[i]=shortestpath[i]；//得到遍历顺序
　　
　　returntemppath；//返回结果
　　
　　}
　　
　　privatevoidgothrough(int[]tpath,intcnum,int[]ctoured)//遍历n个城市
　　
　　{
　　
　　if(cnum==0)//无经历城市时，选择第1个城市
　　
　　{
　　
　　cnum++；
　　
　　tpath[0]=0；

　　ctoured[0]=1；
　　
　　gothrough(tpath,cnum,ctoured)；
　　
　　}
　　
　　elseif(cnum==num)//各个城市已经经历，结束
　　
　　{
　　
　　longtemplength=getlength(tpath)；//计算此经历顺序所走的路程
　　
　　if(templength<shortestlength)//比较路程
　　
　　{
　　
　　shortestlength=templength；//更新最短路程及其经历顺序
　　
　　for(inti=0；i<num；i++)
　　
　　shortestpath[i]=tpath[i]；
　　
　　}
　　
　　}
　　
　　else
　　　　
　　{
　　
　　for(inti=0；i<num；i++)
　　
　　if(ctoured[i]!=1)//选择未经历的城市
　　
　　{
　　
　　ctoured[i]=1；//加入已经历城市
　　
　　tpath[cnum]=i；
　　
　　cnum++；//已经历城市个数+1
　　
　　gothrough(tpath,cnum,ctoured)；//调用下一层
　　
　　ctoured[i]=0；//恢复本层的状态：
　　
　　cnum--；//已经历城市及个数
　　
　　}//endifinfor(i)
　　
　　}//endelse
　　
　　}
　　
　　
　　
　　privatelonggetlength(int[]tpath)//以指定顺序计算遍历路程
　　
　　{
　　
　　longlength=0；//路程
　　
　　intnowpoint=0；//当前城市，第一次取0
　　
　　for(inti=1；i<num；i++)
　　
　　{
　　
　　intj=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]))；//加上首尾城市间的距离
　　
　　returnlength；

　　}
　　
　　}//cities类定义结束
　　
　　在这里使用递归，实现了对n可变时问题的求解。
　　
　　三．递归程序的优化

　　递归程序的优化是程序优化的一种，具有程序优化的一般性，同时更应考虑它的特殊性。递归程序优化中应主要着眼尽快结束递归，避免无谓的调用，因为结束得越早，程序所付出的代价就越小。
　　
　　在旅行家问题中，对城市的遍历gothrough函数是递归程序，下面讨论对它的优化。
　　
　　ⅰ．该问题的第一次优化：各个城市之间的距离在cities类构造时就已经确定，而每一次遍历各个城市后，getlength函数都要计算一次相邻两城市及首尾城市间的距离，显然城市间距离的计算只要进行一次就可以了。因此可以定义一个函数initdistance，在构造函数cities()中调用，并重新定义getlength函数，直接对相邻及首尾城市的距离取和。如下：
　　
　　1．类中增加属性privatelong[]distance；//在initdistance方法中构造
　　
　　2．定义私有方法privatevoidinitdistance()//计算各个城市之间的距离（由于仅计算一次，故未优化）
　　
　　privatevoidinitdistance()
　　
　　{
　　
　　distance=newlong[num][num];
　　
　　for(inti=0；i<num；i++)
　　
　　for(intj=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
　　
　　privatelonggetlength(int[]tpath)
　　
　　{
　　
　　longlength=0l；
　　
　　for(inti=1；i<num；i++)
　　
　　length+=distance[tpath[i-1]][tpath[i]]；
　　
　　length+=distance[tpath[0]][tpath[num-1]]；
　　
　　returnlength；
　　
　　}

　　4．重新定义构造函数cities(intr)
　　
　　publiccities(intr)
　　
　　{．．．
　　　　
　　initdistance()；//计算各个城市间的距离
　　
　　}
　 　
　　ⅱ．该问题的第二次优化：考虑下面的情况，经历顺序为1―2―3―4―5―6―与1―2―3―4―6―5―二者中前四个城市经历顺序相同，可以定义一个变量来保存已经历的路程，只有在经历顺序改变的时候才对已经历的路程进行更新。进行如下优化：
　　
　　1．增加privatelongtouredlength属性并初始化为0，用来记录到“目前”为止所经历的路程。
　　
　　2．重新定义gothrough
　　
　　privatevoidgothrough(int[]tpath,intcnum,int[]ctoured)
　　
　　{
　　
　　．．．//同上

　　elseif(cnum==num)
　　
　　{
　　
　　longtl=touredlength+distance[tpath[num-1]][tpath[0]]；▲//tl记录已经历的路程
　　
　　（用▲标志改进点，下同）
　　
　　if(tl<shortestlength)
　　
　　{
　　
　　shortestlength=tl；
　　
　　for(inti=0;i<num;i++)
　　
　　shortestpath[i]=tpath[i]；
　　
　　}

　　}
　　
　　else//0<citiesnum<n
　　
　　{
　　
　　for(inti=0；i<num；i++)
　　
　　if(ctoured[i]!=1)//nottoured
　　
　　{
　　　　
　　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．增加属性privatelongshortestdistance[]，来保存城市之间的最短距离，次最短距离，次次最短距离，．．．，并在initdistance中得到各距离的值。
　　
　　privatevoidinitdistance()
　　
　　{
　　
　　．．．
　　
　　shortestdistance=newlong[num+1]；
　　　　
　　shortestdistance[0]=0；

　　for(inti=0；i<num；i++)

　　{

　　longdis=10000l；
　　
　　for(intj=i+1；j<num；j++)
　　
　　if(distance[i][j]<dis)
　　
　　dis=distance[i][j]；
　　
　　shortestdistance[i+1]=shortestdistance[i]+dis；
　　
　　}
　　
　　}
　　
　　2．更新gothrough
　　
　　privatevoidgothrough(int[]tpath,intcnum,int[]ctoured)
　　
　　{
　　
　　．．．
　　
　　elseif(cnum==num)
　　
　　{
　　
　　longtl=touredlength+distance[tpath[num-1]][tpath[0]]；
　　
　　if(tl<shortestlength)
　　
　　{
　　
　　shortestlength=tl；
　　
　　for(inti=0；i<num；i++)
　　
　　shortestpath[i]=tpath[i]；
　　
　　}
　　
　　}
　　
　　else//0<citiesnum<num
　　
　　{
　　
　　if(touredlength+shortestdistance[num-cnum]<shortestlength)▲
　　
　　//如果已经历的路程+可能的最短路程>已知的最短路程，则不再继续走下去
　　
　　{
　　
　　for(inti=0；i<num；i++)
　　
　　if(ctoured[i]!=1)//nottoured
　　
　　{
　　
　　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；
　　
　　}
　　
　　}
　　
　　}
　　
　　}
　　
　　比较各种优化方法的求解时间，得到下表的数据（windows98，piii550，128m）：

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

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