递推

简介与概述

递推算法是信息学奥赛（OI）中一种基础且重要的算法思想。它通过已知的初始条件，利用特定的递推关系，逐步推导出后续的数据或结果。递推算法的核心在于找到问题中数据之间的内在联系，将一个复杂的问题分解为一系列简单的步骤，通过不断重复这些步骤来得到最终的解。其功能在于能够高效地解决一些具有规律性和重复性的问题，避免了重复计算，提高了算法的效率。

适用场景

递推算法适用于多种场景，常见的有：

1. 数列问题：当数列中的每一项都可以由前面的若干项通过某种固定的规则计算得出时，递推算法可以轻松解决。例如斐波那契数列，每一项都是前两项之和。
2. 计数问题：在一些需要统计方案数、排列组合数等的问题中，递推算法可以通过分析问题的特点，找出递推关系，从而计算出结果。比如走楼梯问题，计算到达第 n 级楼梯的不同走法数量。
3. 动态规划基础：递推是动态规划的基础，许多动态规划问题可以通过递推的方式来解决。在处理具有最优子结构和重叠子问题的问题时，递推算法可以为动态规划提供思路。

分类

递推算法主要分为顺推和逆推两种类型：

1. 顺推：从已知的初始条件出发，按照一定的递推规则，逐步计算出后续的结果。例如，对于斐波那契数列，已知前两项 F(1) = 1，F(2) = 1，通过递推公式 F(n) = F(n - 1) + F(n - 2)（n > 2），可以依次计算出 F(3)，F(4)，...，F(n)。
2. 逆推：从问题的目标状态出发，通过逆向的递推关系，逐步推导出初始状态。比如在一些求解最优解的问题中，我们可以从最终的最优状态反推到初始状态，从而找到最优解的路径。

递推算法的关键在于找到合适的递推关系和初始条件。递推关系是指数据之间的数学联系，它决定了如何从已知的项推导出未知的项；初始条件则是递推的起点，没有正确的初始条件，递推过程将无法开始。

递推算法经典例题及分析

例题1：台阶问题

分析过程：

1. 状态定义：设 f[i] 表示走到第 i 级台阶的走法数。
2. 递推关系：
   • 走到第 i 级台阶的最后一步可能是走1级（从 i-1 级上来），也可能是走2级（从 i-2 级上来）。
   • 因此 f[i] = f[i-1] + f[i-2]。
3. 初始条件：
   • f[1] = 1（只有1种走法：走1级），f[2] = 2（1+1 或 2）。
4. 递推方向：从 i=3 到 i=n，依次计算每个 f[i]。
5. 时间复杂度：O(n)，线性递推。

例题2：汉诺塔问题

分析过程：

1. 状态定义：设 f[n] 表示移动n个盘子的最少次数。
2. 递推关系：
   • 移动n个盘子时，需先将前 n-1 个盘子从A移到B（需 f[n-1] 次），
   • 再将第n个盘子从A移到C（1次），
   • 最后将前 n-1 个盘子从B移到C（需 f[n-1] 次）。
   • 因此 f[n] = 2 * f[n-1] + 1。
3. 初始条件：f[1] = 1（直接移动1个盘子）。
4. 递推方向：从 n=2 到 n，逐层计算。
5. 数学本质：等比数列，通项公式 f[n] = 2^n - 1，但递推法更直观。

例题3：平面分割问题

分析过程：

1. 状态定义：设 f[n] 表示n条直线最多分割的区域数。
2. 递推关系：
   • 第n条直线与前 n-1 条直线最多有 n-1 个交点，这些交点将第n条直线分成 n 段，
   • 每段对应新增1个区域，因此新增区域数为 n。
   • 故 f[n] = f[n-1] + n。
3. 初始条件：f[0] = 1（0条直线时，平面是1个区域）。
4. 递推方向：从 n=1 到 n，每次累加当前直线新增的区域数。
5. 通项公式：通过求和可得 f[n] = n*(n+1)/2 + 1，但递推法是推导基础。

例题4：错位排列问题

分析过程：

1. 状态定义：设 f[n] 表示n个元素的错位排列数。
2. 递推关系：
   • 考虑第n个元素放在第k个位置（k=1~n-1），分两种情况：
     • 情况1：第k个元素放在第n个位置，此时剩下 n-2 个元素需错位排列，有 f[n-2] 种。
     • 情况2：第k个元素不放在第n个位置，此时等价于将前 n-1 个元素错位排列（第k个元素不能放在第n位，相当于新的错位问题），有 f[n-1] 种。
   • 因此 f[n] = (n-1) * (f[n-1] + f[n-2])。
3. 初始条件：f[1] = 0（1个元素无法错位），f[2] = 1（交换两个元素）。
4. 递推方向：从 n=3 到 n，利用前两项计算当前项。

总结

递推的一般步骤

递推算法的核心是通过状态定义和递推关系，将复杂问题分解为子问题的解。关键步骤：

1. 定义状态：明确 f[i] 或 f[i][j] 表示什么。
2. 推导递推式：分析当前状态如何由之前的状态转移而来。
3. 设定初始条件：确保最小子问题有已知解。
4. 确定递推顺序：从小到大或从底向上，避免依赖未计算的状态。
   通过以上例题可看出，递推广泛应用于计数、最优化、几何等问题，是OI竞赛中基础且重要的算法思想。

递推与动态规划的关系

乍一看，好像递推和动态规划完全一样没什么区别，但是实际上是两种不同的东西。

首先需要明确一点，递推与动态规划不是某种具体的算法，而是解决问题的手段。

递推解决的是数学上的函数的值的推导问题，即我们知道了某个特定函数前面的值，通过递推的手段想得到下一位的值，是函数值与函数值之间的转移。

递推问题的核心是递推公式。

而动态规划解决的是更加复杂的问题，思想类似分治，将一个复杂问题分解成若干子问题进行求解，是状态与状态之间的转移。

动态规划的核心是状态转移方程。

练习：