算法之路——递归

╰+攻爆jí腚メ 2022-07-17 00:15 142阅读 0赞

*  **[递归][Link 1]**（recursion）：程序调用自身的编程技巧。
    
     *  递归满足2个条件：
        
        1）有反复执行的过程（调用自身）
        
        2）有跳出反复执行过程的条件（递归出口）

--------------------

*  递归大家都懂是什么意思，在现实生活中我们也很容易去操作，但是在程序员的世界递归确实是很多人都头疼的一大难题。我总结了递归特色的一句话：**简约而不简单**

--------------------

*  本博主打算通过四个案列来详细的剖析递归里面的思想
    
     *  阶乘算法
     *  全排列算法
     *  汉诺塔问题
     *  斐波那契数列

--------------------

*  阶乘
    
    阶乘应该是递归里面比较简单的问题了，所以我放在第一个将，在这里并不是越往后的越难，我个人觉得斐波那契数列和阶乘是同级别的，都很简单，阶乘主要就是拿一个数不停的去和比自己小一的数据相乘，一直称到1为止。最后返回数字就是阶乘的数据。这个可以用循环也可以用递归，既然我们本章主题是递归，那我们就用递归来实现吧。

//阶乘
    int recursive(int i)
    {
        int sum = 0;
        if (0 == i)
            return (1);
        else
            sum = i * recursive(i-1);
        return sum;
    }

*  全排列问题：
    
    解法一、在数组里进行两两不重复交换，每次交换得到的新数组组成的数据就是全排列的一种情况。 这个有点类似我们排序中的冒泡排序。  
    ![这里写图片描述][20160823152415308]  
    这个逻辑进行下去就是不断的交换，每次交换完成就会产生一组数据，我们只要输出就行了

//全排列
    inline void Swap(int &a,int &b)
    {
        int temp=a;
        a=b;
        b=temp;
    }
    void Perm(int list[],int k,int m)
    {
        if (k == m-1) 
        {
            for(int i=0;i<m;i++)
            {
                printf("%d",list[i]);
            }
            printf("n");
        }
        else
        {
            for(int i=k;i<m;i++)
            {
                Swap(list[k],list[i]); 
                Perm(list,k+1,m);
                Swap(list[k],list[i]); 
            }
        }
    }

解法二、对新数据进行遍历，遍历会拿到每一条数据，拿到数据我们在判断这个数据是否已经被使用了，是则抛弃，否则选择。在递归进入结束条件时，我们输出我们的新数据，最后跳出本条递归。跳出之后我们就该将最近选择的数据状态置为未使用状态，方便下一次遍历使用。这样就会形成全排列。

public static void Circle(Object[] arry,Object[] visit,Integer index){
            if(index==arry.length){
            //自己写的输出list集合的方法。读者自己写
                outArry(resultArry);
                return ;//递归结束；开始想外层跳出
            }else{
                for(int i=0;i<arry.length;i++){
                    if((Integer)visit[i]==0){
                        resultArry[index]=arry[i];
                        //将该数字置为选中状态，下次再配到该数字则弃用该数字
                        visit[i]=1;
                        index++;
                        Circle(arry, visit, index);
                        index--;
                        //跳出循环，应该讲最近使用的数字状态恢复为0
                        visit[i]=0;
                    }
                }
            }
        }

解法二不足之处：在解法二中我将数组写死了，不能根据用户的变化而将记录数组进行改变，后来我进行改进，具体代码如下：

private static List<Object> resultArry=new ArrayList<Object>();
        private static List<Integer> state=new ArrayList<Integer>();
        public static void Circle(Object[] arry,Integer index){
            if(index==arry.length){
                outList(resultArry);
                return ;//递归结束；开始想外层跳出
            }else{
                for(int i=0;i<arry.length;i++){
                    if(state.get(i)==0){
                        resultArry.add(arry[i]);
                        state.set(i, 1);
                        index++;
                        Circle(arry, index);//递归的体现
                        resultArry.remove(arry[i]);
                        index--;
                        state.set(i, 0);
                    }
                }
            }
        }

效果对1、2、3进行全排列：  
![这里写图片描述][20160823154036018]  
效果对1、2、3、4进行全排列：  
![这里写图片描述][20160823160452643]

*  汉诺塔问题
    
    ![这里写图片描述][20160823160529616]
    
    ![这里写图片描述][20160823160544394]
 *  思路梳理：
    
    上图中想实现a–>b，我们必须先将a中上面两个盘子拿到借助柱子B上。那么下面我们要考虑的是如何将A中两个盘子保持顺序的拿到B上呢，这时我们就需要借助C柱来完成，这就需要用递归了。因为我们最终问题是将A上三个盘子借助B按顺序拿到C上，我将问题转换成了将A上的两个盘子借助C拿到B上。ABC在方法里我用1、2、3代替。如果我将方法设为`public static void hanoi(int n,int p1,int p2,int p3)`  
    也就是说一开始我们调用的是`hanoi(3,1,2,3)`  
    到我们里面进行分析后变为`hanoi(2,1,3,2)`（这里转化理解醉关键）  
    下面我们就一层一层向内部挖掘，那么，我们该什么时候结束这个循环递归呢？答案当然是在A柱上就剩一个盘子的时候我们就结束了，也即是方法`hanoi(1,1,2,3)` 这个时候我们只用将A柱上的一个盘子直接拿到C盘上
    
    还有一点就是在我们都执行过了，现在我们回到我第一次剖析的地方，这个时候我们已经成功的将A柱上两个盘子拿到了B柱上了。这个时候我们就可以将A柱上最后一个盘子拿到C盘上，拿完之后我们该做什么呢，拿完之后我们可以将问题看成将B柱上的两个盘子借助A柱按顺序拿到C柱上。用方法表示为`hanoi(2,2,1,3)`,这部我们继续走上面的思想就会完成。
    
    代码：

public static void hanoi(int n,int p1,int p2,int p3)
        {
            if(1==n){
                System.out.println("盘子从"+p1+"移动到"+p3);
            }
            else
            {
                hanoi(n-1,p1,p3,p2);
                System.out.println("盘子从"+p1+"移动到"+p3);
                hanoi(n-1,p2,p1,p3);
            }
        }

效果：

![这里写图片描述][20160823162938240]

--------------------

*  斐波拉契数列
    
    斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……
    
    这个数列从第三项开始，每一项都等于前两项之和。
    
    有趣的兔子问题：
    
    一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？
    
    分析如下：
    
    第一个月小兔子没有繁殖能力，所以还是一对；
    
    两个月后，生下一对小兔子，总数共有两对；
    
    三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，总数共是三对；
    
    ……　
    
    依次类推可以列出下表：

//斐波那契
    long Fib(int n)
    {
     if (n == 0)
      return 0;
     if (n == 1)
      return 1;
     if (n > 1)
      return Fib(n-1) + Fib(n-2);
    }

--------------------

近期本博主将主要更新算法一类的博文，可能更新进度会慢点！

--------------------

> 做最好的自己，每天进步一点点

[Link 1]: http://baike.baidu.com/link?url=rRzLPYC8BdMRyP4B0ny4IrH6vIaN0fwAXE53Sy4SP6ANL8oVlDClC8W6BcGRGYWQvSLAOz6Z8Ws_1AWEV0d3ba
[20160823152415308]: /images/20220717/c68e071affa64ef599f174958bcbabee.png
[20160823154036018]: /images/20220717/d2cd42efea6440dd8b6d9ce3674c3367.png
[20160823160452643]: /images/20220717/955f0c6942ec4610a16440c97a098ad8.png
[20160823160529616]: /images/20220717/5f71ba998c3a4d03b710fc92a2749d55.png
[20160823160544394]: /images/20220717/85e02659d1894cf6b57e92cf503244dc.png
[20160823162938240]: /images/20220717/85202fec5e98415bb02d8b61ce8f1544.png