算法基本型——递归

1. 递归

记得小时候，小伙伴总喜欢玩一个小游戏。一个男孩对另一个男孩说：我给你讲个故事。

那男孩子一听有故事讲，于是说好啊好啊。

男孩子嘴巴开始动起来：从前一座山，山上有一座庙，庙里有个老和尚给小和尚讲故事：从前一座山，山上有一座庙，庙里有个老和尚给小和尚讲故事：从前一座山，山上有一座庙。。。

那男孩子简直快被烦死了，转头就去其他地方玩了。

多年以后，想起这个事情，觉得很好笑，但是那时候的小伙伴已经玩起了递归了，人才。

2. 递归基本型

准确来说，递归并不是一种算法，只能算一种编程方法，这是一种很重要的方法，专门为分治、回溯、动态规划而服务，因此，有必要掌握递归。

归并和动态规划我们放后面讲，今天重点讲普通递归（包含分治）。

简单来说递归就是函数套娃。

复杂问题能递归，说明问题可以划分为多个相同的子问题，而相同子问题用一个函数就可以解决，这才是函数能套娃的基本前提。

使用递归解题有三步：

第一：判断原问题是否能划分为相同子问题？

第二：化动为静，确定边界是什么？

第三：化静为动，写出嵌套函数。

接下来我们以多个例题来讲解。

函数递归调用就像一个栈，我们先到栈的底部，最后再回到栈的顶部，那么在来去的过程中进行一些操作。不同的地方是，你是先操作再入栈，还是先入栈再操作。

下面是快排的实现，快排就是先操作再入栈。

class Solution {
    void quickSort(vector<int>& nums, int l, int r){
        if (l >= r) return;
      
        // 先操作
        int mark = nums[l];
        int mark_ptr = l;
        for (int i=l; i<=r; i++){
            if (nums[i] < mark){
                mark_ptr++;
                swap(nums[i], nums[mark_ptr]);
            }
        }
        swap(nums[mark_ptr], nums[l]);
      
        // 再入栈
        quickSort(nums, l, mark_ptr-1);
        quickSort(nums, mark_ptr+1, r);
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty()) return {};
        quickSort(nums, 0, nums.size()-1);
        return nums;
    }
};

而归并排序则是先入栈到栈底，再操作，最后回到栈顶。

class Solution {
    void mergeSort(vector<int>& nums, vector<int>& temp, int l, int r){
        if (l >= r) return;
        int mid = (l + r) / 2;
        // 先入栈
        mergeSort(nums, temp, l, mid);
        mergeSort(nums, temp, mid+1, r);
      
        // 再操作
        int i=l,j=mid+1; int t = 0;
        while (i<=mid && j<=r){
            if (nums[i] <= nums[j]) temp[t++] = nums[i++];
            else temp[t++] = nums[j++];
        }
        while (i <= mid) temp[t++] = nums[i++];
        while (j <= r) temp[t++] = nums[j++];
        
        for (int i=l,t=0; i<=r; i++)
            nums[i] = temp[t++];
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty()) return {};
        vector<int> temp(nums.size(), 0);
        mergeSort(nums, temp, 0, nums.size()-1);
        return nums;
    }
};

递归思想。递归思想很简单，一定是这个问题存在重复子问题，所以可以使用递归。

入栈，出栈，操作？代码自己动起来了？

递归解题一定要记住，代码是静止的，先别让它动起来。如何静止？那就是分解为子问题，子问题就动不起来了。