求教如何正确理解递归

大咪咪长得胖 发表于 2022-01-26 10:14:37
谢谢，最主要的的确是不要把过程想的太复杂，中间往前推的时候一定要告诉自己前面已经知道结果。

是的，递归的本质就和多个for嵌套一样，都是尝试所有可能的情况，如果有满足答案的，就放入res。for循环出了范围就回退到上一个for循环，这个和递归的流程是类似的。

假设父母至少有一个懂递归，儿女才能懂。那么lz如果想懂递归，必须要最最最组先的组先猴里有一只猴懂。

所以lz懂了吗🤣

可以结合数学归纳法理解。实际应用中最重要的是找出递归关系和边界条件，找几个实际例子会帮助理解，比如著名的斐波那契数列，汉诺塔之类的

想瞭解遞歸，不如這樣想吧，
現在你有個層層牽套的俄羅斯娃娃🪆，想看到最內層的最小娃長什麼樣，就必須要一層一層打開，直到最小娃不能再被打開為止。如下圖。

你可能會問，為什麼一般來說是while loop? （並不是絕對）
-> 當你在拿到俄羅斯娃娃時，你並不知道要打開幾層牽套，才能看到最小娃，這時候while loop的無限制特性就可以幫你完成。

你又問，為什麼要在遞歸的內部加上一個return function?
-> 同理，你要如何知道什麼時候滿足條件，需要打開現在的娃來找下一個小娃？是不是要試一下能否打開，才能知道此娃是否為最小娃呢？
而這試一下的狀態就是return function上的if conditional statement。當完成後return statement會讓你進入下一層。（當然conditional statement也並一定是絕對需要）


希望這樣能讓你更理解遞歸。

递归的形象解释 https://youtu.be/qla3RXaRPCg

补充一下有用的吧。以下是别人总结的，对我帮助挺大。
When I sit down to write a recursive algorithm to solve a problem, I have found it to be helpful to go through the following thought process in order to decide how the recursive call should be structured:

• Break the problem I am trying to solve down into a problem that is one step simpler
• Assume that my function will work to solve the simpler problem — really believe it beyond any doubt
• Ask myself: Since I know I can solve the simpler problem, how would I solve the more complex problem?
  

In addition to the above thought process, you will also need to figure out two things to define an recursive function:

• What value(s) the parent recursive function should pass to its child recursive function.
• What value(s) the child recursive function should return so that it can be used by the parent recursive function.
  

cattyjean 发表于 2022-01-26 09:06:52
我也发现递归是最难的。不知道你过了leetcode explore 没。我发现里面的递归非常好。过一遍，会对递归认识更深刻。

好的我去看看！

递归特别适合一些特定的数据结构。结合数据结构去理解会让你事半功倍。

第一个例子：二叉树。二叉树本身就是一个典型的递归结构：每一棵树都能看作是一个root节点+左右两棵子树的集合。每一个节点又可以代表一颗以此节点为root的子树。二叉树的中序遍历就是我们熟知的“访问左子树 - 访问自身 - 访问又子树”。理解中序遍历的关键在于弄清楚每次递归的开端代表什么意义。在这个例子里，每一次递归的开端就代表“以中序遍历访问以自身为root的子树”，而这个操作又可以拆分成“以中序遍历访问以左孩子为root的子树”“访问自身”“以中序遍历访问以右孩子为root的子树”。左右两个子问题可以复用同样的递归逻辑，只不过稍微修改了输入。

第二个例子：汉诺塔。有A B C三个柱子，A上面有n层汉诺塔，现在需要把它转移到C上，请输出移动的步骤。例如n=3, 输出 A->C, A->B, C->B，A->C, B->A, B->C, A->C。这个题的递归代码很简单：“将从上往下数共计n-1层从A移动到B - 将底层从A移动到C - 将n-1层从B移动到C”。同样的，左右两个子问题可以复用递归逻辑，只不过稍微修改了从哪、到哪、移动多少层的输入。

要有leap of faith，相信它自己会work out。你进了电影院，乌漆嘛黑，自己随便坐下了，然后想知道自己坐在第几排。怎么办呢？问下你的前排，你的前排也不知道。一直这样问下去，直到第一排。第一排的人就是base case。第一排的人将她的数往回传，这样不断地倒腾，最后你就知道自己坐几排了。后面就是recursive case。