Python高阶函数实现递归剪枝优化

林见深

发布时间：2026-10-13 | 5人浏览过

原创

本文介绍如何利用Python高阶函数（装饰器）实现剪枝功能，解决递归算法中的重复计算问题。通过中间字典缓存已执行函数及参数，确保每次递归唯一性，从而优化斐波那契数列和上台阶问题的求解效率。

本文分享了使用Python高阶函数构建剪枝函数的具体代码示例，供读者参考学习。

具体案例如下：

在某些场景下，我们需要为多个函数统一添加特定功能，例如计时统计、记录日志或缓存运算结果等。

具体需求分析：

避免在每个函数内部重复编写完全相同的代码逻辑。

针对上述需求，如何解决？

可以将重复的代码逻辑抽取出来，定义为装饰器来实现。

以斐波那契数列（黄金分割数列）为例，从第3项开始，每一项等于前两项之和。

另一个案例是楼梯问题：共有10个台阶，从下往上走，每次只能迈出1到3个台阶且不能后退，问有多少种走法？

上台阶问题的逻辑整理：

每次迈出1到3个台阶，剩余台阶数为7到9个。

若迈出1个台阶，需计算剩余9个台阶的走法。

若迈出2个台阶，需计算剩余8个台阶的走法。

若迈出3个台阶，需计算剩余7个台阶的走法。

这三种情况通过递归方式实现，递归过程类似树结构，每次递归都会生成子节点函数。

上述两个问题若直接通过递归解决，会出现重复求解的情况。剔除这些重复求解的过程，在C++语言中被称为剪枝函数。

#!/usr/bin/python3
 
 
def jian_zhi(func):
  # 中间字典，判断已经是否求解过
  median = {}
   
  def wrap(*args):
    # 假如不在中间字典中，说明没有求解过，添加到字典中去，在的话，直接返回
    if args not in median:
      median[args] = func(*args)
    return median[args]
  return wrap
 
@jian_zhi
def fibonacci(n):
  if n <= 1:
    return 1
  return fibonacci(n-1) + fibonacci(n-2)
 
@jian_zhi
def climb(n, steps):
  count = 0
  # 当最后台阶为0的时候，说明最后只是走了一次
  if n == 0:
    count = 1
  # 当最后台阶不为0的时候，说明还需要走至少一次
  elif n > 0:
    # 对三种情况进行分别处理momo
    for step in steps:
      count += climb(n-step, steps)
       
  # 返回每次递归的计数
  return count
 
if __name__ == '__main__':
  print(climb(10, (1, 2, 3)))
  print(fibonacci(20))

剪枝函数的核心在于保证每次递归函数的唯一性。利用中间字典保存已执行过的函数及其参数，通过判断参数来剔除重复的函数调用。

以上就是本文的全部内容，希望对大家的学习有所帮助，也欢迎大家多多支持本站。