### Python 实现递推法和递归法解决15阶楼梯问题 #### 递推法代码示例 以下是基于递推法的解决方案，通过迭代计算每一层楼梯的可能性： ```python def climb_stairs_iterative(n): # 定义前三个台阶的结果作为初始条件 if n == 1: return 1 # 只有一种方式到达第1级台阶 elif n == 2: return 2 # 有两种方式到达第2级台阶 elif n == 3: return 4 # 有四种方式到达第3级台阶 # 初始化前三级台阶的数量 step_1 = 1 # 到达第1级台阶的方式数 step_2 = 2 # 到达第2级台阶的方式数 step_3 = 4 # 到达第3级台阶的方式数 # 使用循环逐步计算到第n级台阶的方法数量 for i in range(4, n + 1): current_step = step_1 + step_2 + step_3 # 当前台阶等于之前三步之和 step_1 = step_2 # 更新step_1为之前的step_2 step_2 = step_3 # 更新step_2为之前的step_3 step_3 = current_step # 更新step_3为当前台阶 return step_3 # 返回最终结果 # 调用函数并打印结果 result_iterative = climb_stairs_iterative(15) print(f"使用递推法计算15阶楼梯的方法总数：{result_iterative}") ``` 此代码实现了从低到高的逐层累加过程[^1]。 --- #### 递归法代码示例 下面是利用递归方法解决问题的代码，同时加入了缓存机制以优化性能： ```python import functools @functools.lru_cache(maxsize=None) # 缓存中间结果，减少重复计算 def climb_stairs_recursive(n): # 基础情况处理 if n == 1: return 1 # 第1级台阶只有一种走法 elif n == 2: return 2 # 第2级台阶有两种走法 elif n == 3: return 4 # 第3级台阶有四种走法 # 对于更高的台阶，应用递归关系式 f(n) = f(n-1) + f(n-2) + f(n-3) return climb_stairs_recursive(n - 1) + \ climb_stairs_recursive(n - 2) + \ climb_stairs_recursive(n - 3) # 调用函数并打印结果 result_recursive = climb_stairs_recursive(15) print(f"使用递归法计算15阶楼梯的方法总数：{result_recursive}") ``` 该递归算法的核心在于定义基础情形以及状态转移方程，并借助`lru_cache`提升效率[^3]。 --- ### 结果对比 两种方法均能有效解决给定问题。递推法的时间复杂度较低，适合大规模输入；而递归法则更直观易懂，在加入缓存后也能高效运行。 ---