递归是指函数内调用自身函数

  • 递归的两个条件：
    • 基线条件（Base case）
    • 递归条件（recursive case）
  • 所有函数的调用都进入调用栈（recall stack，压入和弹出）
  • 调用栈可能很大，这将占用大量内存
  • 递归过程记录的状态信息在调用栈中（同普通的函数嵌套函数调用），即每次递归过程，在没有返回状态信息时，是没有结束的该层递归的

1. 实现递归的两个步骤

  1. 找出base case，即当前输入的最简单规模的例子
  2. 找到recursive case
    • 使整个输入规模减少，向base case方向
    • 保证减小规模后仍然可执行递归函数的操作（快排对数组缩小后，继续进行快排）

2. 队列方法和递归方法

广度优先遍历（BFS）-> 队列 while
深度优先遍历（DFS）-> 递归（栈）

举例：从盒子中找钥匙，其中可能盒子嵌套盒子

队列方法

  • 创建盒子堆
  • if 盒子堆不空：从中取出一个盒子
  • if 这个盒子是钥匙：return；else 获取一个新盒子，将其放入盒子堆中
  • 回到第二步，再次取一个盒子

递归方法

  • 详细检查盒子中的每样东西
  • if 该物品是盒子：返回第一步，递归操作
  • else 是钥匙，return

3. 调用栈

栈是LIFO（last in first out）结构

在计算机内部使用调用栈，例如，在一个函数体Func1内部再调用另一个函数Func2

  • 此时，调用栈就会先将Func1和其参数压入栈
  • 之后，再将Func2和参数压入栈
  • Func2执行完毕后，先出栈，随后func1出栈
  • 最后，结束调用

递归过程，同样使用调用栈，规律同上