自己叫自己的魔法
函数能调用自己？听起来像魔法，但其实递归就在你身边——俄罗斯套娃、镜中镜，都是递归。
你玩过俄罗斯套娃吗？打开一个大的，里面有个小的；打开小的，里面还有更小的……一直打开到最后一个不能再打开。这种“自己里面套自己”的结构，在编程里叫“递归”——一个函数在自己里面叫自己。听起来像魔法，但其实它是一种特别巧妙的解题思路。
你知道吗
你知道吗？谷歌搜索 recursion（递归），它会问你“是不是想查 recursion？”——这本身就是一个递归笑话！程序员之间还有句名言：“要理解递归，必须先理解递归。”
递归的两个关键
写递归要记住两件事：第一，要有“终止条件”——什么时候不再叫自己，否则会无限套下去，程序就崩溃了。第二，每次调用自己，问题要比上次“小一点”，朝着终止条件靠近。就像套娃，最小的那个打不开，就是终止条件。少了终止条件，递归就会像两面相对的镜子，无限反射下去。
举个例子：算 5 的阶乘（5!）。5! = 5 × 4!，4! = 4 × 3!，3! = 3 × 2!，2! = 2 × 1!，1! = 1（终止条件！）。所以 5! = 5 × 4 × 3 × 2 × 1 = 120。递归让复杂的问题变成“做一步 + 把剩下交给更小的自己”，思路清晰优雅。
递归在生活中其实很常见。你在两面相对的镜子里看自己，会看到无数个自己越远越小——这就是递归。一棵树的树枝分叉出小树枝，小树枝再分叉出更小的树枝，也是递归。甚至你问“我是谁”的时候，脑子里可能又冒出“‘我’是什么”的问题——这也是一种递归思考！理解了递归，你会发现世界到处都是它的影子。
- 递归就是自己叫自己
- 递归必须有终止条件
- 每次调用自己，问题要变小
- 阶乘、斐波那契数列都能用递归
- 树、套娃、镜中镜都是递归的例子
递归和循环有什么不同？
递归和循环都能让程序重复做事，但思路不一样。循环是“我做一遍、再做一遍、再做一遍”，像绕圈跑；递归是“我做一步，剩下的交给一个更小的我”，像把大任务一层层分给小助手。有些问题用循环写很麻烦，用递归却特别简洁，比如走迷宫、算家族树。但递归也不能乱用，调用太多次会让电脑“记不住”那么多层，导致崩溃。
动手试试
不插电小游戏：找一叠书，最上面一本写“5”。规则：每次翻开最上面一本，里面是“上一个数减 1”，直到翻开写着“1”的书为止，然后从最后翻开的开始大声报数：1、2、6、24、120——这就是 5!。每一步都在做“递归”。也可以和家人玩“传话游戏”：你悄悄对下一个人说一句话，他再悄悄传给下一个，最后一个大声说出来——这其实就是递归的“一层层传递”。
迭代是人，递归是神。——L. 彼得·多伊奇
