数据结构与算法===递归

定义

递归(Recursion)是指函数的自身调用。
这个算法演变为了程序员之间的梗，所表达的意思近似于“套娃”，表示不断重复引用别人的话从而产生循环。

适用场景

这个应该很多的，像一些树的遍历；前序，中序，后序，都可以使用递归来实现。来看看下面的例子吧。

爬楼梯

题目如上，也可以去leetcode上去看看。这个是我很早之前刷过的题，下面看看代码实现

代码实现

先看看C++的吧，如下：

class Solution {
public:int climbStairs(int n) {if(n <= 3){ return n; }int f0 = 2, f1 = 3, ans = 0;for(int i = 4; i <= n; ++i) {ans = f0 + f1;f0 = f1;f1 = ans;}return ans;}
};

再看看python的实现吧，如下：

class Solution:def climbStairs(self, n: int) -> int:if n < 4:return nans = 0f2 = 2f3 = 3for i in range(4, n+1):ans = f2 + f3f2 = f3f3 = ansreturn ans

小结

这里采用了递归树的思维，为什么不是直接调用函数呢，可以看下之前讲过的算法时间复杂度，里边有很多重复的操作，就采用了递归的思维，然后做了下调整，用一些临时变量来存储，减少了内部调用。下边给个递归的模板吧，如下：

# 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, p1, ...)     # reverse the current level status if needed

这么看还是很清晰的。