面试中需要熟知的递归

递归介绍

递归是一种解决问题的方法，它把一个问题分解成一个或多个独立的子问题。

所有递归函数都包含两部分:

• 定义一个(或多个)基本情况，也就是递归的出口，它决定了递归什么时候停止，否则递归将永远继续下去，直到程序的栈被打爆!

• 将问题分解为更小的独立子问题并递归调用，即递归关系。

最常见的递归例子是斐波那契数列。

• 递归出口：fib(0) = 0和fib(1) = 1
• 递归关系： fib(i) = fib(i - 1) + fib(i - 2)

int fib(int n) {
  if (n <= 1) {
      return n;
  }
  return fib(n - 1) + fib(n - 2);
}

面试中涉及到递归的有二分查找、归并排序、树的遍历、深度优先搜索等。

面试中要注意的事

• 一定不要忘记定义递归的出口条件。明确基本用例的数量，在上面的斐波那契数列示例中，注意我们的一个递归调用调用fib(n - 2)。这表明你应该定义两个基本用例（n=1 和 n=0的情况），以便你的代码涵盖输入范围内所有可能的函数调用。如果递归函数只调用fib(n - 1)，那么只需要定义一个基本用例。

• 排列问题，树相关的问题在面试中经常出现，你要知道如何使用递归来生成一个序列的全排列，以及如何去重，还要熟练掌握树的各种遍历的递归实现。

• 递归隐式地使用栈来实现。因此，所有递归方法都可以使用迭代的方法利用栈进行重写。需要注意递归级别太深而导致栈溢出(Python的默认限制是1000)。递归的实现一般不会有0(1)的空间复杂度，因为涉及到栈，除非有尾部调用优化(TCO)。不同的语言对尾部调用优化支持的情况也是不一样的。

递归的边界条件

实际上也就是上面提到的递归出口。

• n = 0
• n = 1
• 确保有足够的基本用例来覆盖所有可能的递归函数调用

常见的递归优化方法

在某些情况下，可能需要计算先前计算过的结果。让我们再看一下斐波那契的例子。fib(5)调用fib(4)和fib(3)， fib(4)调用fib(3)和fib(2)。其中fib(3)被调用了两次，如果记住fib(3)的值并再次使用，则大大提高了算法的效率，时间复杂度变为O(n)，这就是常用的备忘录法，在刷题中经常会遇到。