当Python装饰器遇上递归函数

Python

不久前我在参加某比赛时，写了一些处理数据的代码，当时并没有采用SQL，而是用Python去实现。为了计算监测处理数据所耗费的时间，当时写了这样code：

1
2
3
4
5
import time
t_start = time.time()
func()
t_end = time.time()
print "run time %.5f" %(t_end-t_start)

这样写确实没什么问题，但是一旦使用的次数多了，会发现代码非常累赘，比如说要得到func1(),func2(),func3()三个函数的运行时间，就得写三次上面的代码。

那时我就在想，Python没有提供实现这种功能的内置函数吗？当然，因为只是一个小问题所以当时也没有去细究。直到前阵子，在写装饰器有关的代码时，想起了这件事，一拍脑袋，这不就是我要的“内置函数”嘛，有了装饰器，实现这个计时的小功能不是分分钟的事嘛。当然，后面我又碰到了难题，请往下看。

首先，我写了这么一个装饰器，用来获取函数运行的时间：

1
2
3
4
5
6
7
8
def runTime(func):
    def wrapper(*args,**kwargs):
        import time
        t1 = time.time()
        func(*args,**kwargs)
        t2 = time.time()
        print "%s run time: %.5f s" %(func.__name__,t2-t1)
    return wrapper

然后我写了个冒泡排序来测试一下：

1
2
3
4
5
6
7
8
9
10
@runTime
def bubbleSort(a):   
    length = len(a)
    for i in range(length):
        for j in range(0,length-1-i):
            if a[j] > a[j+1]:
                a[j],a[j+1]=a[j+1],a[j]

a = [5,8,6,3,7,8,5,2,8,6,4]*100
bubbleSort(a)

一切都很顺利，程序输出：

1
bubbleSort run time: 0.35800 s

我又写了一个斐波那契数列来测试：

1
2
3
4
5
6
7
8
9
10
@runTime
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

fib(10)

发现输出了很多的错误信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fib run time: 0.00000 s
fib run time: 0.00000 s

Traceback (most recent call last):
  File "H:\pythonProject\装饰器\runtime.py", line 48, in <module>
    fib(20)
  File "H:\pythonProject\装饰器\runtime.py", line 9, in wrapper
    func(*args,**kwargs)
  File "H:\pythonProject\装饰器\runtime.py", line 46, in fib
    return fib(n-1) + fib(n-2)
  File "H:\pythonProject\装饰器\runtime.py", line 9, in wrapper
    func(*args,**kwargs)

...省去若干行...

TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

为什么会出现这种错误？

深入理解了装饰器就知道，这里fib = runTime(fib) = wrapper，而fib又是一个递归函数，所以当调用fib(10)的时候，其实执行的是:

1
2
fib(10)  ->  fib(9)+fib(8)  ->  fib(8)+fib(7)+fib(7)+fib(6) ->.....
-> fib(1)+fib(0)......

那么程序首先肯定会执行一次fib(1)和fib(0)，这时候是OK的，并且由于fib是被装饰的函数，所以fib(1)和fib(0)执行后，会打印出两行：

1
2
fib run time: 0.00000 s
fib run time: 0.00000 s

这没有任何问题，但是打印完后，问题就出来了。前面说过，fib等于wrapper，而wrapper函数里没有返回值，即返回值为NoneType，那这下好玩了：

1
fib(1)+fib(0) = wrapper(1)+wrapper(0)=NoneType+NoneType

行文至此，所有问题都一目了然了吧。

所以，当你对一个递归函数做装饰的时候，不要忘了递归函数里的每一层调用，都是被装饰过的。这个时候如果你的程序没有问题，那谢天谢地。如果程序有问题，也不必慌张，对付递归函数，其实在函数外面再加个套就行了：

1
2
3
4
5
6
7
8
9
10
11
12
@runTime
def fib(n):
    def _fib(n):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            return _fib(n-1) + _fib(n-2)   
    return _fib(n)

fib(20)

这个时候仍然是fib = runTime(fib)，只不过fib不再是递归函数，_fib才是，但装不装饰已不关_fib鸟事。