针对递归函数的优化与Python修饰器实现

我们围绕一个数学问题来说明本文的思想，组合数C(n,i)，也就是从n个元素中任选i个，共有多少种选法。当然，这个问题有很多种求解方法，例如【最快的组合数算法之Python实现】。本文主要分析组合数的递归求解方法，也就是著名的帕斯卡公式C(n,i) = C(n-1, i) + C(n-1, i-1)，首先编写出可以运行的正确代码，然后再进行优化和改进。

import time

from functools import wraps

def f0(n, i):

'''原始版本，随着参数的增大很快就会崩溃'''

if n==i or i==0:

return 1

return f0(n-1, i) + f0(n-1, i-1)

#使用全局的字典来存储中间计算结果，避免重复计算

#并且崩溃会晚一点到来

cache1 = dict()

def f1(n,i):

if n==i or i==0:

return 1

#如果当前参数还没计算过才计算

#如果已经计算过了，就直接返回之前计算的结果

elif (n,i) not in cache1:

cache1[(n,i)] = f(n-1, i) + f(n-1,i-1)

return cache1[(n,i)]

#使用嵌套定义函数来实现同一个问题

def f2(n,i):

cache2 = dict()

def f(n,i):

if n==i or i==0:

return 1

elif (n,i) not in cache2:

cache2[(n,i)] = f(n-1, i) + f(n-1, i-1)

return cache2[(n,i)]

return f(n,i)

#定义修饰器

def cachedFunc(func):

#使用字典存储中间结果

cache = dict()

#对目标函数进行改写

@wraps(func)

def newFunc(*args):

if args not in cache:

cache[args] = func(*args)

return cache[args]

#返回修改过的新函数

return newFunc

#使用修饰器

@cachedFunc

def f3(n, i):

#使用最原始的思路编写代码即可

if n==i or i==0:

return 1

return f3(n-1, i) + f3(n-1, i-1)

#测试不同实现的运行时间

for f in (f0, f1, f2, f3):

start = time.time()

for i in range(100000):

f(15,3)

print(f.__name__, ':', time.time()-start)

运行结果为：

f0 : 19.13409447669983

f1 : 0.04300236701965332

f2 : 4.019229888916016

f3 : 0.03200173377990723

虽然运行效果显示使用修饰器的效果不错，但是大家肯定会有个疑问，是不是针对每个函数都要写一个不同的修饰器呢？实际上是不用的，一般来说，同一个修饰器函数适用于特定的一类问题，是可以重复使用的，例如下面的斐波那契数列问题就重复使用了上面定义的修饰器。

def fib1(i):

if i<2:

return 1

return fib1(i-1) + fib1(i-2)

fib2 = cachedFunc(fib1)

for f in (fib2, fib1):

start = time.time()

for i in range(1000):

f(30)

print(f.__name__, ':', time.time()-start)

运行结果为：

fib1 : 0.4820277690887451

fib1 : 426.09937143325806

太神奇了，居然相差这么多。不过好像有个问题，为啥最后这段代码两次输出的函数名都是fib1呢，第一个为啥不是2呢？这算是修饰器的小坑吧，目前还没有找到解决办法（谁要是知道的话一定要告诉我，谢谢），所以推荐使用修饰器的用法，不建议把修饰器当函数来使用。

最后需要说明的是，本文的思想只是缓解了问题，并不会彻底解决函数递归调用对递归深度的限制，随着参数的增大，一样会崩溃。