python中的递归

阳光穿透心脏的1/2处 2022-05-17 06:25 184阅读 0赞

# python中的递归 #

**关注公众号“轻松学编程”了解更多。**  
文章更改后地址：[传送门][Link 1]  
间接或直接调用自身的函数被称为**递归函数**。

间接：
    def func():
    	otherfunc()
    
    def otherfunc():
    	func()
    
    直接：
    def func():
    	func()

递归函数必须要有**收敛条件**和**递归公式**。

### 1、递归求和 ###

''' 使用递归求和 '''
    
    def my_sum(n):
        ''' 递归求和 1+2+3+...+n :param n: int型 :return: int型 '''
        # 收敛条件
        if n == 1:
            return 1
        # 递归公式
        return n + my_sum(n-1)
    
    
    def main():
        print(my_sum(10))
    
    
    if __name__ == '__main__':
        main()

结果为：
    55

当发生函数调用时 需要做保存现场和恢复现场的工作。

保存现场和恢复现场的工作都是利用栈(stack)来实现的。

栈是一个FILO的结构 - 栈非常的快但是它很小。

python默认栈的层数为1000层，可以使用以下方法来增加层数(不推荐)

import sys
    # 比如增加层数到9999层
    sys.setrecursionlimit(9999)

这样的递归不好，因为递归使用的是栈，需要用栈来保护现场和恢复现场，很耗费资源，可以使用尾递归来解决这个问题，即不回溯，直接使用最后一次的结果作为最终的结果。

### 2、尾递归 ###

''' 使用递归求和 '''
    
    def my_sum(n,result=0):
        ''' 递归求和 1+2+3+...+n :param n: int型 :param result: int型,上一层求得的结果，第一层递归时为0 :return: int型 '''
        # 收敛条件
        if n == 1:
            return result +1
        # 递归公式
        return my_sum(n-1,result=result+n)
    
    
    def main():
        print(my_sum(10))
    
    
    if __name__ == '__main__':
        main()

结果为：
    55

### 3、递归求斐波那契数列 ###

''' 斐波那契数列： f(n) = 1 当n = 1,2时 f(n) = f(n-1) + f(n-2) 当n > 2时 比如： [1,1,2,3,5,8,13,21,34,55] '''
    
    def fibonacci(n):
        # 收敛条件
        if n <= 2:
            return 1
        # 递归公式
        return fibonacci(n-1) + fibonacci(n-2)
    
    
    def main():
        print(fibonacci(10))
    
    
    if __name__ == '__main__':
        main()

结果为：
    55

这样的递归是不好的，因为每求一层递归都要重新计算前面(n-1)层递归，开销很大，比如:

求f(9)
    要先求f(8) + f(7)
    而f(8)= f(7) + f(6)
    f(7)=f(6) + f(5)
    ...

为了节省这部分重复的开销，可以使用动态规划来解决这个问题。

### 4、动态规划实现递归 ###

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

其基本思想也是将**待求解问题分解成若干个子问题**，先求解子问题，然后从这些子问题的解得到原问题的解。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。**不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中**。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

在python中的递归，可以使用字典来代替这个表。

''' 斐波那契数列： f(n) = 1 当n = 1,2时 f(n) = f(n-1) + f(n-2) 当n > 2时 比如： [1,1,2,3,5,8,13,21,34,55] '''
    
    def fibonacci(n,temp={  }):
        # 收敛条件
        if n <= 2:
            return 1
        # 首先先从字典中取值
        try:
            return temp[n]
        except KeyError:
            # 如果字典中没有就先把值存进字典
            temp[n] = fibonacci(n-1) + fibonacci(n-2)
            return temp[n]
    
    
    def main():
        print(fibonacci(10))
    
    
    if __name__ == '__main__':
        main()

结果为：
    55

使用动态规划解决：

一个小孩爬阶梯，一次有3种走法：一次走1个阶梯，一次走2个阶梯，一次走3个阶梯，问如果有10个阶梯总共有多少中走法？

def walk(steps,temp={ }):
        if steps < 0:
            return 0
        elif steps == 0:
            return 1
        try:
            return temp[steps]
        except KeyError:
            temp[steps] = walk(steps - 1) + walk(steps - 2) + walk(steps - 3)
            return temp[steps]
    
    print(walk(10))

结果为：
    274

### 5、使用装饰器测试递归函数用时 ###

''' 斐波那契数列： f(n) = 1 当n = 1,2时 f(n) = f(n-1) + f(n-2) 当n > 2时 比如： [1,1,2,3,5,8,13,21,34,55] '''
    from functools import wraps
    import time
    
    def func_time(func):
        # 使用@wraps后可以还原原来的函数
        # 即可以使用func.__wrapped__()来去掉装饰器
        @wraps(func)
        def wrapper(*arg,**kwargs):
            # 第一层递归才输出时间
            if kwargs['level'] == 0:
                start = time.perf_counter()
                result = func(*arg,**kwargs)
                end = time.perf_counter()
                print(f'Execution Time:{end-start}s')
                return result
            else:
                return func(*arg,**kwargs)
        return wrapper
    
    @func_time
    def fibonacci(n,temp={ },*,level):
        # 收敛条件
        if n <= 2:
            return 1
        # 首先先从字典中取值
        try:
            return temp[n]
        except KeyError:
            level += 1
            # 如果字典中没有就先把值存进字典
            temp[n] = fibonacci(n-1,level=level) + fibonacci(n-2,level=level)
            return temp[n]
    
    
    def main():
        print(fibonacci(121, level=0))
        
        fib_19 = fibonacci.__wrapped__(19,level=0)
        fib_20 = fibonacci.__wrapped__(20,level=0)
    
        print(f'黄金比例:{fib_19/fib_20}')
    
    
    if __name__ == '__main__':
        main()

结果为：
    Execution Time:0.0012316425773240605s
    8670007398507948658051921
    黄金比例:0.6180339985218034

**注意1**：能用循环写的代码一定不要使用递归。

**注意2**：如果用递归也尽量使用**尾递归**(只需要递归不需要回溯)和**动态规划**。

## 后记 ##

【后记】为了让大家能够轻松学编程，我创建了一个公众号【轻松学编程】，里面有让你快速学会编程的文章，当然也有一些干货提高你的编程水平，也有一些编程项目适合做一些课程设计等课题。

也可加我微信【1257309054】，拉你进群，大家一起交流学习。  
如果文章对您有帮助，请我喝杯咖啡吧！

公众号

![公众号][20200317124808234.jpg]

![赞赏码][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xtX2lzX2Rj_size_16_color_FFFFFF_t_70]

关注我，我们一起成长~~

[Link 1]: https://blog.csdn.net/lm_is_dc/article/details/105802315
[20200317124808234.jpg]: /images/20220517/197ece5a433649caa11a4f0106437622.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xtX2lzX2Rj_size_16_color_FFFFFF_t_70]: /images/20220517/d286fd97bde74bb5a7fa214c68d5c0c3.png