递归梳理

如何设计和使用递归

Posted by Haiming on March 31, 2020

递归算是一个困扰我很久的问题,之前觉得总是转不过来弯,今天试着详细的梳理一下,将这个地方搞透。

参照:https://chenqx.github.io/2014/09/29/Algorithm-Recursive-Programming/

1. 概念

递归算法,其实质是将问题分解成规模缩小的同类问题的子问题,然后递归的调用自身来解决问题。

递归算法的特点有:

  1. 在方法里面调用自身
  2. 在使用递归策略的时候,必须有一个明确的递归结束条件,称为递归出口
  3. 递归算法解决问题的效率较低,而且在调用的过程之中,每一层的返回点,局部变量等等都开辟了栈来存储,如果其递归的过程比较多,那么容易造成栈溢出问题,所以一般要小心使用递归算法来解决问题。

递归算法的要求有:

  1. 每次调用在规模上面都有所缩小,通常是减半
  2. 相邻两次重复之间有紧密联系。通常前一次的输出就是后一次的输入
  3. 在问题的规模极小,可以作为退出条件时直接给出解答,而不再做递归调用。

2. 以计算阶乘为例演示递归算法的使用

由于阶乘具有:对某个数的阶乘=这个数*比其小一个数的阶乘,所以一开始我们可以这样编写程序:

Integer factorial(Integer n){
  return factorial(n-1)*n;
}

但是这种表示方式,有一点是缺失的:没法退出。那么程序会跑到天荒地老。按照之前我们提到的,应该在规模足够小的时候直接退出,所以最后应该是这样的:

    Integer factorial(Integer n) {
        if (n == 1) {
            return 1;
        } else {
            return factorial(n - 1);
        }
    }

此处我忽略了一些与递归无关的因素,比如范围的校验等等。但是可以看出递归算法的实质并不难:一个退出条件,一个分解问题。

之前的博文之中有提到二叉树的遍历,树是一种天然的适合递归算法的结构:每一个节点下面都是一棵规模更小的树,可以做到天然的分解问题。

3. 递归程序的基本步骤

  1. 初始化算法:向函数传递其启动所需的参数
  2. 检查是否符合返回条件。满足直接返回
  3. 使用更小的子问题界定答案
  4. 对子问题进行计算
  5. 将结果,通常是返回值,合并进入答案的表达式
  6. 返回结果

4. 使用归纳定义

有的时候,使用归纳程序很难获得子问题,但是使用归纳定义的(indectively defined) 数据集,可以使得子问题的获得更简单。归纳定义的数据集是根据自身定义的数据结构——这就叫做归纳定义(inductive defination)。

比如链表,链表之中的一个结构体是两部分组成的:其所持有的数据,还有指向另一个节点对象(或者是NULL,结束链表)的指针。因为节点结构体的内部包含一个指向节点结构体的指针,所以称为是归纳定义的。

使用归纳数据编写递归过程和递归程序非常类似,链表的定义也包含一个基线条件,与我们刚才讲的退出条件类似:此处是NULL指针。因为NULL指针会结束一个链表,所以我们也可以使用NULL指针作为基于链表的递归程序的结束条件。

5. 使用链表求和作为归纳定义的使用示例

假设我们有一个数字链表,并且想要求其中所有数字的和。那么有下面的步骤:

  1. 初始化算法:将要处理的第一个节点作为初始值,作为参数传递给函数
  2. 检查退出条件:程序需要确认检查当前节点是否为NULL,如果是的话就退出链表
  3. 将问题分解为更小的问题:变成当前节点的值加上除去此节点之后的链表求和。

此处连带Node定义的代码如下:

    class Node {
        Integer value;
        Node next;
    }

    Integer sumAllLinkedList(Node start) {
        if (start == null) {
            return 0;
        }
        return start.value + sumAllLinkedList(start.next);
    }