程序员文章、书籍推荐和程序员创业信息与资源分享平台

网站首页 > 技术文章 正文

Python基础 - 优化递归算法的两种基本思路

hfteth 2025-04-26 18:28:31 技术文章 6 ℃

由于递归存在重复计算,如果递归深度很大,会引起性能问题。

本文以斐波那契数列为例,介绍优化递归算法时间复杂度的两种基本思路:使用循环代替递归,缓存计算结果。

斐波那契数列是一个经典的数学序列,定义如下:

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) (n>=2时)

斐波那契数列的前几项是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

递归实现

Bash
def fibonacci_recursive(n: int) -> int:
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

循环实现

通过循环可以避免重复计算。

递归算法理论上都可以转换为循环,但不是所有递归算法都容易转换为循环。尾递归(递归调用是函数体中的最后一个操作)的转换相对简单,可以直接用循环替换;而非尾递归和复杂递归的转换则可能需要显式使用栈等数据结构来管理状态。

Bash
def fibonacci_iterative(n: int) -> int:
    if n <= 1:
        return n
    pre, cur = 0, 1
    for _ in range(2, n + 1):
        # 先计算=右边的结果,并赋值给临时变量,再将临时变量赋值给=左边的变量
        pre, cur = cur, pre + cur
    return cur

手动缓存计算结果

手动缓存通过一个字典或列表存储已经计算过的斐波那契数,避免重复计算。

def fibonacci_cache(n: int, cache={}) -> int:
    if n in cache:
        return cache[n]
    if n <= 1:
        result = n
    else:
        result = fibonacci_cache(n - 1, cache) + fibonacci_cache(n - 2, cache)
    cache[n] = result
    return result

自动缓存计算结果

使用Python提供的functools.lru_cache 装饰器,可以自动缓计算结果。

@lru_cache(maxsize=None)  # maxsize=None 表示不限制缓存大小
def fibonacci_lru_cache(n: int) -> int:
    if n <= 1:
        return n
    return fibonacci_lru_cache(n - 1) + fibonacci_lru_cache(n - 2)

耗时统计

def measure_time_with_log(func, *args, **kwargs):
    """
    测量函数执行时间并打印日志的通用函数。

    :param func: 要测量的函数
    :param args: 函数的位置参数
    :param kwargs: 函数的关键字参数
    :return: 函数的返回值
    """
    start_time = time.perf_counter()
    result = func(*args, **kwargs)
    end_time = time.perf_counter()
    elapsed_time = end_time - start_time
    print("'{}' takes {:.2f} milliseconds".format(func.__name__, elapsed_time * 1000))
    return result
    
if __name__ == '__main__':
    measure_time_with_log(fibonacci_recursive, 32)
    measure_time_with_log(fibonacci_iterative, 32)
    measure_time_with_log(fibonacci_cache, 32)
    measure_time_with_log(fibonacci_lru_cache, 32)

输出结果示例如下:

'fibonacci_recursive' takes 406.02 milliseconds

'fibonacci_iterative' takes 0.01 milliseconds

'fibonacci_cache' takes 0.02 milliseconds

'fibonacci_lru_cache' takes 0.01 milliseconds

最近发表
标签列表