一、写作此文的原因:
学过
程序设计的朋友都知道,存在自调用的算法称作递归算法。
递归往往能给我们带来非常简洁非常直观的代码形势,从而使我们的编码大大简化,然而递归的思维确实很我们的常规思维相逆的,我们通常都是从上而下的思维
问题,而递归趋势从下往上的进行思维,正由于此,很多人对于递归有着深深的恐惧,我曾经也是如此,如今为把我的经验通过几个经典的例子与初学者共享,故作此文,希望能对需要者有所助益,如若如此,便是幸甚。。。
二、递归算法设计的基本思想是:对于一个复杂的问题,把员问题分解为若干个相对简单前类同的子问题,继续下去直到子问题简单到能够直接求解,也就是说到了递推的出口,这样原问题就有递推得解。
关键要抓住的是:(1)递归出口
(2)地推逐步向出口逼近
三、具体实例
1。汉诺塔
这是递归的超经典的例子,几乎每本程序设计书上谈到递归都会介绍。具体情景不再赘述。以我上述的方法观之:(1)递归的出口在于disk数为一的时候
(2)向出口逼近:如果不是一,是n,则我们先挪动上面n-1块disk,等上面挪完,即递归返回的时候,我们挪动最底下的disk。
仅仅如此,一个貌似十分复杂的问题就解决了,因为挪动那n-1块disk的时候,会继续向上减少,直到disk的数量为一为止。下面给出java程序编码(已测试过,运行正常):
importjavax.swing.JOptionPane;
publicclassHanoi{
privatestaticfinalStringDISK_B="diskB";
privatestaticfinalStringDISK_C="diskC";
privatestaticfinalStringDISK_A="diskA";
staticStringfrom=DISK_A;
staticStringto=DISK_C;
staticStringmid=DISK_B;
publicstaticvoidmain(String[]args){
Stringinput=JOptionPane.showInputDialog("pleaseinputthenumberofthedisksyouwantmemove.");
intnum=Integer.parseInt(input);
move(num,from,mid,to);
}
privatestaticvoidmove(intnum,Stringfrom2,Stringmid2,Stringto2){
if(num==1){
System.out.println("movedisk1from"+from2+"to"+to2);
}
else{
move(num-1,from2,to2,mid2);
System.out.println("movedisk"+num+"from"+from2+"to"+to2);
move(num-1,mid2,from2,to2);
}
}
}
2。这是一个排列的例子,它所做的
工作是将输入的一个字符串中的所有元素进行排序并输出,例如:你给出的参数是"abc"则程序会输出:
abc
acb
bac
bca
cab
cba
(1)算法的出口在于:low=high也就是现在给出的排列元素只有一个时。
(2)算法的逼近过程:先确定排列的第一位元素,也就是循环中i所代表的元素,