递归算法的宏观理解：从概念到实现
递归算法的宏观理解：从概念到实现
递归算法是计算机科学中的一个重要概念，但很多人在学习时会感到头疼。本文将从递归的基本概念出发，通过对比微观和宏观两种看待递归问题的方式，深入浅出地讲解递归算法的核心思想和实现要点。
一、递归是什么
递归就是函数或过程在运行过程中直接或间接地调用自身的一种算法结构。
例子🌰：相信大家小时候都听过一个故事：从前有座山，山里有座庙，庙里有个老和尚在讲故事。讲的是，从前有座山，山里有座庙，庙里有个老和尚在讲故事。讲的是，从前有座山，山里有座庙，庙里有个老和尚在讲故事……如此循环往复，无限套娃！！
这就是递归最简单的例子了。
二、为什么要使用递归
简短来讲，就是因为有出现重复的问题和出现了重复的子问题，所以要用递归。
三、何为宏观看待递归问题
①微观看待递归问题
🌰二叉树遍历
比如二叉树的遍历，就是一个自己调用自己的过程。在后序遍历的过程中，先遍历自己的左子树，再遍历自己的右子树，再遍历自己；然后在下一个左子树的节点的时候，再遍历自己的左子树，右子树，根……这就是递归，一个最简单的一个应用，但往往这样递归下去，是很多很复杂很重复的工作的。
🌰斐波那契数列
如果你要搞懂这道题的计算原理，画出递归图。你简单算一个f（5）要先调用算出f（4）和f（3），要算出f（4）又要再调用f（3）和f（2）.......如此循环往复下去，一个一个画图计算都要画到天荒地老。
如果每次递归都画递归展开图，那肯定每次都会花费很大的时间和精力，如果遇到一个较大的数肯定不想做了。
上述就是微观理解递归。
②宏观看待递归问题
如何宏观看待递归，就是不用在意递归展开图是咋样的。把递归函数的细节展开图看成一个黑盒，不关心合盒里面具体实现、递归。只关心我要这个黑盒完成什么任务 ，足够的相信这个黑盒能够帮你完成这个任务。
有了这一思想，我们可以带入上述思想去求解。
比如在二叉树的遍历中，我们需要它先帮我们完成后序遍历。就先帮我们遍历一遍左子树，右子树以及根节点。现在我们就把这个任务交个这个函数，让它们去帮我们完成，所以我们只需要传递这个左边的根节点，和右边的根节点就可以让这个函数就能帮我们完成
所以伪代码如下：
void dfs(Listnode root){
//相信这个递归函数一定能帮我们实现
dfs(root.left);//传入树左边节点
dsf(root.right);//遍历树右边节点
print(root);//自己
}
四、如何实现好递归代码
①递归函数首先要确定头函数（确定参数）
解决这个问题的关键就在于如何理解这个重复子问题是什么需要什么。
比如说二叉树的遍历，我们需要一个根节点就可以遍历到整棵树，此时我们只需要传入一个头节点。再比如快排则是你需要给我这个需要排序的数组，和左右两边双指针即可以帮你排好序。
②确定函数体的实现⭐️⭐️⭐️
这个是看待宏观最重要的一步了
解决这个问题也很简单，只需要关注某一重复子问题的实现，把重复的问题抽象出来即可。
比如二叉树就是走左，走右，自己;把这三步抽象出来也就是dfs（root.left)、dsf(root.right)、printf(root)。
快排也就是选一个中间节点，排左，排右的过程。
③函数出口
当然递归函数的出口也很重要。如果没有出口，函数将无限的递下去，也就没有没有出口也就无法回归。
递归的出口：也就是函数走到头，无法走出头的条件。（这一步相对来讲比较简单）