关于递归的理解和使用总结
一、如何理解递归
举例说明：去电影院看电影，自己坐下了，但是不知道自己坐的是第几排，可以问下前面的人，然后自己根据他的回答+1 就行，如果前面的人也不知道自己第几排，那就再往下问，直到问到第一排，第一排肯定知道自己是第一排，然后回复第二排，然后依次回复到你自己这里； 以上的过程就是递归，如果用 f(n) 表示自己第几排的话，那就会得到以下公式：
f(n) = f(n-1) + 1递：一排一排的往前问的时候就是“递” 归：递到最小问题后，一个一个往前回复的时候，就是“归” 以上就是递归
二、递归要满足的三个条件
- 一个问题的解可以分为几个子问题的解
子问题就是数据规模更小的问题，比如“我在第几排”的子问题就是“我的前一排在第几排”
- 这个问题与分解后的子问题，除了数据规模不同，求解思路完全相同
我求解“自己在第几排”的思路和前一排求解“我在第几排”的思路完全一样
- 存在递归终止条件
比如电影院那个，不能无限制的“递”下去，所以到 f(1) 的时候，第一排的人显然知道自己在第一排
三、如何编写递归代码
递归代码最关键的就是写出递归公式、找到终止条件，然后将递归公式转化成代码 LeetCode 题解链接：https://leetcode.cn/problems/power-of-two/ 举例说明（文中举例的是青蛙跳台阶问题，这里换一道题）： 给一个整数 n，判断这个整数是否是 2 的幂次方，如果是，返回 true，如果不是，返回 false； 先找规律：f(1) = true f(2) = true f(3) = false f(4) = true f(5) = false f(6) = false 2^0 = 1 2^1 = 2 2^2 = 4 2^3 = 8 2^4 = 16 2^5 = 32 由此可得，判断 n 是不是 2 的幂次方，关键就是判断 n%2 == 0 && n/2 是不是 2 的幂次方 所以找出递归公式：f(n) = n%2 == 0 && f(n/2) 终止条件：f(1) = true 需要排除一下特殊情况 f(0) = false 所以就有以下代码：
class Solution {
public boolean isPowerOfTwo(int n) {
if (n == 0) {
return false;
}
if (n == 1) {
return true;
}
return n % 2 == 0 && isPowerOfTwo(n/2);
}
}
四、递归总结
编写递归代码的关键，就是找到大问题分解成小问题的规律，基于规律写出递推公式，再推敲终止条件，最后公式和条件翻译成代码 但是，我们遇到递归，不要去想里面到底是咋递归的，只需要想成一个公式即可，站在最高层思考
五、递归的一些问题
5.1 栈溢出
递归会有多层函数调用栈，有时候递归层数太多，会导致栈溢出 如何避免这个问题？限制递归的深度
5.2 重复计算
有一个公式：f(n) = f(n-1) + f(n-2)
- f(6) = f(5) + f(4)
- f(5) = f(4) + f(3)
我们在计算 f(6) 的时候，先计算 f(5) 再计算 f(4) 然后求和，但是我们发现，f(4) 进行了两次计算，一次是算 f(5) 的时候，一次是算完 f(5) 和 f(4) 求和算 f(6) 的时候 如何避免？用哈希表存储一下值，以后计算先从哈希表里面取，取不到再计算