不会用递归解题？这一篇教会你！！

深藏阁楼爱情的钟 2022-11-07 11:55 142阅读 0赞

### 递归 ###

*   *  1、什么是递归？
     *  2、听听音乐，放松心情，享受思考的过程！
     *   *  2.1、单递归问题
         *  三级目录

## 1、什么是递归？ ##

通俗来说，递归就是一个方法自己调用自己，但是，如果一直调用的话就会造成栈溢出。所以，**递归需要出口**，那么，递归的出口应该如何创建呢？  
         很明显，这里需要用到参数。只有使用形式参数，才能将数据递归到下一个方法，这时候我们只需要让形式参数在每一次递归的时候逐渐变化，然后在达到一定条件的时候终止，这，就是构造出口 **`(ps:哈哈，突然就想写一句,这，就是西厂)`**  
         当执行触发了出口之后，就需要结束程序了，通常是使用 **return语句**

**当我们拿到一个题，应该怎么去构造递归性呢？**  
对于递归来说，最最重要的就是构造递归的条件（构造递归的相似性），同时也是能够让递归一直往下走的条件，通常情况是利用方法参数的递归变化来进行实现，而一旦递归的条件构造好了，那么出口自然也就有了！  
         下面我们来练习几道经典的算法题(别觉得简单就觉得不重要，蓝桥杯大多数题都是在此基础上演变而来的)；

## 2、听听音乐，放松心情，享受思考的过程！ ##

### 2.1、单递归问题 ###

顾名思义，就是单个递归，一个方法中只需要有一个递归就能解决问题！**`以下是笔者选取的比较经典的入门题，仅供参考！！！`**

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

**`求一个数的阶层和：`**  
题目分析： 假设要求的数是N，那么它的阶层和就是1\* 2\* 3\*…\*N，通过他的变化规律可以发现，累乘的参数逐渐递增，所以，我们可以构造带一个参数的方法，让其形式参数逐渐递键，直到该参数等于1，方法结束。

public static int getNumStratum(int num){ 
            if(num==1) return 1;
            return num*getNumStratum(num-1);
    }

**`反转字符串：`**  
题目分析： 这题如果暴力破解的话，直接对字符串逆序遍历然后输出就行了，但如果用递归，那么我们首先应该去信办法构造其相似性，也就是构造递归的条件，在暴力破解中，我们是通过循环去遍历字符串的下标，那么，递归我们同样也可以如此。对于参数，我们肯定需要一个字符串，同时，我们还需要一个用来遍历字符串的指针，在每一次递归的过程中让指针逐渐往前移动，直到指针指向了字符串的第一个字符，递归结束！

public static String reversalStr(String arg0,int end){ 
          if(end==0){ 
              return arg0.charAt(0)+"";
          }
          //只改变指向下标，字符串不变
          return arg0.charAt(end)+reversalStr(arg0,end-1);
        }

**`求最大公约数:`**  
题目分析： 首先，我们需要知道约数是什么？约数，就是能够被一个数整除的数。而我们要去求两个数公共的最大的约数，在小学数学中，求两个数的最大约数就是通过不断的找出二者的约数，然后将所有的约数相乘，结果即为它们的最大公约数！这里直接暴力的话可以直接遍历二者从1到本身的所有约数，然后找出二者所有的公约数，但这样就显得太唠了，这里我比较推荐的一种方法就是 **辗转法**，这里用到了一点点数学的知识，稍微分析一下就ok了。以下是代码实现：

public static int maxCommonDivisor(int num1,int num2){ 
    		//如果num2能被num1整除，那么它们的最大公约数就是num2
            if(num1%num2==0){ 
                return num2;
            }
            return maxCommonDivisor(num2,num1%num2);
        }

(未完，明天更后续！！！)

### 三级目录 ###