01 递归

递归的基本概念

​ 递归作为一种算法结构是指在函数的定义中调用函数自身，一个经典的例子就是用递归函数求阶乘

int factorial(int n){
    if(n == 0){
        return 1;
    }else{
        return n * factorial(n-1);
    }
}

​ 从上例可以看出递归的基本思想就是把规模大的问题拆解为规模小的相同的子问题来解决，且在这个不断拆解为更小问题的过程中有一个临界点，即问题拆解的终止条件。当达到临界点时，从被拆解的最小问题的解开始对战栈式地返回答案，累积得到原问题的解。

​ 所以在递归函数实现时，包含了两部分，一个是递归主体，另一个是终止条件：

• 递归主体：因为大问题和小问题是一样的问题，因此大问题的解决方法和小问题的解决方法也是同一个方法这就是递归主体。一般情况下，递归主体就是一个递推公式，该递推公式来自将大问题拆解为小问题的规律。
• 终止条件：这种函数调用它自身的情况，必须有明确的终止条件，否则就会导致无限递归。而终止条件就是问题的平凡解，即问题的最简单情况。

​ 总的来说，递归问题的求解关键在于找出问题转化的递推公式和终止条件。

递归的作用：

• 替代多重循环
• 用于解决本来就是用递归形式定义的问题
• 将问题分解为规模更小的子问题进行求解

面试题 08.06. 汉诺塔问题 (opens new window)

​ 有一个梵塔，塔内有三个座 A 、 B 、 C，A 座上有 N 个盘子，盘子大小不等，大的在下，小的在上。 现在想把这 N 个盘子从 A 座移到 C 座，但每次只能允许移动一个盘子，并且在移动过程中， 3 个座上的盘子始终保持大盘在下，小盘在上 。 在移动过程中可以利用 B 座。

输入三个数组，输出一个数组表示移动结果

 输入：A = [2, 1, 0], B = [], C = []
 输出：C = [2, 1, 0]

解析：

​ 汉诺塔问题是经典的递归问题，本题的初始情况：所有的圆盘按大小顺序堆放在 A 上，最大的在底部；移动规则：允许圆盘一次从一个木桩移动到另一个，大盘不能放在小盘的上面；要达到的最终目标：以最少的移动次数将所有圆盘从 A 转移到 C。

​ 分析本题的递推规律：先将 n-1 个盘子从 A 移动到中转 B，再将最大的一个盘子移动到 C，然后将 n-1 个盘子从 B 移动到 C。即将规模为 N 的大问题，转化为规模为 N-1 的子问题，直到最终转化为 1 的平凡解。

​ 递归的终止条件为：A 只有一个盘子，直接将它从 A 移动到 C

class Solution {
public:
    void rec(int n, vector<int>& A, vector<int>& B, vector<int>& C){
        // 终止条件
        if(n==1){
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        // 递推公式
        rec(n-1,A,C,B);
        C.push_back(A.back());
        A.pop_back();
        rec(n-1,B,A,C);
    }

    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        rec(A.size(),A,B,C);
    }
};

509 斐波那契数 (opens new window)

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

现给定 n，请计算 F(n)

输入一个整数，输出一个整数表示斐波那契数

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

解析：

​ 斐波那契数列（Fibonacci sequence），又称黄金分割数列，0,1,1,2,3,5,8,13,21,34,……，其递归公式为:

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

​ 更加直观的理解斐波那契数列如下图所示：

​ 我们可以直接根据斐波那契数列的递推公式得出递归主体和终止条件：

• 终止条件：F(0) = 0，F(1) = 1
• 递归主体：F(n) = F(n - 1) + F(n - 2)

class Solution {
public:
    int fib(int n) {
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        return fib(n-1)+fib(n-2);
    }
};

70 爬楼梯 (opens new window)

某人正在爬楼梯，需要 n 阶才能到达楼顶。每次可以爬 1 或 2 个台阶，请计算有多少种不同的方法可以爬到楼顶。

输入一个整数 n，输出一个整数表示爬到楼顶的方法数。

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

解析：

​ 本题可以转化为斐波那契数列问题。

​ 首先我们考虑爬楼梯的终止条件。本题可以有多种终止条件，n<0 时没有台阶可走，n=0 时需要返回上一步移动的结果；n=1 时只剩下一种移动方式；n=2 时有 1,1 和 2 两种移动方式。所以本题的终止条件可以为如下三种情况：

• n < 0, return 0; n = 0, return 1;
• n = 0, return 1; n = 1, return 1;
• n = 1, return 1; n = 2, return 2;

​ 接着我们考虑爬楼梯的递推规律：先考虑规模为 N 的大问题，N 阶楼梯的走法等于第一次走一步和走两步之后规模为 N-1 和 N-2 两个子问题的走法之和。即 ( n 阶楼梯的走法) = (走一级台阶之后，n-1 级台阶的走法) + (走两级台阶之后，n-2 级台阶的走法)，形式化表达 f(n) = f(n-1) + f(n-2)。

class Solution {
public:
    int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }

        return climbStairs(n-1) + climbStairs(n-2);
    }
};

​ 需要注意的是，LeetCode 中本题不能直接使用递归求解，会超出时间限制，使用动态规划的方式求解。

class Solution {
public:
    int climbStairs(int n) {
        // 初始条件 只走一步
        int r = 1, s = 0, t = 0;
        for(int i=1;i<=n;++i){
            s = t;
            t = r;
            r = s + t;
        }
        return r;
    }
};