7.2 递归算法

[giscus[bot]]

7.2 递归算法

递归算法 1. 递归简介 递归（Recursion）：指的是一种通过重复将原问题分解为同类的子问题而解决的方法。在绝大数编程语言中，可以通过在函数中再次调用函数自身的方式来实现递归。 举个简单的例子来了解一下递归算法。比如阶乘的计算方法在数学上的定义为： fact(n)={1n×fact(n−1)​n = 0n > 0​ 根据阶乘计算方法的数学定义...

https://algo.itcharge.cn/07_algorithm/07_02_recursive_algorithm/

[HongxiangLu]

5.2.3 解题思路的思路 1： 递归算法下面，递归主体少了+ 1

[lalalalalal0]

斐波那契那道题请问为什么我用字典存计算结果，最后时间复杂度反而高了。以下是我的代码：

class Solution:
    def fib(self, n: int) -> int:
        cach = {}
        def solu(n):
            if n==0:
                return 0
            elif n==1:
                return 1
            if n in cach:
                return cach[n]
            res = self.fib(n-1)+self.fib(n-2)
            if n not in cach:
                cach[n] = res
            return res
        return solu(n)