@Dmaxiya
2026-01-25T09:59:15.000000Z
字数 942
阅读 46
Hello_World
比赛链接：寒假第三次培训 递归 递推
递归是算法设计里一个非常重要且基础的分析方法，一些常见的算法都需要从递归的角度入手分析。早在c语言专业课里，我们就已经接触过递归的思想（只是你当时并不一定真的掌握了）。
- 谭浩强书上有好几页的篇幅，讲解了一个经典的递归问题：汉诺塔问题。
你可能听说过：“递归的代码是低效的”，或“一些题目用递归的写法没法得到满分”。确实是这样的，因为运行时间或递归栈内存限制，导致一些题目必须改成递推的写法才能AC。但不代表你可以不会递归的写法。本节练习依然有些题用递归写是拿不到满分的，但本节目的不只是写对这些题，而是希望锻炼用递归分析题目、锻炼递归写法。
【基础】学习分析递归公式，用递归的解法求解题目。
【基础】学会分析递归程序的时间复杂度。
【基础】理解为什么递归程序在一些题目中拿不到满分。（为什么一个正确的递归写法，在一些输入下会超时或超内存？）（可以试试在自己的电脑上，递归深度达到多少时，一个正确的递归程序也会在运行中出现异常）
【基础】学会将递归程序改写为递推写法。
多个例题帮助你理解递归，随便看几个，看到懂就可以不继续看了！
多个例题帮助你理解递推，随便看几个，看到懂就可以不继续看了！
本章第2～4题，建议都用递归先写一遍（没拿到满分是正常的），再用递推写。
最后一题略有难度，如果你写到这时已经是2月份了，可以直接跳过最后一题。
再次强调，本章题目，递归写法写对了也不一定能拿到满分，但一定要学会如何用递归写法写这几个题目！
B. P1888 三角函数
C. P2562 [AHOI2002] Kitty猫基因编码
D. P1706 全排列问题