递归思考：基础情况与递归
将问题拆分为更小的同类问题
递归思考：基础情况与递归 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
递归的含义
递归是指函数通过对更小的部分调用自身来解决问题，直到这部分小到可以直接回答为止。🌀
相信更小规模的副本
关键的思维方式是相信递归调用能够完成任务：假设递归调用已经能够处理更小的输入，然后在此基础上构建您的答案。
每个递归都需要基本情况
基本情况是您无需继续递归、可以直接回答的最小输入。如果没有它，函数就会永远调用自身并最终崩溃。
递归情况
递归情况会缩小问题，并在更小的版本上调用自身。每次调用都必须更接近基本情况。
以阶乘作为第一个例子
这里的 阶乘 同时展示了两部分：零的基例，以及对 n 减一的递归调用。
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)调用栈的工作方式
每次调用都会在调用栈中等待，直到内部调用返回。最深层的调用会先完成，然后结果逐层向上返回。
关注递归深度
Python 默认将递归深度限制在约 1000 层。深度较大的竞赛递归需要使用 sys.setrecursionlimit，以避免运行时错误。
import sys
sys.setrecursionlimit(300000)每次调用都要取得进展
正确的递归总会让输入逐步缩小，趋向基例。如果某次调用再次遇到相同的规模，它就会无限循环。⚠️
递归求列表和
这个递归求和会去掉第一个元素，然后依靠调用来加上列表的其余部分。
def total(a):
if not a:
return 0
return a[0] + total(a[1:])递归树展示分支
当一个函数发起多个调用时，这些工作就会形成一棵递归树。树的大小告诉您总成本是多少。
重复计算可能很慢
朴素的斐波那契算法会反复重新计算相同的值，导致指数级时间。对这些结果进行记忆化就能立即解决这个问题。
快速检查
如果递归函数没有基例，会发生什么？
回顾：两部分，一个思路
您学到了，递归需要一个用于停止的基例，以及一个会缩小输入的递归情况。将更小规模的工作交给递归调用，剩下的自然会完成。🎯
用 AI 导师学习 Coding Interview Prep — 免费
在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。
- 课程
- 90
- 课程
- 360
常见问题解答
「递归思考：基础情况与递归」课时是免费的吗？
是的 — 「递归思考：基础情况与递归」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「递归思考：基础情况与递归」这节课中我会学到什么？
将问题拆分为更小的同类问题 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「递归思考：基础情况与递归」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 递归思考：基础情况与递归
- 生成所有子集
- 排列与 N 皇后思想
- 剪枝以应对时间限制