递归方法

大家好，欢迎来到IT知识分享网。

一、什么是递归

　　递归是指函数直接或间接调用自身的一种编程方法。调用的过程就是“递”，返回的过程就是归。基本上， 所有的递归问题都可以用递推公式来表示。 

二、递归满足的三个条件

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

2，这个问题与分解之后的子问题， 除了数据规模不同， 求解思路完全一样
3. 存在递归终止条件
把问题分解为子问题， 把子问题再分解为子子问题， 一层一层分解下去， 不能存在无限循环， 这就
需要有终止条件。

三、如何编写递归代码

写递归代码的关键就是找到如何将大问题分解为小问题的规律， 并且基于此写出递推公式， 然后再推敲终止条件， 最后将递推公式和终止条件翻译成代码。

对于递归代码， 这种试图想清楚整个递和归过程的做法， 实际上是进入了一个思维误区。 很多时候， 我们理解起来比较吃力， 主要原因就是自己给自己制

造了这种理解障碍。 那正确的思维方式应该是怎样的呢？

如果一个问题 A 可以分解为若干子问题 B、 C、 D， 你可以假设子问题 B、 C、 D 已经解决， 在此基础上思考如何解决问题 A。 而且， 你只需要思考问题

A 与子问题 B、 C、 D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题， 子子问题与子子子问题之间的关系。 屏蔽掉递归细节， 这样子理

解起来就简单多了。因此， 编写递归代码的关键是， 只要遇到递归， 我们就把它抽象成一个递推公式， 不用想一层层的调用关系， 不要试图用人脑去分解递

归的每个步骤。 

四、递归的优点和缺点

1.优点：代码表达能力强，写起来简单

2.缺点：空间复杂度高，存在堆栈溢出风险、存在过多的重复计算、过多的耗时函数调用等。

参考：极客时间《数据结构与算法之美》