递推与递归的区别及递推题通用解法详解

1. 从“sdut-程序设计基础Ⅱ-递推”这个标题里我先看到了什么先说点实际的。做过程序设计基础课的助教或者刷过OJ题库的人看到这类标题基本不用点进去就知道它在考什么——递推。这个标题典型的OJ课程题命名风格学校缩写加课程名加题目类型规规矩矩。但真正值得琢磨的不是标题本身而是藏在“递推”两个字背后的一整套思维方式和代码套路。程序设计基础Ⅱ这门课通常排在C语言或Java语法基础之后学生已经会写循环、数组、函数了。这个阶段突然上一道叫“递推”的题很多人第一反应是去翻递归结果一写就超时一写就栈溢出最后卡到怀疑人生。我见过太多学生在这道题上反复提交十几次错因不是语法而是根本没有把“递推”和“递归”从根上区分开。所以这篇文章我不打算只给一份AC代码就收工。我会把递推这个主题拆开讲透它和递归到底什么关系递推式的构造逻辑是什么边界条件到底怎么处理以及当你在OJ上反复提交不过的时候应该按什么顺序排查问题。课程名里那个“Ⅱ”也别忽视它说明这是第二学期的内容难度会比程序设计基础Ⅰ明显上台阶递推就是第一道真正需要“设计思路”的题不再是照着语法抄。如果你正卡在递推题上或者想彻底搞懂这一类题目的通用解法这篇文章值得你花二十分钟看完。我尽量用菜鸟也能听懂的话讲但也不会回避必要的严谨性。2. 递推与递归的分界线两者只在边界条件上一致实现策略完全不同2.1 一个入门例子讲清楚递推和递归的差异很多教科书一上来就讲斐波那契数列F(1)1F(2)1F(n)F(n-1)F(n-2)n≥3。然后学生就开始写递归int fib(int n) { if (n 1 || n 2) return 1; return fib(n - 1) fib(n - 2); }代码三行搞定样例也能过感觉良好。但一旦n给到40以上程序开始卡得像老式电脑开机n到50基本跑不动。原因就是递归在重复计算fib(6)要算fib(5)和fib(4)fib(5)又要算fib(4)和fib(3)这中间的fib(4)被反复展开至少两次。整个函数调用树呈指数爆炸时间复杂度O(2^n)n稍微大一点就彻底崩溃。递推的做法则完全不同。它不“回头”调用而是从已知的初始条件出发一步一步往后推int fib(int n) { int a 1, b 1, c; if (n 2) return 1; for (int i 3; i n; i) { c a b; a b; b c; } return b; }这里只有一层循环每个结果只用一次时间复杂度O(n)。同样算fib(100)递归连算都算不出来递推瞬间出结果。这就是“递推”的核心优势它把一个大问题拆成一步步小问题每一步都站在上一步的肩膀上而不是反复回溯。注意我这里只讨论时间复杂度递归也有用武之地比如树的遍历、回溯搜索这类天然分层的场景但纯数值序列递推题这门课的题目基本都是这种递推是绝对首选。2.2 为什么“第三项等于前两项之和”能成为通用母题热搜词里出现的“第三项等于前两项之和的递推公式”本质上就是斐波那契数列的一般化描述。但很多初学者没意识到这句话描述的是一种极为通用的递推结构当前状态由前面若干个确定状态直接推导而来。把这个结构抽象出来就是你看到的所有递推题的母模板状态定义f[n] 表示第 n 个元素的值或方案数 递推关系f[n] 某种由 f[n-1], f[n-2], ..., f[n-k] 组合得到的表达式 初始条件f[1], f[2], ... 必须先人工确定 循环推进for (i 初值1; i n; i) 计算 f[i]不管是爬楼梯问题f[n] f[n-1] f[n-2]铺砖问题f[n] f[n-1] f[n-2]还是单词拆分问题万变不离其宗。这个模板的价值在于它给你一个“做题入口”拿到任何递推题先别管代码怎么写先把上面四个部分列清楚列清楚了代码几乎是照着翻译。从热搜词里能看到也有人把这个话题延伸到“遗忘因子递推最小二乘法”“RLS数据校核”这些工程应用上说明递推不是考试专属的玩具。实际工程里只要一个系统的当前状态能由历史状态估计出来用的就是同一套思想。课程里学的这十几行循环本质上是在训练你建立状态转移的思维模式这点等你后续接触动态规划、状态机甚至信号处理会有更深体会。2.3 递推代码的“三段式”写法根据我带学生的经验递推题的代码实现就三句话结构极其固定定义存储开一个数组长度比题目要求的最大值再大几个防止越界。初始化手工赋值把递推式需要的前几项如f[1]、f[2]、甚至f[0]赋值。从初始项的下一位循环到目标项循环体里直接套递推关系。很多同学的代码反复出问题不是因为看不懂递推关系而是第一步和第二步没做好。比如写了int a[n];结果n在运行时才知道或者忘记给f[1]、f[2]赋值就从f[3]开始推导致拿到一个垃圾值还一脸懵。我建议你们养成一个习惯不管题目给没给初始条件先自己在纸上把n1、n2、n3的情况手算一遍再去写代码正确率能高一大截。3. 从题目到代码递推公式的推导与边界条件处理差一点就差很多3.1 拿到题目先别急着写码先做三件事很多事情差一层窗户纸。同样是递推题有人十分钟AC有人卡一小时差距往往不在编码速度而在动手写代码之前的“准备工作”。我给的准备工作就三步读题标记所有已知量题目里给出的f(1)、f(2)这类条件用一个明显的记号标出来。很多同学不是不会推是漏看了某个初始值导致后面白推半天。手算前五个数建立“数感”比如题目说f(1)1f(2)2递推关系是f(n)f(n-1)f(n-2)你先手动算出f(3)3f(4)5f(5)8。这个过程能帮你验证递推式写得对不对也方便后期用手算结果做程序输出的比对。确认数据范围决定用什么类型这是新手最容易忽略、老手最容易翻车的地方。int最高能存到大概21.47亿大约在Fibonacci的第46项左右就会溢出。long long能撑到第93项左右。如果题目n能给到10000甚至更大那基本就要结合取模了。我们看个典型题铺砖问题。有一块长为n的区域用1×2的砖去铺问有多少种铺法。拿到题第一步先想f(1)1一块砖竖着放f(2)2两块横着并排或者两块竖着并排那f(3)呢想清楚这一点递推式就能推出来。在这个基础上如果题目还要对1000000007取模那代码里就要在每次加法后做模运算而不是最后再取一次模因为中间过程的数可能已经溢出到面目全非了。3.2 边界条件的几个典型坑边界条件是递推题里最秀操作的部分多少AC率被它拉低。第一个坑n0算不算有效输入。有的题目会明确n≥1那无所谓。但如果没有明确你就得想清楚f(0)到底是什么。在铺砖问题里长度为0的区域铺法可以认为是1空方案也可以认为无定义。这直接决定你从哪儿开始初始化。第二个坑递推式的定义域。比如f(n) f(n-1) f(n-3)当n2时f(-1)没意义。所以循环得从4开始或者单独特判n1和n2。这种细节教科书不会专门讲但OJ用测试数据教做人错了就是错了。第三个坑溢出。别以为“我开了long long就万事大吉了”。有些题表面上n不大但中间运算会先乘后加比如f(n)2f(n-1)3n60时先算2f(59)就可能炸掉。我的建议是凡是递推题除非n非常小个位数否则一律用long long起步如果题目给了取模要求且n较大则在每次运算后立即取模。处理边界条件时可以画一个状态表格来辅助思路比如nf(n) 推导过程值1手工定义12手工定义13f(1)f(2)24f(2)f(3)35f(3)f(4)5这个表格别看简单它能帮你直观发现“递推关系在第几个位置开始成立、初始条件有哪些、到了哪一项出现分支”比纯在脑子里空想要靠谱得多。3.3 三段式写代码的正确姿势这里我用Java写一个通用的递推模板贴合一下热搜词里的“java程序设计基础”import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNext()) { int n sc.nextInt(); long[] f new long[n 5]; // 第1步定数组多开几个防越界 f[1] 1; // 第2步赋初值 f[2] 1; for (int i 3; i n; i) { f[i] f[i - 1] f[i - 2]; // 第3步循环递推 } System.out.println(f[n]); } } }注意这个while (sc.hasNext())——OJ的题经常是多组输入直到EOF很多新手只处理一组数据提交就WA答案错误还死活找不到原因。凡是题目没说“只有一组数据”默认都要写成多组输入。还有一种更省的写法不需要开数组因为斐波那契递推永远只用到前两项long a 1, b 1, c 1; for (int i 3; i n; i) { c a b; a b; b c; } System.out.println(c);这种写法适合“只需要最终项”的递推题。但如果题目要求输出每一阶段的值比如求前缀和那还是老老实实开数组存别打小算盘。4. 递推不是只有一种姿势一维升二维从Fibonacci到路径计数与卡特兰数4.1 二维递推的推导套路状态表格与移动方向这门课到后期递推题会开始变着花样出不上点段位还真容易被绕进去。第一个升级方向是二维递推。典型的例子从方格左上角走到右下角只能向右或向下走问有多少种走法。裸DFS深度优先搜索当然能做但n一大就跪了。递推解法则漂亮得多设dp[i][j]表示从左上角走到(i,j)的路径数。要走到(i,j)上一步只能来自左边(i,j-1)或者上边(i-1,j)所以dp[i][j] dp[i-1][j] dp[i][j-1]初始化dp[1][1] 1且第一行第一列只能横着/竖着一条线过来所以dp[i][1]1、dp[1][j]1。然后两层for循环填表for (int i 1; i n; i) { for (int j 1; j m; j) { if (i 1 || j 1) dp[i][j] 1; else dp[i][j] dp[i-1][j] dp[i][j-1]; } } printf(%lld\n, dp[n][m]);这个例子的价值在于告诉我们递推式的核心是找“上一步”在哪里。不要去看“下一步”顺着来从近到远。把状态表格画出来横轴纵轴分别代表什么标清楚填表顺序就是递推执行顺序。二维的本质仍然是“当前状态只依赖有限个已知状态”和一维没有任何思维上的鸿沟。4.2 特殊递推模型卡特兰数递推式不是只有加法如果说上面那些题是递推的普通关卡那么卡特兰数Catalan就是一道隐藏分水岭。它的经典递推式长这样C(0) 1 C(n) C(0)C(n-1) C(1)C(n-2) ... C(n-1)C(0)每个新项都是前面所有项的加权求和不单纯是加减还涉及乘法累加。它对应的场景包括n对括号的正确匹配数、n个节点的不同二叉搜索树数量、凸n边形的三角形划分方案数等。这个模型在程序设计基础Ⅱ里不一定直接出但动态规划里必然会用到。我建议学有余力的同学去手动推导一遍前五项把这项能力内化后续遇到“看起来像计数但找不着递推式”的题思路会宽很多。在实际应用场景里卡特兰数的递推长这样long[] c new long[n 1]; c[0] 1; for (int i 1; i n; i) { for (int j 0; j i; j) { c[i] c[j] * c[i - 1 - j]; } }两个循环嵌套时间复杂度O(n²)。这里的技巧是内层循环的边界是j i综合了所有二分组合。4.3 “滚动数组”与空间压缩二维递推里有人一上来就开一个int dp[1005][1005]n到1000还好n到10000就爆内存了。但实际上当递推只依赖相邻行时可以只开两行数组交替利用int dp[2][1005]; dp[0][1] 1; for (int i 1; i n; i) { for (int j 1; j m; j) { if (i 1 j 1) continue; dp[i % 2][j] dp[(i - 1) % 2][j] dp[i % 2][j - 1]; } } printf(%d\n, dp[n % 2][m]);这里的i % 2就是滚动的精髓奇数行用数组的第1行、偶数行用第0行旧数据自然被覆盖。我见过有些同学一参透这个写法就所有题都套滚动数组但其实没必要。空间够用就开完整二维数组能极大降低调参难度只有在n、m都很大、内存限制紧的情况下才考虑滚动数组。优化是好事但不加思考的优化只会徒增出错概率。5. 做题时最值钱的坑OJ评测的隐藏规则与调试方法论5.1 拿到WA答案错误后按什么顺序排查递推题的代码短出问题往往不是逻辑大崩而是细节没对齐。我建议按这个顺序排查检查数据读取方式是不是用循环读完所有组数据了检查初始化顺序有没有可能还没给f[1]、f[2]赋值就开始循环了打印前十个结果用printf/System.out.print手动打印f[1]到f[10]和自己手算的答案逐一比对。这一步能排除绝大多数逻辑性错误。检查数据精度涉及乘法或者n较大int是不是不够用。检查取模时机如果递推过程是先加后取模中间数据会不会已经溢出。这串流程走下来80%的WA问题都能自己解决。剩下的20%多半是递推式本身的构造想错了那就回到第一步重新推倒重来别在错误的路线上优化。5.2 超时TLE的判定与优化方向递推题能写出TLE通常只有一个原因用了递归。如果题目数据范围给到n1000、10000递归稳稳超时递推循环稳稳过。如果你用了递推循环还是TLE那可能是多组数据场景下没有用记忆化每组从头算到尾而测试数据的组数极大。对策是离线预处理比如先一次性算出1到10^6的所有答案存数组再对每组n直接输出f[n]复杂度从O(m*n)降到O(max_n m)。数据需要用更快的输入输出流Java的Scanner在数据量极大时确实慢换BufferedReaderPrintWriter会好不少。递推式本身有更高阶的优化空间比如斐波那契可以用矩阵快速幂做到O(log n)但程序设计基础Ⅱ一般不要求到这种程度知道即可不必死磕。我在OJ上见到最多的TLE解法长这样public static int fib(int n) { if (n 2) return 1; return fib(n - 1) fib(n - 2); }这段代码的递归调用次数会让我血压升高。这门课上但凡你写的是“先调用再返回”结构的代码大概率不是出题人想要的递推解法。5.3 评测系统的输出格式陷阱让你的AC率瞬间飙升很多学生AC率低不是算法问题是“格式强迫症”没治好。递推题在OJ上常见的坑包括要求每组答案占一行有人全挤在一行输出。错要用println或\n换行。题目说“每个结果后跟一个空格”有人多输出了一个空格多出一个空格在某些OJ上会被判Presentation Error也就是PE。解决办法是遍历输出时做“前面加空格”处理比如if (i 1) System.out.print( ); System.out.print(arr[i]);而不是每次末尾加空格。有多余的“Case #x:”前缀但题目没要求输出。这道题尤其常见大家一看到样例输出有前缀就默认所有测试都要实际上OJ只比对要求的部分。这些格式细节本身就是程序设计基础课程考核的一部分尤其在机试场景下一个大意就是一次“无效提交”。我的习惯是提交前认真读一遍题目输出描述把样例输出的空格和换行实际复制到一个文本编辑器里看不做任何脑补。5.4 一组完整的调试实例当递推结果总比预期大一点我拿之前带学生时遇到的一个真实情况举例。题目是个求和型递推式f(n) f(n-1) 2*n-1已知f(1)1。学生写了代码long[] f new long[n 1]; f[1] 1; for (int i 2; i n; i) { f[i] f[i - 1] 2 * i - 1; }手里算f(4)应该是135716但程序输出f(4)是17。她把递推式反复验证了好多遍都找不出问题。我让她打印f(1)到f(4)的中间值结果发现f(2)就变成了6而不是预期的4——问题出在2 * i - 1当i2时答案是3但她在纸上手算时写成了2*i再减1并顺手算错了优先级。这是一个很扯的失误但也很典型。通过这个例子我想说调试递推题不要只看最终答案把中间每一层的输出都和手算表逐一比对就能精准定位到出错的递推步。6. 关于测试数据与扩展练习递推能力怎么从课程题变成真本事很多同学课程结束后就把递推抛之脑后了。我不妨直接说如果你只把递推当成“OJ上一道题”那确实是浪费。事实上这门课安排的递推题目是后续算法课程中动态规划、状态压缩、矩阵快速幂、甚至图论最短路径的底层能力储备。6.1 一个管用的自测数据生成法递推题写完之后怎么确认代码绝对正确光靠样例远远不够。我的习惯是自己写一个小工具用最粗暴的方法比如DFS枚举算出小数据范围内的所有正确答案然后和递推代码的结果交叉验证。比如铺砖问题你可以先用DFS暴力算n1到15的所有答案存入数组A再用递推代码算出答案存B最后逐项比对A和B。如果它们完全一致这道题的正确性基本就稳了。这不是什么高深技巧但在OJ提交前就能过滤掉一大部分潜在错误省下大量提交等待时间。很多同学脑子里想的是“反正错了OJ会告诉我”这种心态在课程作业里混得过去在工作后的代码评审里会吃大亏。6.2 迁移动态规划递推是台阶DP是楼递推和动态规划的关系用一句不严谨但好记的话概括递推是动态规划脱离“策略选择”后的纯计算部分。你以后写DP时状态转移方程的本质就是“递推式”只不过多了决策和最优化的环节。所以现在把递推的基本功打扎实后面学DP时的心理落差会小很多。课上递推题如果你能做到三分钟写出正确代码、不出边界错、不超时那你的程序设计基础真的打牢了。我建议的扩展练习路径是斐波那契数列变体跳台阶、兔子繁殖铺砖/密铺类型状态压缩的入门二维路径计数转化为组合数学问题前缀和、后缀和的递推构造锻炼“状态设计”思维卡特兰数初步接触乘积型递推每类题做十道做完之后回头再看这道“sdut-程序设计基础Ⅱ-递推”你会觉得它只是递推世界的一扇小门。7. 我的真实体会递推是少数“提前做功课就能稳拿分”的题型最后聊点个人的实际经验。我带过的学生里递推题的得分方差极大会的人三分钟AC不会的人耗一小时也交不上一个能看的代码。但递推恰恰是所有算法题型里最容易通过“标准化流程”来稳定拿分的。因为它本质上没有太多玄学你不必像贪心那样证明正确性不必像搜索那样处理剪枝只要把递推式搞对、边界处理好、循环写对答案一定是对的。所以我在带课时从来不劝学生“多刷题”。我劝他们做三件事背模板演草纸推演手工交叉验证。这三件事做扎实递推题基本不可能失手。尤其是“用手算结果校验程序输出”这一步很多高手都嫌麻烦不做但恰恰是这一步能让你对自己代码的信心产生质的飞跃。我个人到现在做工程开发处理一些序列递推、时间序列预测的代码依然保留这套习惯状态怎么转移、初始条件怎么定、结果用简单case校准一遍。这套方法论就是从程序设计基础Ⅱ的递推题里长出来的。所以别看它只是一道课程题认真学透值回票价。