期末成绩怎么做网站,设计素材网站哪个好用,建立网站需要注册公司吗,邵阳建设银行网站是多少欢迎关注我的CSDN#xff1a;https://spike.blog.csdn.net/ 本文地址#xff1a;https://spike.blog.csdn.net/article/details/140137432 免责声明#xff1a;本文来源于个人知识与开源资料#xff0c;仅用于学术交流#xff0c;不包含任何商业技术#xff0c;欢迎相互学… 欢迎关注我的CSDNhttps://spike.blog.csdn.net/ 本文地址https://spike.blog.csdn.net/article/details/140137432 免责声明本文来源于个人知识与开源资料仅用于学术交流不包含任何商业技术欢迎相互学习不支持转载。 递归函数 是特殊的编程技术通过调用自身来解决问题。递归函数通常包含两个关键部分基线条件(Base Case) 和 递归步骤(Recursive Step)包括
递归函数(Recursive Function)递归函数是调用自身的函数。允许程序通过将问题分解为更小的、更易于管理的子问题来解决问题。递归函数通常用于解决可以自然分解为相似子问题的问题如树的遍历、排序算法如快速排序和归并排序等。基线条件(Base Case)基线条件是递归函数中用来停止递归调用的条件。没有基线条件递归将无限进行下去最终导致栈溢出错误。基线条件通常是一个或多个特定情况当满足这些条件时递归函数将返回一个不需要进一步递归调用的值。结果缓存(Memoization)结果缓存是一种优化技术用于存储递归函数的计算结果以避免重复计算相同的子问题。这在具有大量重复计算的递归算法中非常有用。通过缓存结果显著提高递归函数的性能在 Python 中使用字典结构 dict() 作为缓存。LRU 缓存装饰器(LRU Cache Decorator)LRU即 Least Recently Used是常用于缓存最近最少使用的数据的数据结构。LRU缓存装饰器可以应用于递归函数以实现自动的结果缓存和过期策略。这有助于管理内存使用提高具有大量重复调用的递归函数的性能。生成器(Generator)生成器是一种特殊的迭代器允许惰性地生成值即一次生成一个值而不是一次性生成所有值。在 Python 中生成器使用 yield 关键字实现。生成器对于处理大型数据集或实现复杂的迭代逻辑非常有用并且可以与递归结合使用以简化代码并提高效率。
运行效率排序迭代 LRU 缓存 字典缓存 普通递归
即
#!/usr/bin/env python
# -- coding: utf-8 --Copyright (c) 2024. All rights reserved.
Created by C. L. Wang on 2024/7/2
import timedef fib2(n):递归实现斐波那契数列if n 1: # 基线条件return nreturn fib2(n - 2) fib2(n - 1)memo {0: 0, 1: 1}def fib3(n):递归实现斐波那契数列使用字典缓存if n in memo:return memo[n]memo[n] fib3(n - 2) fib3(n - 1)return memo[n]from functools import lru_cachelru_cache(maxsizeNone)
def fib4(n):递归实现斐波那契数列使用lru_cache缓存if n 1: # 基线条件return nreturn fib4(n - 2) fib4(n - 1)def fib5(n):迭代实现斐波那契数列if n 0:return 0last, _next 0, 1for _ in range(1, n):last, _next _next, last _nextreturn _nextdef fib6(n):生成器输出斐波那契数列yield 0if n 0:yield 1last, _next 0, 1for _ in range(1, n):last, _next _next, last _nextyield _nextif __name__ __main__:s_time time.time()print(ffib2: {fib2(30)}, time: {(time.time() - s_time)*1000:.4f} ms)s_time time.time()print(ffib3: {fib3(30)}, time: {(time.time() - s_time)*1000:.4f} ms)s_time time.time()print(ffib4: {fib4(30)}, time: {(time.time() - s_time)*1000:.4f} ms)s_time time.time()print(ffib5: {fib5(30)}, time: {(time.time() - s_time)*1000:.4f} ms)for i in fib6(10):print(i, end )
运行输出
fib2: 832040, time: 213.8369 ms
fib3: 832040, time: 0.0222 ms
fib4: 832040, time: 0.0148 ms
fib5: 832040, time: 0.0043 ms
0 1 1 2 3 5 8 13 21 34 55
