前面几章，我们已经把函数的基本骨架慢慢搭起来了。
你已经知道，函数可以定义，可以接收参数，可以返回结果，也知道参数怎么设计更清楚，变量作用域为什么会让很多人一开始犯迷糊。 到这里，函数对你来说，应该已经不再只是一个陌生语法了。
但接下来，你会碰到函数世界里一个看起来特别神奇的现象：
函数，居然可以调用自己。
很多人第一次看到递归时，第一反应都差不多：
这不是套娃吗 它不会死循环吗 函数自己调自己，到底图什么 这种写法看起来很绕，真的有必要学吗
这些反应都很正常。
因为递归这个东西，表面看确实有点反直觉。 平时你理解函数，都是一个函数去调用另一个函数。 突然看到它自己调用自己，大脑很容易先打个结。
但你只要把递归背后的逻辑想清楚，就会发现它其实并不玄。
递归最核心的思想只有一句话：
把一个大问题，拆成一个和原问题长得很像、但规模更小的小问题
而函数之所以能调用自己，正是因为这种问题结构本身具有自相似性。
这一章，我们就把递归这件事彻底讲明白。 不急着上复杂题，不急着搞什么很绕的数学推导。 我们先从最容易理解的角度入手，把这个看起来神秘的东西，一层一层拆开。
一、先别急着看代码，先理解什么叫递归
你可以先把递归理解成一种解决问题的思路。
这种思路的特点是：
当前问题，和更小一点的问题，本质上是同一种问题 我只要先解决更小的那个 当前这个就能顺带解决
比如数楼梯。
如果你站在第 10 级楼梯，想走到第 1 级， 你其实可以先想：
那我先走到第 9 级再说
而从第 9 级走到第 1 级， 和从第 10 级走到第 1 级，本质上是同一类问题，只不过规模变小了一点。
这就是递归的味道。
它不是一下把整个问题全部硬算出来， 而是不断把问题往更小的同类问题上推。
所以递归不是某种奇怪的函数技巧。 它首先是一种思考方式。
二、为什么函数可以调用自己
因为函数本来就是一个带名字的处理过程。
只要这个处理过程面对的是一个可以继续拆成更小同类问题的任务， 那它当然就可以在处理中，继续调用自己去解决那个更小的问题。
比如你定义了一个函数，专门负责：
打印从某个数字开始倒数到 1
那如果现在它要处理数字 5， 它可以先打印 5， 然后把 剩下从 4 倒数到 1 这件事，再交给自己。
看起来像是自己调用自己。 但本质上是在说：
我已经知道怎么处理这个类型的问题了 那更小一点的同类问题，当然也可以继续由我来处理
所以递归函数不是在自我纠缠， 而是在重复使用同一套逻辑处理越来越小的问题。
三、递归最关键的两个要素
你现在先记住两个词，后面会反复出现。
第一个，结束条件 第二个，递归步骤
这两个东西缺一个，递归都不成立。
为什么？
因为函数自己调用自己，如果没有结束条件，它就会无限调下去。 这肯定不行。
所以递归一定要有一个明确的停点。 也就是：
到什么情况下，不再继续调自己了
这就是结束条件。
而递归步骤则是在说：
如果还没到结束条件，那我怎么把当前问题缩小一点，再交给自己
你可以把它理解成：
结束条件，负责踩刹车 递归步骤，负责继续往前走
递归能不能写对，核心就看这两件事是不是想清楚了。
四、先看一个最简单的递归例子：倒数
比如我们想打印从 n 倒数到 1。
正常写法你当然可以用循环。 但现在我们专门用递归感受一下。
defcountdown(n):if n == 0:return print(n) countdown(n - 1)countdown(5)
输出：
54321
这段代码非常适合当递归入门例子。
我们来拆开看。
if n == 0:return
这就是结束条件。 意思是：
当 n 变成 0 时，别再往下调了，函数结束。
然后：
print(n)countdown(n - 1)
这就是递归步骤。
先打印当前的 n， 然后把更小的问题，也就是 n - 1，再交给自己去处理。
你会发现，这个函数并没有一次性想完 5 到 1 所有细节。 它每次只做两件事：
处理当前这一层 把剩下更小的问题交给下一层
这就是递归最朴素的样子。
五、为什么这个例子不会死循环
因为有结束条件。
我们来脑子里顺一遍：
countdown(5)打印 5 再调 countdown(4)
countdown(4)打印 4 再调 countdown(3)
countdown(3)打印 3 再调 countdown(2)
一直到：
countdown(1)打印 1 再调 countdown(0)
这时候：
if n == 0:return
成立，函数结束，不再继续往下调。
所以递归可怕的从来不是 自己调自己， 真正危险的是：
你有没有明确让它在某个时刻停下来
只要停点设计清楚，递归本身并不神秘。
六、如果没有结束条件，会发生什么
看这个例子：
deftest(): print('开始') test()test()
这段代码几乎肯定会出问题。
因为它一直在调自己， 却永远没有停下来的时刻。
这就像你在镜子前照镜子，镜子里再有镜子，永远套下去。 程序会一直不断往下调用，最后把调用空间耗尽，然后报错。
所以你现在要牢牢记住一句特别重要的话：
递归最怕的，不是自己调用自己 而是没有结束条件
很多人一听递归就怕，本质上其实是怕失控。 而结束条件，正是用来防止失控的。
七、递归为什么看起来像在重复，但又不是普通重复
因为它和循环的重复方式不一样。
循环更像是：
同一个动作在同一层重复很多次
比如 for、while
而递归更像是：
当前这一层，把剩下的问题交给下一层 下一层再把剩下的问题交给更下一层
也就是说，递归的重复，不是横着重复， 而是往下一层一层展开。
这也是为什么很多人第一次看递归，会觉得脑子有点立体化了。 因为它不像循环那样扁平。
你可以把它想成一层层往下走台阶。 每一层都做类似的事，但处理的是更小规模的问题。
八、再看一个更经典的递归例子：求阶乘
阶乘是递归教学里非常经典的例子。
比如 5 的阶乘是：
5 × 4 × 3 × 2 × 1
写成数学关系，其实就是：
5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!
你会发现，这里面就藏着非常明显的递归结构：
当前问题，等于当前值 × 更小的问题
代码如下：
deffactorial(n):if n == 1:return1return n * factorial(n - 1)print(factorial(5))
输出：
120
这段代码里：
if n == 1:return1
是结束条件。 因为 1 的阶乘就是 1，已经不能再拆了。
而：
return n * factorial(n - 1)
就是递归步骤。 意思是：
当前 n 的阶乘 等于 n 乘以 n - 1 的阶乘
你会发现，这种问题特别适合递归。 因为它天然就长着一个“自己依赖更小自己”的结构。
九、递归最容易让人懵的地方，不是代码，而是执行过程
比如刚才这个：
factorial(5)
很多人看代码还能看懂。 但一问它到底怎么执行，就容易乱。
我们来手动拆一下：
factorial(5)等于 5 * factorial(4)
而 factorial(4)等于 4 * factorial(3)
而 factorial(3)等于 3 * factorial(2)
而 factorial(2)等于 2 * factorial(1)
而 factorial(1)直接返回 1
所以整个过程就会变成：
5 * 4 * 3 * 2 * 1
最后得到 120。
你会发现，递归其实不是在魔法计算。 它只是不断把大问题展开，直到碰到最小的结束条件， 再一层层把结果带回来。
所以很多人学递归卡住，不是不会写那几行代码， 而是脑子里没有把“展开”和“回收结果”这两个过程想清楚。
十、递归可以理解成“先往下拆，再往回收”
这句话特别值得记住。
递归执行时，通常会经历两个阶段：
先一层层往下调用 直到碰到结束条件
然后再一层层往回返回结果
比如阶乘那个例子：
先往下拆：
5 4 3 2 1
到了 1 停住。
然后开始往回收：
factorial(1) = 1factorial(2) = 2 * 1 = 2factorial(3) = 3 * 2 = 6factorial(4) = 4 * 6 = 24factorial(5) = 5 * 24 = 120
这就是为什么很多人说递归像压弹簧。 先一层层压下去， 再一层层弹回来。
这个理解方式特别有助于你看懂递归返回值是怎么传回来的。
十一、不是所有问题都适合递归
这一点一定要讲清楚。
学了递归，不代表以后什么题都该上递归。 递归不是越高级越好，也不是越绕越厉害。
它特别适合的问题，通常有一个共同点：
问题本身就能自然拆成更小的同类问题
比如：
倒数 阶乘 树形结构遍历 文件夹层级遍历 某些数学定义 某些分治问题
但如果一个问题本身根本没有这种结构， 你硬上递归，代码就会写得又绕又难读。
所以递归不是必须到处用。 它只是函数世界里特别重要的一种思路。
你当前阶段最重要的，不是追求处处递归， 而是先学会识别：
什么时候这个问题本身就长得很递归
十二、递归和循环，不是谁替代谁
很多新手学到这里会问：
既然倒数、求和这些东西，用循环也能做，那递归到底图什么
这个问题问得非常好。
答案是：
递归和循环都能解决一些重复问题 但它们的思维方式不同
循环更适合那种：
重复规则很平铺 一步一步往前走 状态变化比较直观
递归更适合那种：
问题天然是层层嵌套的 每一步都和更小的同类问题有关 整体结构像树、像套娃、像一层包一层
所以不是递归比循环高级。 也不是学了递归就不用循环了。
更准确地说是：
有些问题用循环更自然 有些问题用递归更自然
你越往后学，越会体会到这种 选工具 的感觉。
十三、再看一个特别生活化的递归理解方式：套娃
假设你有一个套娃。 最大的娃里面装着一个小一点的娃， 小一点的里面又装着更小的。
如果你想把最里面那个拿出来，思路其实很像递归：
先打开当前这个 再去处理里面那个 直到里面已经没有更小的为止
这就是典型的递归结构。
每一层都在做同样的事： 检查当前这一层 如果还有更小的，就继续处理下一层
直到某一层成为最小单元。 那就是结束条件。
这个比喻非常适合帮助你理解递归为什么“长得像自己调自己”。 因为问题本来就是一层套一层的。
十四、递归函数的代码，往往看起来很短，但理解不能只看表面
比如阶乘函数：
deffactorial(n):if n == 1:return1return n * factorial(n - 1)
就两行核心逻辑。 短得不能再短。
但递归最容易骗人的地方就在这里：
代码短，不代表思路浅
很多人一看代码短，就觉得自己肯定懂了。 结果一让他手动推执行过程，就乱掉。
所以学递归时，千万别只停留在：
我看得懂代码字面
更重要的是：
我能不能顺着参数变化，把它一层层推下去，再一层层收回来
这才是真正理解递归。
十五、写递归函数时，最该先想什么
永远先想这两个问题：
结束条件是什么 怎么把问题缩小
比如倒数：
结束条件是 n == 0缩小方式是 n - 1
比如阶乘：
结束条件是 n == 1缩小方式是 n - 1
你会发现，大部分递归题最难的地方，其实不是语法。 而是这两个问题有没有想明白。
只要结束条件和缩小方式想清楚，代码往往很短。 反过来，只要这两个问题没想清楚，代码再短也很容易写错。
所以以后你一看到递归题，先别急着下手写。 先问自己：
到哪里停 每次怎么缩小
这是最稳的递归思路。
十六、一个特别容易犯的错：问题没有真的变小
比如你写：
deftest(n):if n == 0:return print(n) test(n)
这里看起来好像也有结束条件。 但问题在于：
你递归调用时，传进去的还是 n， 根本没有变小。
这就意味着，如果 n 一开始不是 0， 它永远不会朝结束条件靠近。 程序最后还是会失控。
所以递归不仅要有结束条件， 还必须保证每次递归调用时，问题确实在朝结束条件逼近。
这一点特别重要。
你可以把它理解成：
不是光有刹车就行，车还得真的朝终点开过去 不能原地轰油门
十七、再看一个字符串场景下的递归例子
比如你想打印一个字符串的每个字符。
当然，这事用循环更自然。 但我们现在专门用它来感受递归。
defprint_chars(text):if text == '':return print(text[0]) print_chars(text[1:])print_chars('python')
输出：
python
这段代码里：
结束条件是：
if text == '':return
也就是字符串已经空了，就结束。
递归步骤是：
先处理第一个字符 再把剩下的字符串继续交给自己
你会发现，这个结构也很递归。
当前问题：打印整个字符串 更小的问题：打印去掉第一个字符后的字符串
虽然这个例子日常写法不推荐递归， 但它特别适合帮你建立感觉：
递归并不只属于数字题 只要问题天然能缩小成同类问题，就能递归
十八、递归和函数调用栈，你现在只要理解一层就够了
你以后可能会听到一个词：
调用栈
当前阶段你不用把它想得太复杂。 先理解成：
每调一次函数，程序就会暂时记住这一层的执行状态 等里面更深那一层执行完了，再回来接着往下走
这也是为什么递归可以一层层往下，再一层层回来。
比如 factorial(5)， 程序会记住 5 这一层还没算完， 因为它还等着 factorial(4) 的结果。 而 factorial(4) 又会等 factorial(3)一直等到 factorial(1) 返回。
然后再一层层把结果带回来。
你现在只要理解成：
递归时，程序会帮你记住每一层还没完成的任务
这已经够用了。
十九、递归为什么容易让人一开始头晕
因为它不像普通代码那样从上到下线性流动。 它会发生一种“先深入，再返回”的过程。
而人的直觉通常更适合处理：
一步接一步 从前往后
递归却更像是：
先往更深处走 再从最里面往外回来
所以你一开始觉得绕，不代表你笨。 而是这种思维本来就需要适应。
最好的办法不是硬背， 而是多做这种事：
把一个具体递归调用过程，拿纸一层层写出来
比如写：
factorial(4) 怎么展开countdown(3) 怎么一层层结束
你只要亲手推过几次，脑子就会顺很多。
二十、一个特别实用的递归调试建议
如果你写递归函数总觉得它像黑箱， 最简单的办法就是：
多 print
比如：
defcountdown(n): print('进入函数，n =', n)if n == 0: print('到达结束条件')return countdown(n - 1) print('函数返回，n =', n)countdown(3)
输出会让你非常直观地看到：
它是怎么一层层进去 又怎么一层层回来的
这招特别有用。
因为很多人不是逻辑想不明白， 而是递归的执行过程在脑子里太抽象了。 而打印过程，会把这个抽象过程可视化。
以后你遇到递归发懵， 第一反应不是放弃， 而是先把每层状态打印出来看看。
二十一、最容易犯的几个错
第一个，没有结束条件。
这是最危险、也最经典的错误。 没有结束条件，递归就会一路掉下去。
第二个，结束条件写了，但问题没有真正变小。 结果还是永远到不了停点。
第三个，结束条件位置不合理。 导致函数该停时没停，不该停时提前停了。
第四个，只会看代码表面，不会手动推执行过程。 这样一到稍微复杂一点的递归就容易乱。
第五个，明明问题更适合循环，却强行用递归。 结果把自己绕进去了。
所以递归最重要的不是敢写， 而是写之前先想清楚：
为什么这个问题适合递归 停点在哪里 每次怎么缩小
二十二、这一章最该建立的，不是“我会写递归了”，而是递归感觉
你现在不需要马上做到：
任何递归题拿来就秒写
这不现实，也没必要。
这一章更重要的目标是：
你开始理解递归到底是什么 你不再害怕函数调用自己 你知道递归必须有结束条件 也知道递归每一步都要把问题缩小
这就已经非常够用了。
递归真正的熟练，不是靠一次讲完就彻底掌握。 而是后面你不断遇到那些天然递归的问题时，慢慢把感觉练出来。
所以当前阶段，不求全能。 先把味道吃到，最重要。
二十三、练习题：这一章一定要自己推一推
下面这些小练习，建议你一定要手动敲，也最好手推一下过程。
1. 写一个递归函数，打印从 n 倒数到 1
defcountdown(n):if n == 0:return print(n) countdown(n - 1)countdown(5)
2. 写一个递归函数，求 n 的阶乘
deffactorial(n):if n == 1:return1return n * factorial(n - 1)print(factorial(5))
3. 写一个递归函数，逐个打印字符串字符
defprint_chars(text):if text == '':return print(text[0]) print_chars(text[1:])print_chars('python')
4. 给递归函数加上打印语句，观察它怎么一层层进去再回来
比如：
deftest(n): print('进入', n)if n == 0: print('结束')return test(n - 1) print('返回', n)test(3)
这一题特别有价值。 因为它会帮你真正看到递归的执行节奏。
二十四、本章小结
这一章我们正式认识了递归函数。
你要记住的核心不是某段代码，而是递归背后的思路：
把一个大问题，拆成一个更小的同类问题 函数继续去解决这个更小的问题 直到遇到结束条件为止
递归最关键的两个要素是：
结束条件 递归步骤
结束条件负责停下来。 递归步骤负责把问题缩小。
你还要记住几个特别实用的点：
函数可以调用自己 但前提是问题本身适合递归 递归不是没有尽头地套娃 而是要朝着结束条件一步步逼近 理解递归，不能只看代码，要学会手动推执行过程
从这一章开始，你已经接触到函数世界里一个非常有代表性的思维方式了。 它不一定是你以后最常用的写法， 但它会极大地训练你怎么去理解：
大问题如何拆成小问题 而小问题又如何和大问题保持同一种结构
下一章我们继续讲 把复杂问题拆成函数，是编程进阶的第一步。 到那一章，你会发现，递归是把问题往“更小的自己”里拆，而更广泛的函数设计，则是在把大问题往“多个小功能”里拆。
10个月宝宝每天需要喝多少奶粉？
