递归需要满足的三个条件

1.一个问题的解可以分解为几个子问题的解
何为子问题？子问题就是数据规模更小的问题。比如，前面讲的电影院的例子，你要知道，“自己在哪一排”的问题，可以分解为“前一排的人在哪一排”这样一个子
问题。
2.这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
比如电影院那个例子，你求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路，是一模一样的。
3.存在递归终止条件
把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。

如何编写递归代码

写出递推公式
找到终止条件
再将递推公式转化为代码

递归代码要警惕堆栈溢出

避免递归深度过深

递归代码要警惕重复计算

一个经典的例子：求斐波那契数列

将递归代码改造成非递归代码

递归代码要额外计算空间复杂度。
理论上来说，所有递归代码都可以转换为非递归代码。有些编程语言不支持递归。
非递归代码，效率更高。