递归函数从零到掌握:自学是门手艺递归篇完整教程
递归函数从零到掌握:自学是门手艺递归篇完整教程
《自学是门手艺》(the-craft-of-selfteaching)是李笑来编写的免费开源自学手册。这篇文章是该书递归篇的完整教程,用零门槛的方式讲透 Python 递归函数——公认理解门槛最高的概念:递归函数的执行流程如何运转、为什么必须有退出条件、递归三原则是什么,以及自学者怎样真正掌握递归式思维。全文代码极少,读懂即可上手。
递归函数是什么:一个"自己调用自己"的函数
书中把递归函数(Recursive Functions)称为"理解门槛比较高的概念"——那些在自身内部调用自身的函数。经典示例是计算阶乘(factorial):
n! = n × (n-1) × … × 1,即n! = n × (n-1)!
递归写法出人意料地简短:
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
短短 5 行,却藏着两个关键要素:
- 返回自身的调用(或含自身的表达式)——这才是"递归"的本体;
- 退出条件
n == 1——这才让递归"能停下来"。
递归函数的执行流程:f(5) 是怎么变成 120 的
初学者最容易迷惑的一点:f(5) 调用了 f(4) 之后,f(5) 去哪了?答案是:它挂起,等待 f(4) 的结果返回后才继续。整个过程像下楼梯再上楼梯:
这张表来自原书,精确记录了每次调用与返回:
f(5)算不出来,先调用f(4)并等待;f(4)再调f(3)等待……一路到f(1);f(1)命中退出条件,直接返回1;- 值逐层回传:
1 → 2×1=2 → 3×2=6 → 4×6=24 → 5×24=120。
在函数里加几行输出语句,就能亲眼看到"先下后上"的顺序,完整可运行代码在 Part.2.D.4-recursion.ipynb 中,跑一遍胜过读十遍。
没有退出条件的递归:和尚讲故事与 RecursionError
书中用一个极妙的例子解释"没有退出条件会怎样"——中国经典绕口令故事:
山上有座庙,庙里有个和尚,和尚讲故事,他说……
山上有座庙,庙里有个和尚,和尚讲故事,他说……
山上有座庙……
"套娃式"的故事永远讲不完,在程序里就是无限循环(死循环)。同理,电影《盗梦空间》的"入梦"也是递归函数:除非满足"在梦中死去"或"被 kick"这两个退出条件,人就永远醒不来。
没有退出条件的递归函数,跑不了几十次就会被 Python 拦下:
RecursionError: maximum recursion depth exceeded
以后再看到 RecursionError 别慌,它只是在提醒你:递归缺少退出条件,或者无法逐步逼近退出条件。
递归函数三原则:写出合格递归的自检清单
全书对递归的精髓浓缩为"递归三原则",写递归函数前逐条对照即可:
| # | 原则 | 自问一句 |
|---|---|---|
| 1 | 必须在内部调用自己 | return 语句里含自身的调用吗? |
| 2 | 必须设定退出条件 | 什么情况下直接返回值、不再递归? |
| 3 | 必须能逐步达到退出条件 | 每次递归都离退出条件更近一步吗? |
三条缺一不可。factorial() 之所以是合格的递归函数,正是因为它每次调用 n 减 1,必定逐步逼近 n == 1——注意第三条强调的是"逐步达到",而不是"反正迟早能达到"。
递归总让人迷惑?先搞懂变量作用域
初学者另一个高频困惑:"函数里的 n 为什么不会跟着递归一层层变掉?"
关键在变量作用域:每次 factorial(n) 被调用都会形成一个独立的作用域,函数内外两个 n 只是"名字恰好相同",毫无关系。把参数传入函数,传的是值,外部变量不会被修改:
n = 5
m = factorial(n) # 函数内部怎么操作,n 都保持 5
print(n, m) # 5 120
原书 Part.2.D.4-recursion.md 专门用几组变量名不同的 factorial() 对比,帮你一眼看穿"命名巧合"的迷雾,建议对照阅读。
递归不只是一个技巧:它是自学的思维方式
作者强调:递归不是某种编程语言的特有属性,而是一种特殊算法与解题方式——当问题可以被拆分成越来越小的模块、且每个模块都用同一种算法处理时,递归最简洁有效。更妙的是,学递归本身就在锻炼脑力:从迷惑、到不太迷惑、到特别清楚,这段"烧脑"过程留下的思维肌肉,可以复用到所有难题上。
全书封面那段"伪代码"本身就是个递归函数:
def teach_yourself(anything):
while not create():
learn()
practice()
return teach_yourself(another)
teach_yourself(coding)
自学还真的就是个递归函数:学、练、造;当前一项完成,就带着下一个主题再次调用"自己"——退出条件只有一个:能够创造。
从递归篇出发:你的下一步自学路径
递归篇位于全书第二部分"为什么从写函数开始?"。建议先完成函数与参数两个前置章节,再向文档字符串、模块、测试驱动开发推进。相关章节文件路径如下:
- 前置 · 函数入门:Part.1.E.4.functions.md
- 前置 · 关于参数(上):Part.2.D.1-args.md
- 本章正文:Part.2.D.4-recursion.md,可运行版本为 Part.2.D.4-recursion.ipynb
- 下一站 · 函数的文档:Part.2.D.5-docstrings.md
- 下一站 · 保存到文件的函数(模块):Part.2.D.6-modules.md
- 下一站 · 测试驱动的开发(TDD):Part.2.D.7-tdd.md
- 进阶 · 刻意思考:Part.2.E.deliberate-thinking.md
- 封面(含递归式自学伪代码):00.cover.md
掌握递归函数,你获得的不只是一个 Python 编程技巧,更是一门自学的手艺:把大问题拆成越来越小的模块,用同一种方法逐个击破,并为自己设定清晰的退出条件——递归如此,自学亦然。


