求助前辈 recursion怎么想

请位前辈们
recursion怎么才能进步
感觉自己遇到recursion就没有思路。
前辈们都是怎么想recursion的 有什么推荐学习的东西吗。

个人认为递归函数首先要考虑的是什么情况下需要退出递归，当知道了什么情况下需要退出递归之后，再考虑在当前递归层需要做哪些事情。
整体的思路是把整个过程想象成一个大树，每个节点代表一个状态，从第一层往下层迁移的时候考虑什么状态需要修改，在从下层回到上层的时候，什么状态需要恢复。

还有就是哪些状态可以保存下来，这样可以剪枝来优化时间。

用琪琪题举例的话，

1. 
   
2. class Solution {
   
3. public:
   
4.     void dfs(int n, int k, int start, vector<int>& path, vector<vector<int>>& res)
   
5.     {
   
6.         if(start > n)
   
7.         {
   
8.             if(path.size()==k) res.push_back(path);
   
9.             return;
   
10.         }
    
11.         path.push_back(start);
    
12.         dfs(n,k, start+1, path, res);
    
13.         path.pop_back();
    
14.         dfs(n,k, start+1, path, res);
    
15.     }
    
16.     vector<vector<int>> combine(int n, int k) {
    
17.         
    
18.         vector<vector<int>> res;
    
19.         vector<int> path;
    
20.         dfs(n,k,1,path,res);
    
21.         return res;
    
22.     }
    
23. };
    

复制代码

递归函数dfs，首先考虑什么情况下需要退出递归，这种情况下，start大于n的时候说明所有的数已经访问过了，所以需要退出。
第二步要考虑的是在当前递归层里要做什么，这里需要做两件事，一件事是如果把start的值考虑在这个组合中，剩下的由递归解决，第二件事是如果不把start的值考虑在这个组合中结果是什么。所以这种情况下，path需要先保存好start，做完要做的事情，然后恢复path的状态，也就是pop_back。


浅显的理解，不知道是否能帮到你。顺便求大米 ：P

递归分三步走
1，先想好退出条件，比如为空时返回什么值，index超出时返回什么值
2，内部调用一下本函数，比如LinkedList就用LinkedList.next调用自身函数，tree就是tree.left和tree.right调用函数
3，最后返回函数一开始定义的值。

不清楚楼主背景很难准确推荐，不过如果是以学习为目的，可以尝试下学习 The little schemer 这本书。如前言所说 “The goal of this book is to teach the reader to think recursively.”

有什么后续问题，欢迎提问。

最后，求加米。

想法设法把大问题分解为若干个相同的小问题，这些小问题都是同样的解法，只是数据不同。
多刷树的题目。树这个数据结构是递归定义的，因此90%的树的算法也都是递归来解的。刷熟了就对递归有感觉了。

wisdompeak2 发表于 2021-03-16 20:01:56
想法设法把大问题分解为若干个相同的小问题，这些小问题都是同样的解法，只是数据不同。
多刷树的题目。树这个数据结构是递归定义的，因此90%的树的算法也都是递归来解的。刷熟了就对递归有感觉了。

我也知道是拆解 可是怎么拆是问题
请问需要考虑call stack吗 还是宏观的思考呢。
哎 自己好难。

sukiyy 发表于 2021-3-17 12:23
我也知道是拆解 可是怎么拆是问题
请问需要考虑call stack吗 还是宏观的思考呢。
哎 自己好难。

递归是一种高屋建瓴的哲学思想。具体怎么拆那样看具体问题了。
大多数问题本身就是可以递归解决的，举个简单的例子：求一棵树所有元素的val的和，等于根节点的val+左子树所有元素的val的和+右子树所有元素的val的和，后两者就是递归调用。要把这种思想提升到一种哲学高度去体会。
另外部分稍微难一点的题，可能要设计一个稍微不同的递归问题。比如求一棵树里的最长直径。任何一条直径都有一个拐点，直径的长度就是拐点往左走到叶子的最远距离+拐点往右走到叶子的最远距离。所以此时的递归问题就是：求一个节点到叶子节点的最远距离。

twtypsj 发表于 2021-03-17 11:42:06
个人认为递归函数首先要考虑的是什么情况下需要退出递归，当知道了什么情况下需要退出递归之后，再考虑在当前递归层需要做哪些事情。
整体的思路是把整个过程想象成一个大树，每个节点代表一个状态，从第一层往下

谢谢🙏我觉得你说的这个哲学思想很有帮助 我总是想要往里面死绕。

递归就三步：
1. 如何停止
2. 如何进行下一步
3.初始状态是什么

比如 斐波那契数列

1. 如何停止 - if (n ==1 || n==2) then return 1.
2. 如何下一步 fnc(n-2) + fnc(n-1)
3. 初始状态 - fnc(初始值）

如果需要backtracking 那再加一步
4. 如何step back.

稳稳地

把你要求的内容用函数表示出来，例如cost=f(x,y)。然后看f(x,y)怎么用f(x',y')表达。最后找能求出来的边界值。

sukiyy 发表于 2021-3-16 20:23
我也知道是拆解 可是怎么拆是问题
请问需要考虑call stack吗 还是宏观的思考呢。
哎 自己好难。

不用考虑call stack，就假设递归函数已经是一个第三方实现好的函数，然后用在自己的函数里面。只不过自己的函数正好和这个“第三方函数”同名。

多写写dfs tree traversal还有dp top down的题目就可以了 这个recursion需要你灵活用的 刷题刷多了就有感觉了 先多看看答案 刷题刷多了 你自己的思维方式也会像答案的大神一样