满足递归实现的条件
- 一个问题的解可以分解为几个子问题的解
- 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样
- 存在递归终止条件
递归实现的方法
- 写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推
公式 - 然后再推敲终止条件
- 最后将递推公式和终止条件翻译成代码
递归实例
- 上台阶的步数求解
f(n)=f(n-1)+f(n-2)
f(1) = 1;
f(2) = 2;
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}
递归的坑
- 堆栈溢出
函数调用会使用栈来保存临时变量。每调用一个函数,都会将临时变量封装
为栈帧压入内存栈,等函数执行完成返回时,才出栈。系统栈或者虚拟机栈空间一般都不大。如果
递归求解的数据规模很大,调用层次很深,一直压入栈,就会有堆栈溢出的风险。 -
重复计算
image.png - 空间复杂度比较大
递归使用场景
- 计算文件夹大小
- 快排
递归leetCode相关题
- 求指数（50 Medium https://leetcode.com/problems/powx-n/)
