递归算法浅谈

大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。

递归算法

　　程序调用自身的编程技巧称为递归（ 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;// 递归的出口
  //以下部分为解决当前要做的(能够从最后一步或第一步着手思考要做的事)—相当与(n)
  //===================================================
    while(b<=n){//
     p[b-1]=(p[b-1]==0)?1:0;//
     b=2*b;//
     }
  //====================================================
    process(a-1);//调用自身，解决同样的但规模要小的又一问题—相当于f(n-1)


   }

   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)
*
*
*要学会把复杂的递归问题迁移成像阶层一样简单的递归问题