递归算法总结

(Updated: )
数据结构与算法

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

一、如何理解递归

举例说明：去电影院看电影，自己坐下了，但是不知道自己坐的是第几排，可以问下前面的人，然后自己根据他的回答+1 就行，如果前面的人也不知道自己第几排，那就再往下问，直到问到第一排，第一排肯定知道自己是第一排，然后回复第二排，然后依次回复到你自己这里；
以上的过程就是递归，如果用 f(n) 表示自己第几排的话，那就会得到以下公式：

1
f(n) = f(n-1) + 1

递：一排一排的往前问的时候就是“递”
归：递到最小问题后，一个一个往前回复的时候，就是“归”
以上就是递归

二、递归要满足的三个条件

  1. 一个问题的解可以分为几个子问题的解

子问题就是数据规模更小的问题，比如“我在第几排”的子问题就是“我的前一排在第几排”

  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
所以就有以下代码：

1
2
3
4
5
6
7
8
9
10
11
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)

  1. f(6) = f(5) + f(4)
  2. f(5) = f(4) + f(3)

我们在计算 f(6) 的时候，先计算 f(5) 再计算 f(4) 然后求和，但是我们发现，f(4) 进行了两次计算，一次是算 f(5) 的时候，一次是算完 f(5) 和 f(4) 求和算 f(6) 的时候
如何避免？用哈希表存储一下值，以后计算先从哈希表里面取，取不到再计算