一学一记:递归

¶递归

¶概念:

直接从递归算法的特点来说，递归是对不同数据规模的同等类型问题的求解方式，通过将问题分解为子问题，求解子问题以达到解开父级问题的目的
这么说比较绕，引用王峥老师的《数据结构与算法之美》中的递归场景：
当你带着你女朋友(也不知道你有没有)去电影院看电影,坐在中间某一排的时候，因为太暗了看不清，你女友问你现在坐在第几排，你也不知道，只能问前面的人他们是第几排，然后参照得出你所在的位置；
如果你前面的人也不知道自己是第几排的话，他们就需要继续往前一排问；
直到有人可以明确地回答自己所在的排数，最后你就间接得出了自己所在的位置。
这个场景中提到的求解你所在的排数的问题，涉及到几个数据：
- 你前一排的人的排数
- 可以明确知道自己所在排数的人
- 前者等同于你询问自己的排数，后者决定了哪里会得到答案

¶递归的适用场景

从上面的例子总结一下递归算法的应用场景，当问题满足以下三个条件的时候，可以考虑使用递归
- 一个问题可以分解为几个子问题的解
  - 上面的例子里，你前一排的人的位置，就是你所在位置的子问题
- 这个问题与分解后的子问题，除了数据不同，求解思路完全一样
  - 你需要询问你前一排的人得到自己所在的排数，你前一排的人也需要同样询问确定他所在的位置
- 存在递归终止条件
  - 当有人可以明确地回答你他所在的排数，你也就可以得到自己所在的排数了；

¶如何编写递归代码

将问题转化成代码需要先对问题进行抽象，得出问题的概念模型，王峥老师推荐的方法是：写出递推公式，找到终止条件，剩下的就是将递推公式转换成代码
求解 n 个台阶走法:
- 存在 n 个台阶，你一次可以跨1步或者2步
- 求解n个台阶会有几种走法
- 可能第一反应是脑子里演练这个过程，它的一次次调用是怎样的，最终停止条件又是什么…这样很难得出问题的解法，递归的实现思路和我们思考问题的思路差别挺大，我们无法非常直观地自己展示出这个过程
- 寻找递推公式 : 先尝试把问题模型抽象出来
  - 用 f(n) 表示 n 个台阶走法的解
  - 走完1步后，剩下n-1 个台阶的走法，加上走了2步之后，剩下 n-2 个台阶的走法， f(n) = f(n-1) + f(n-2)
  - 当 n=1,n=2 的时候问题都有解，所以 f(1) = 1,一步走完；f(2) = 2，解是 1，1 和 2 两种走法
  - 转换成递归代码:
    - 1
      2
      3
      4
      5
      6
      
      int f(int n){
      if(n==1) return 1;
      if(n==2) return 2;
      return f(n-1)+f(n-2);
      }
    - n =1 或 n=2 作为递归终止的条件
    - n > 2 时持续求子问题的解，直到 n 代表的数据规模有解

¶递归代码的缺陷

递归深度过大导致的堆栈溢出
- 每一次的方法调用都是一次方法栈帧在函数调用栈的入栈和出栈过程，而递归是一直循环调用，递归层次太深或没有终止条件都是导致堆栈溢出
- 当数据规模大致可以预测的情况下，可以指定递归深度，防止堆栈溢出；不过这种方法能够使用的场景比较有限
递归代码警惕重复计算
- 以上面的 n 个台阶走法为例，假设 n =6 ，求解 f(6) = f(5) + f(4) ; 求解 f(5) + f(4) + f(3) , 求解 f(4) = f(3) + f(2) … 可以看到这里存在重复计算的步骤；递归本身是获取子问题的解然后拿来计算自身的解，n 个台阶的问题因为存在两个分支场景，所以会出现部分解被重复计算的过程
- 防止重复计算比较简单，可以使用 Map 映射保存已经计算过的解的结果，当 Map 中存在解时，不再次进行计算而是直接取用解。

¶递归代码改写为非递归代码

在第一个电影院的场景中，考虑将递归改造成非递归的代码


int f(int n){
    int ret = 1;
    for(int i=2;i<=n;++i){
        ret=ret+1；
    }
    return ret;
}

以 n 作为输入循环累加

¶递归问题–排列组合：

角谷定理:输入一个自然数，若是偶数则除2，若是奇数则乘3+1,经过有限次的运算之后，会得出结果1，运算次数是多少？

分析问题：

这个问题的终止条件数字为1的时候，输出就是它本身，递归结束
当数字是偶数(num%2 == 0) ，num =num/2 ；当数字是奇数(num%2 !=0)，num=num*3 +1；
代码实现:


public static int natureNumCount(int num, int count) {

    //递归退出条件
    if (num == 1) {
        return count;
    }
    //判断分支条件
    if (num % 2 == 0) {
        num = num / 2;
    } else {
        num = num * 3 + 1;
    }
    count++;
    return natureNumCount(num, count);
}

这个问题比较简单，而且符合我们思维习惯，所以好解

电话号码的数字对应着字符组合，例如 2 对应着 ABC； 7 对应着 PQRS；数字串 27 对应的字符组合有 3*4 =12 种，输入 3-11 位长度的电话号码，输出所有可能组合和组合数:

分析问题

将这个问题分解，每个数字都可以转换成对应的字符数组，每次只取一组进行组合然后作为和下一组组合的结果传递下去
直到所有的字符数组都比较完毕，输出结果
代码:


public static List<String> numStr(String[] numbers,int start,ArrayList<String> result){

    if(start >= numbers.length){
        System.out.println("共有"+result.size()+"种排列方法！");
        return result;
    }
    // 数字按键对应的字符串
    String[] numKeyStr = {"","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};
    //每次只取一组
    int firstIndex = Integer.valueOf(numbers[start]);
    while(firstIndex == 0 || firstIndex ==1){
        firstIndex = Integer.valueOf(numbers[++start]);
    }

    String[] strs = numKeyStr[firstIndex].split("");
    if(result.size()==0){
        result.addAll(Arrays.asList(strs));
        return numStr(numbers,start+1,result);
    }else{
        ArrayList<String> list = new ArrayList<>();
        for(String arrStr:strs){
            for(String resStr : result){
                list.add(resStr+arrStr);
            }
        }
        return numStr(numbers,start+1,list);
    }
    
}

这个实现没有考虑代码的可优化，虽然求出了解，但是感觉传递的参数有点多，如果可以将数组已经被组合的部分剔除，就不需要传递start参数标记此次起始下标

任意字符串的随机排序组合结果输出:给定字符串abc，输出排序组合有abc,acb,bac,bca,cba,cab六种，给出算法
1. 问题分析
  1. 先将问题划分，可以看作是求解任意一个字符开头，与剩余字符的组合
  2. 剩余字符的组合也是一样的求解思路
  3. 代码:
  4. 1
    //TODO 没实现出来