递归Recursion
如何理解递归?
- 函数自身调用自身
- 通过函数体来进行的循环
- 以自相似的方法重复进行的过程
计算n!
n! = 1* 2* 3* …* n
def factorial(n): if n <= 1: return 1 return n * factorial(n - 1)
啊喂，求n!用递推它不香吗…
确实，因为n!的推导路径我们已经知道了，for一遍就好了。
但如果是不太容易找到推导路径的问题呢?
比如下面的问题，一棵树，在根节点的时候，我们是不知道下边长什么样的…
递归的三个关键:
- 定义需要递归的问题（重叠子问题)——数学归纳法思维
- 确定递归边界
- 保护与还原现场
C++/Java代码模板
void recursion(int level, int param) { // terminator if (level > MAX_LEVEL) { // process result return; } // process logic in current level process(level, param); // drill down recur(level + 1, new_param); // restore the current level status }
Python代码模板
def recursion(level, param1, param2, ...): # recursion terminator if level > MAX_LEVEL: # process result return # process logic in current level process(level, data...) # drill down self.recursion(level + 1, new_param1, ...) # restore the current level status if needed
实战
78.子集
https://leetcode.cn/problems/subsets/
class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { n = nums.size(); recur(nums,0); return ans; } private: void recur(vector<int>& nums, int i){ if(i == n){ ans.push_back(chosen); return; } recur(nums, i + 1); chosen.push_back(nums[i]); recur(nums, i + 1); chosen.pop_back(); } int n; vector<int> chosen; vector<vector<int>> ans; };
77.组合
https://leetcode.cn/problems/combinations/
class Solution { public: vector<vector<int>> combine(int n, int k) { this->n = n; this->k = k; recur(1); return ans; } private: void recur(int i) { if(chosen.size() > k || chosen.size() + (n - i + 1) < k) return; if(i == n + 1){ ans.push_back(chosen); return; } recur(i + 1); chosen.push_back(i); recur(i + 1); chosen.pop_back(); } int n, k; vector<int> chosen; vector<vector<int>> ans; };
46.全排列
https://leetcode.cn/problems/permutations/
class Solution { public: vector<vector<int>> permute(vector<int>& nums) { n = nums.size(); used = vector<bool>(n, false); recur(nums, 0); return ans; } private: void recur(vector<int>& nums, int pos) { if(pos == n){ ans.push_back(a); return; } for(int i = 0; i < n; i++){ if(!used[i]){ a.push_back(nums[i]); used[i] = true; recur(nums, pos + 1); used[i] = false; a.pop_back(); } } } vector<bool> used; vector<int> a; int n; vector<vector<int>> ans; };
47.全排列 ||
https://leetcode.cn/problems/permutations-ii/
class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int> > res; do{ res.emplace_back(nums); }while(next_permutation(nums.begin(), nums.end())); return res; } };
递归基本形式总结
以上问题都是递归实现的“暴力搜索”（或者叫枚举、回溯等)
可以总结为以下三种基本形式
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
