递推是通过小规模结果推出大规模结果的数学思想，递归是其实现方式；需明确终止条件（如0!=1）和递推关系（如n!=n×(n-1)!），并确保参数递减以避免无限调用。
递归函数中的“递推”通常指的是从当前问题规模向更小规模问题推进的过程。在Python中使用递归函数实现递推，关键在于明确递归的两个要素：递归边界（终止条件）和递推关系（递归表达式）。
理解递推与递归的关系
递推是一种数学思想，通过已知的小规模结果推出更大规模的结果。递归是编程中实现递推的一种方式，函数调用自身来解决子问题。
例如计算阶乘：
- 递推关系：n! = n × (n-1)!
- 终止条件：0! = 1 或 1! = 1
def factorial(n):
if n == 0 or n == 1: # 终止条件
return 1
return n * factorial(n - 1) # 递推调用
正确设计递推步骤
写好递归函数的核心是清晰定义每一步如何将问题缩小。
- 确保每次递归调用都在向终止条件靠近，比如参数减小
- 避免无限递归，必须有明确的退出路径
- 递推逻辑应自然反映问题本身的结构，如斐波那契数列
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2) # 递推公式 F(n) = F(n-1) + F(n-2)
优化递推过程避免重复计算
朴素递归可能重复求解相同子问题，效率低。可通过记忆化优化。
立即学习“Python免费学习笔记（深入）”；
使用字典缓存已计算结果，提升性能。
带记忆化的递归：def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
基本上就这些。掌握递推的关键是理清问题的分解方式，再用递归自然表达出来。不复杂但容易忽略细节。
