论坛 › Python交流 › 使用装饰器计算递归函数运行时间的一个问题

YnZon 发表于 2023-6-26 19:27:17

使用装饰器计算递归函数运行时间的一个问题

问题来源：python最新版中的递归课后作业中，要求分别计算普通递归、尾递归和迭代方式相应的解决时间。本人尝试使用之前使用的装饰器知识去解决，代码如下：
import time
def timee(func): #装饰器函数，用于计算函数运行时间
    def inner(n):
      t1 = time.time()
      func(n)
      t2 = time.time()
      print(f"耗时：{t2-t1}")
    return inner

@timee
def fibRecur(n): #待计算运行时间的斐波拉契函数（普通递归算法实现）
   if n == 1 or n == 2:
         return 1
   else:
         return fibRecur(n-1) + fibRecur(n-2)
fibRecur(12) #12为计算斐波拉契数列第12项的结果

运行结果：
耗时：0.0
耗时：0.0
Traceback (most recent call last):
File "F:\Programs\Python\HomeWork\fibtime.py", line 16, in <module>
    fibRecur(12)
File "F:\Programs\Python\HomeWork\fibtime.py", line 5, in inner
    func(n)
File "F:\Programs\Python\HomeWork\fibtime.py", line 15, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
File "F:\Programs\Python\HomeWork\fibtime.py", line 5, in inner
    func(n)
File "F:\Programs\Python\HomeWork\fibtime.py", line 15, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
File "F:\Programs\Python\HomeWork\fibtime.py", line 5, in inner
    func(n)
File "F:\Programs\Python\HomeWork\fibtime.py", line 15, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
File "F:\Programs\Python\HomeWork\fibtime.py", line 5, in inner
    func(n)
File "F:\Programs\Python\HomeWork\fibtime.py", line 15, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
File "F:\Programs\Python\HomeWork\fibtime.py", line 5, in inner
    func(n)
File "F:\Programs\Python\HomeWork\fibtime.py", line 15, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
File "F:\Programs\Python\HomeWork\fibtime.py", line 5, in inner
    func(n)
File "F:\Programs\Python\HomeWork\fibtime.py", line 15, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
File "F:\Programs\Python\HomeWork\fibtime.py", line 5, in inner
    func(n)
File "F:\Programs\Python\HomeWork\fibtime.py", line 15, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
File "F:\Programs\Python\HomeWork\fibtime.py", line 5, in inner
    func(n)
File "F:\Programs\Python\HomeWork\fibtime.py", line 15, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
File "F:\Programs\Python\HomeWork\fibtime.py", line 5, in inner
    func(n)
File "F:\Programs\Python\HomeWork\fibtime.py", line 15, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
File "F:\Programs\Python\HomeWork\fibtime.py", line 5, in inner
    func(n)
File "F:\Programs\Python\HomeWork\fibtime.py", line 15, in fibRecur
    return fibRecur(n-1) + fibRecur(n-2)
TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

想请问出现上述异常的原因是什么？如何改进代码？

isdkz 发表于 2023-6-26 19:35:24

你的代码中出现这个错误是因为你在装饰器函数中没有返回 func(n) 的结果。你的装饰器函数只是计算了运行时间，然后打印了这个时间，但并没有返回原函数的计算结果。在斐波那契数列的计算过程中，你需要将每一步的结果返回给上一步以便计算，所以在这里你需要返回 func(n) 的结果。

你可以将你的装饰器函数修改如下：

import time

def timee(func): #装饰器函数，用于计算函数运行时间
    def inner(n):
      t1 = time.time()
      result = func(n) # 收集函数结果
      t2 = time.time()
      print(f"耗时：{t2-t1}")
      return result # 返回函数结果
    return inner

@timee
def fibRecur(n): #待计算运行时间的斐波拉契函数（普通递归算法实现）
   if n == 1 or n == 2:
         return 1
   else:
         return fibRecur(n-1) + fibRecur(n-2)


这样修改后，你的装饰器函数除了计算运行时间之外，还会返回原函数的计算结果，这样在斐波那契数列的计算过程中就不会出现 'NoneType' 错误了。

但这样一来，你的装饰器会对每一次递归都进行计时，而我们通常需要的是整个函数从开始到结束的运行时间，而不是每一次递归的运行时间。所以在实际使用中，可能需要进一步优化你的装饰器以实现对整个函数运行时间的计算。

sfqxx 发表于 2023-6-26 19:37:03

本帖最后由 sfqxx 于 2023-6-26 19:39 编辑

出现上述异常的原因是在装饰器函数 inner 中，你没有正确传递返回值。这导致了斐波那契递归函数的递归调用返回了 None，无法进行加法操作。

要改进代码，你需要在递归函数 fibRecur() 中使用 return 语句返回计算结果，以确保每个递归调用都返回相应的值。同时，在装饰器函数 inner 中，你需要将递归函数的返回值返回给调用者。

以下是改进后的代码示例：


import time

def timee(func):
    def inner(n):
      t1 = time.time()
      result = func(n)
      t2 = time.time()
      print(f"耗时：{t2-t1}")
      return result
    return inner

@timee
def fibRecur(n):
    if n == 1 or n == 2:
      return 1
    else:
      return fibRecur(n-1) + fibRecur(n-2)

fibRecur(12)
改进后的代码会正确计算斐波那契递归函数的运行时间，并给出正确的结果。

（无限递归）

查看完整版本: 使用装饰器计算递归函数运行时间的一个问题