目录

递归的理解

什么是递归

方法或函数调用自身的方式称之为递归,调用成为递,返回称为归。

优缺点

  • 优点:代码简洁表达能力强。

  • 缺点:空间复杂度高,栈溢出,存在重复计算。

递归使用场景

满足以下三个条件,就可以使用递归:

  1. 问题的解可以分解为几个子问题的解,何为子问题?就是数据规模更小的问题。

  2. 问题与子问题,除了数据规模不同,求解思路完全一样。

  3. 存在递归终止条件。

如何实现

1. 编写

关键是找到如何将大问题分解为小问题的规律,写出递归公式,推敲终止条件,最后翻译成实际的代码。

2. 理解

避免思维误区:不要试图去想清楚整个递和归的过程。 那怎么想?如果问题 A 可以分解为 B、C、D 三个子问题,可以假设 B、C、D 已经解决。只需要思考问题 A 和 子问题之间的关系即可。