递归是一种解决问题的方法，其中解决方案取决于解决相同问题的较小实例。
所有递归函数都包含两部分：
- 基本情况（或多个情况）已定义，用于停止递归 - 否则它将无限进行下去！
- 将问题分解为较小的子问题，并调用递归调用
递归最常见的例子之一是斐波那契数列。
- 基本情况：
fib(0) = 0和fib(1) = 1 - 递归关系：
fib(i) = fib(i-1) + fib(i-2)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
许多在编码面试中相关的算法大量使用递归 - 二分搜索、归并排序、树遍历、深度优先搜索等。在本文中，我们关注那些使用递归但不属于其他众所周知算法的问题。
学习资源
面试时需要注意的事项
- 总是要记得定义一个基本情况，以便你的递归会结束。
- 递归对于排列很有用，因为它生成所有组合和基于树的问答。你应该知道如何生成序列的所有排列以及如何处理重复项。
- 递归隐式地使用了堆栈。因此，所有递归方法都可以使用堆栈迭代重写。小心递归层次过深导致堆栈溢出（Python默认限制为1000）。如果你能指出这一点给面试官，可能会得到额外的分数。除非有尾调用优化（TCO），否则递归永远不会是O(1)空间复杂度。找出你选择的语言是否支持TCO。
- 基本情况的数量 - 在上面的斐波那契示例中，注意到我们的递归调用
fib(n - 2)。这表明你应该定义两个基本情况，以便代码覆盖输入范围内函数的所有可能调用。如果你的递归函数只调用fn(n - 1)，那么只需要一个基本情况。
边缘情况
n = 0n = 1- 确保你有足够的基案例来覆盖递归函数的所有可能调用
技巧
记忆化
在某些情况下，你可能正在计算之前计算的输入的结果。让我们再次看看斐波那契示例。fib(5) 调用 fib(4) 和 fib(3)，而 fib(4) 调用 fib(3) 和 fib(2)。fib(3) 被调用了两次！如果 fib(3) 的值被记忆化并再次使用，这将大大提高算法的效率，时间复杂度变为 O(n)。
基本问题
如果你正在为这个主题学习，这是你需要练习的基本问题。
推荐练习问题
在你已经为这个主题学习和练习了基本问题之后，这是推荐的练习问题。
推荐课程
import AlgorithmCourses from '../_courses/AlgorithmCourses.md'