Skip to content

编码面试的递归备忘单

原文：https://www.techinterviewhandbook.org/algorithms/recursion/

简介

递归是一种解决计算问题的方法，其解决方案依赖于同一问题的较小实例的解决方案。

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

  1. 定义了一个基本情况(或多个情况),它定义了递归何时停止——否则它将永远继续下去！
  2. 将问题分解成更小的子问题，并调用递归调用

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

  • 基本情况: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)。向面试官指出这一点可能会给你加分。递归永远不会是 O(1)空间复杂度，因为涉及到堆栈，除非有尾调用优化 (TCO)。了解您选择的语言是否支持 TCO。
  • 基本案例的数量——在上面的斐波纳契例子中，注意我们的一个递归调用调用了fib(n - 2)。这表明您应该定义 2 个基本用例，以便您的代码覆盖输入范围内所有可能的函数调用。如果你的递归函数只调用了fn(n - 1)，那么只需要一个基本用例

拐角情况

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

技巧

记忆

在某些情况下，您可能正在计算先前计算的输入的结果。让我们再来看看斐波那契的例子。fib(5)调用fib(4)和fib(3)，fib(4)调用fib(3)和fib(2)。fib(3)被叫了两次！如果fib(3)的值被记忆并再次使用，这大大提高了算法的效率，并且时间复杂度变为 O(n)。

基本问题

如果你在学习这个话题，这些是需要练习的基本问题。

推荐练习题

这些是在你为题目学习并练习了基本问题后推荐练习的问题。

推荐课程

AlgoMonsterT3】

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得终身访问。 今天加入七折优惠→

寻找编码面试:编码问题的模式

设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式，而不是背答案！ 现在获得终身使用权→

掌握编码面试:数据结构+算法

这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星，21.5k 评分，135k 学生)，包含了价值 19 个小时的内容。像技术面试手册一样，它超越了编码面试，涵盖了简历，非技术面试，谈判。是一个全包！请注意，JavaScript 用于编码演示。 结账→

回到顶部