递归算法总结

关于递归的理解和使用总结

一、如何理解递归

举例说明：去电影院看电影，自己坐下了，但是不知道自己坐的是第几排，可以问下前面的人，然后自己根据他的回答+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);
    }
}