递归算法
程序调用自身的编程技巧称为递归（ recursion）。 一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。 注意： (1) 递归就是在过程或函数里调用自身; (2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
一个比较经典的描述是老和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山， ……。这样没完没了地反复讲故事，直到最后老和尚烦了停下来为止。
反复讲故事可以看成是反复调用自身，但如果不能停下来那就没有意义了，所以最终还要能停下来。递归的关键在于找出递归方程式和递归终止条件。即老和尚反复讲故事这样的递归方程式要有，最后老和尚烦了停下来这样的递归的终止条件也要有。
阶乘的算法可以定义成函数
当 n>0时，用 f(n-1)来定义 f(n)，用 f(n-1-1)来定义 f(n-1)……，这是对递归形式的描述。
当 n=0时， f(n)=1，这是递归结束的条件。
其实所有的递归问题都可以看成是阶层问题
所要解决的整个问题(整个递归函数)看成是 f(n).在这个递归函数中要做到如下几点:
*1.写出递归的出口 *2.解决当前要解决的问题-----相当与阶层问题中的(n) *3.递归下去(调用自身)解决相同的但规模要小的又一问题-----相当于f(n-1)
如果函数实现了这几点,那么递归算法也就基本成功.
不过有些问题他的f(n-1)可能要调用几次(可能每次的参数还不同),因为他在实现(n)的时候要先调用f(n-1)为前提,
这样的例子很多.比如梵塔问题就是这种情况.
总而言之,你要懂的把复杂的递归问题迁移成简单的阶层递归问题,这时候问题就比较好理解和解决.
下面是几个用递归解决问题的几个例子
一.用递归的算法把数组中的N个数按颠倒的次序重新存放。
经过上面的方法来分析得出程序如下:
package sf.digui;
public class Recursion
{ private int b[]=null;
private int len=0;
public Recursion(int b[])
{ this.b=b;
this.len=b.length;
}
public void resevert(int i,int j)
{
if(i>=j)
return; //====================
b[i]=b[i]+b[j];
b[j]=b[i]-b[j];//注意：这里没有通过第三方(另开内存)来实现两个变量的值交换
b[i]=b[i]-b[j];
//=========================
resevert(i+1,j-1);
}
public void printThis()
{
for(int i=0;i<len;i++)
{
System.out.print(b[i]+" ");
}
System.out.println();
}
public static void main(String[] args)
{
int b[]={1,2,3,4,5,6,7,8,9};
int len=b.length;
Recursion rec=new Recursion(b);
System.out.println("数组起始的数为：");
rec.printThis(); rec.resevert(0,len-1);
System.out.println("数组经过倒转之后的数为：");
rec.printThis();
}
}
二..用递归算法完成：有52张牌，使它们全部正面朝上，第一轮是从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；第二轮从第3张牌开始，凡是3的倍数位置上的牌，正面朝上的翻成正面朝下,正面朝下的翻成正面朝上；第三轮从第4张牌开始，凡是4的倍数位置上的牌按上面相同规则翻转，以此类推，直到第一张要翻的牌超过52为止。统计最后有几张牌正面朝上，以及它们的位置号。
经过上面的方法分析,得出程序如下:
package sf.digui;
public class DiGui
{ private int n;
//private int a;
private int p[]=null;//存放所有牌的正反面信息
public DiGui(int n)
{
this.n=n;
//a=n;
p=new int[n];
for(int i=0;i<n;i++)
{
p[i]=0;//这里0表示是正面，1表示是反面
}
}
public void process(int a){//======相当于f(n)
int b=a;
if(a==1) return;// 递归的出口
//调用自身，解决相同的但规模要小的又一问题---相当于f(n-1)
process(a-1); //下面部分为解决当前要做的(可以从最后一步或第一步着手思考要做的事)---相当与(n) //===================================================
while(b<=n)
{//
p[b-1]=(p[b-1]==0)?1:0;//
b=2*b;//
}
//====================================================
}
public void printThis()
{ process(n);
for(int i=0;i<n;i++)
{
System.out.println("第"+(i+1)+"张的正反面序号为："+p[i]);
}
}
public static void main(String[] args)
{ DiGui digui=new DiGui(52);
digui.printThis();
}
}
/*说明： *我认为所有递归都可看成像阶层一样的问题---相当于f(n)=n+f(n-1)，都要做递归函数中 *解决如下几个问题： *1.写出递归的出口 *2.解决当前要解决的问题-----相当与阶层问题中的(n) *3.递归下去(调用自身)解决相同的但规模要小的又一问题-----相当于f(n-1) * * *要学会把复杂的递归问题迁移成像阶层一样简单的递归问题
**/
以上是我学习递归的一些想法,希望有更多人回复,大家一起来谈论,交流,共同进步.
0 评论:
Post a Comment