递归

递归一直是搞不明白，而且越往里想越糊涂，这里借鉴别人的想法结合自己的理解，并结合力扣题目深入理解递归。

递归是在函数中存在调用自身的现象

1
2
3
4
假设我们用递归来算阶乘 f(n)

f(n) = n * f(n-1)
if n == 1: return 1
1
2
3
4
5
6
7
8
9
10
例如计算f(4)
f(5) =  5 * f(4)
     =  5 * (4 * f(3))
     =  5 * (4 * (3 * f(2)))
     =  5 * (4 * (3 * (2 * f(1))))
     =  5 * (4 * (3 * (2 * 1)))
     =  5 * (4 * (3 * 2))
     =  5 * (4 * 6)
     =  5 * 24
     =  120

递归过程就是逐步展开递推然后在回归计算的过程

递归代码最重要的两个特征：结束条件和自我调用。自我调用是在解决子问题，而结束条件定义了最简子问题的答案。

递归思维

在知乎上对递归的讨论中，有两个回答我觉得非常的形象

递归思维就是摊派任务

假设你是老板，你就把活分给各个分管副总，各个副总再把活分给自己下一级的各个部门总监，

总监再把活分给下面各个干活的经理，最后分到最基层干活的人手上，

然后等待下面的完成结果再反向一级级的向上汇报。

等你当了老板就没这个疑问了，

这里面难在事情该怎么分才是合理的，怎么保证下一级都能及时的给出结果，从而快速有效的完成总任务。

递归可以想象成查字典

你遇到一个【生词 1】，然后去查字典。

发现这个【生词 1】的解释里又碰见一个【生词 2】，接着你又去查这个【生词 2】的意思，

没想到【生词 2】里又遇到一个【生词 3】…

于是只有当你查完【最后一个】【生词 N】的时候，

你才可以依次理解【生词 N-1】，【生词 N-2】…【生词 2】【生词 1】。

斐波那契数（力扣509）

题目：

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：

输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

分析

斐波那契数是入门递归的第一步，可以画出递归树如下图所示：

斐波那契递归树

求f(5)需要知道f(4)和f(3)，直到f(1)和f(2),结果已知，可直接返回。

1
2
3
4
5
class Solution:
    def fib(self, n: int) -> int:
        if n == 0:return 0
        if n == 1:return 1
        return self.fib(n-2) + self.fib(n-1)

我们发现在计算f(4)时算了f(3)，计算f(5)时也重复算了f(3)，对计算资源消耗较大，我们可以使用备忘录，用空间换时间，计算完f(3)后，以后的f(3)都是用查表操作。表可以使用字典或者数组都行，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 使用数组做备忘录
class Solution:
    def fib(self, n: int) -> int:
        memo = [0]*(n+1)
        def dfs(n):
            if n == 0:
                memo[n] == 0
                return 0
            if n == 1:
                memo[n] == 1
                return 1
            memo[n] = dfs(n-1) + dfs(n-2)
            return memo[n]
        return dfs(n)
1
2
3
4
5
6
7
8
9
10
11
#使用字典做备忘录
class Solution:
    def fib(self, n: int) -> int:
        memo = {0:0,1:1}
        def dfs(n):
            if n in memo:
                return memo[n]
            else:
                memo[n] = dfs(n-1) + dfs(n-2)
                return memo[n]
        return dfs(n)

这是从上到下的使用递归的解法，也可从下到上，使用迭代。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def fib(self, n: int) -> int:
        if n == 0:return 0
        if n == 1:return 1
        first, second = 0, 1
        result = 0
        for i in range(n-1): 
            result = first + second
            first = second
            second = result
        return result

第 N 个泰波那契数（力扣1137）

题目

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：

输入：n = 25

输出：1389537

分析

首先使用递归解法：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def tribonacci(self, n: int) -> int:
        memo = {0:0,1:1,2:1}
		def dfs(n):
            if n in memo:
                return memo[n]
            else:
                memo[n] = dfs(n-1) + dfs(n-2) + dfs(n-3)
                return memo[n]
        return dfs(n)

同样使用带备忘录的递归

1
2
3
4
5
6
class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:return 0
        if n == 1:return 1
        if n == 2:return 1
        return self.tribonacci(n-3) + self.tribonacci(n-2) + self.tribonacci(n-1)

使用迭代的方法：

和上题思路一样，只不过变成了3数相加，循环也应该少循环一次(循环几次可以带n=3进去预演一下，本题n=3时只需循环一次，n=4需循环2次，故而range(n-2))

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:return 0
        if n == 1:return 1
        if n == 2:return 1
        first, second, third = 0, 1, 1
        for i in range(n-2): 
            result = first + second + third
            first = second
            second = third
            third = result
        return result