什么是递归

调用自己的函数

第9课里，函数是把事情打包起名的东西，函数里面还能调用别的函数。
递归又往前走了一步：函数再次调用它自己。
就像镜子里的镜子，同样的东西又多了一层。

每按一次“再一层”，里面就多出一层同样的框。

很神奇，也有点吓人。
这样一直调用自己，不是永远停不下来吗？
没错。所以递归必须要有一样东西。

必须有停下来的地方

两面镜子确实能无限照下去，可计算机做不到“永远”。
所以要定一条规则：“碎块小到一定程度，就在那里停下。”
没有这条停止规则，它就会一直转下去，最后崩溃。

打开停止规则，到3、2、1就稳稳停住；关掉它，就会一直往下，最后崩溃。

把停下的地方想成“底”，就好懂了。
到底之前一直调用自己，到底以后就不再调用。
那么，关键就在于怎样拆分问题。

同一个问题的缩小版

递归真正的诀窍，是把大问题看成“一步 + 同样但更小的问题”。
整段楼梯等于一级台阶加上剩下的楼梯，而剩下的楼梯也是同样的问题，只是少了一级。
越变越小，到了0级，就结束了。

每按一次“拆掉一级”，楼梯就少一级。剩下的楼梯，每次都是“同样但更小”的问题。

难题一下子变简单了。
不必一口气全部解决，只处理“一级”，剩下的再交给同一个函数就行。
可是交出去的事，又是怎么回来的呢？

下去再回来

递归朝两个方向走。
先是调用自己、再调用自己，一路下到底。
到底以后，再反过来往上走，每一层加上自己的那一份。
就跟先把盘子摞起来，再从上往下一个个收走一模一样。

按“下一步”，就会把1+2+3一路拆到底，再往上走，合成6。

这种“下去再上来”，就是递归的心脏。
往下走时拆分问题，往上走时合并答案。
堆起来的事，从底下开始依次解开。

循环的兄弟，以及更远处

递归和循环（第7课）是兄弟。
两者都把同一件事做很多遍，但循环是横着一排摆开，递归是一层层往里钻。
像文件夹里的文件夹那样枝上又生枝的事，用递归最合适。

每按一次，枝杈就会再分出来。同一条规则，自己画出了一棵树。

把事情打包起名的函数（第9课），现在连自己都能调用了。
拆小、在底部停下、再合起来，这一个想法能解开文件夹、回复的回复，甚至走迷宫。
下一课我们去看怎样把值成对地装起来。