递归是一种编程技术,其中函数重复调用自身直到满足终止条件。使用递归的一些例子是斐波那契数列、阶乘等的计算。但它们的问题是,在递归树中,已经解决的子问题可能会再次被解决,这会增加开销。 记忆是一种记录中间结果的技术,可以用来避免重复计算并加快程序速度。它可用于优化使用递归的程序。在 Python 中,可以借助函数装饰器来完成记忆。 让我们以计算数字的阶乘为例。下面的简单程序使用递归来解决问题:
# Simple recursive program to find factorial def facto(num): if num == 1: return 1 else: return num * facto(num-1) print(facto(5)) print(facto(5)) # again performing same calculation
输出
120 120
上面的程序可以通过使用装饰器进行记忆来优化。
# Factorial program with memoization using # decorators. # A decorator function for function 'f' passed # as parameter memory = {} def memoize_factorial(f): # This inner function has access to memory # and 'f' def inner(num): if num not in memory: memory[num] = f(num) print('result saved in memory') else: print('returning result from saved memory') return memory[num] return inner @memoize_factorial def facto(num): if num == 1: return 1 else: return num * facto(num-1) print(facto(5)) print(facto(5)) # directly coming from saved memory
result saved in memory result saved in memory result saved in memory result saved in memory result saved in memory 120 returning result from saved memory 120
说明: 1.定义了一个名为memoize_factoria l的函数。它的主要目的是将中间结果存储在称为内存的变量中。 2. 第二个函数facto是计算阶乘的函数。它已被装饰器(函数 memoize_factorial)注释。由于闭包的概念,事实可以访问内存变量。注释相当于写作,
facto = memoize_factorial(facto)
\3. 当facto(5)被调用时,除了存储中间结果之外,还会进行递归操作。每次需要进行计算时,都会检查结果是否在内存中可用。如果是,则使用它,否则,计算该值并将其存储在内存中。 \4. 我们可以验证memoization确实有效
原文链接:codingdict.net