调用自己的解法，递归

它再调用自己

解法调用自己，
听着有点怪吧。
可它很简单。
要做“解(5)”，
做“解(4)”就行，
要做“解(4)”，
做“解(3)”就行。
同一套解法，
用更小的输入再调用一次。

同一个盒子用更小的输入再调用自己。(解(5) → 解(4) → … → 解(1))

盒子里同样的盒子，
里头还是同样的盒子。
像镜中镜一样。
变的只有一样，
输入一格格地变小。
越变越小，
迟早成了很小的、
马上能解的问题。

停下的地板

要是只顾着调用自己，
会怎样？
没完没了往下掉。
所以递归里
必须有个说
“到这儿停”的地板。
“输入到 1 了，
就别再调用，直接给答案”，
就是这样的约定。

有地板 vs 没地板。(有: 到 1 就停 · 没有: 没完没了往下)

有地板，
往下走到那儿就停，
再带着答案爬回来。
没地板，
就一直往下掉进 0、负数，
永远出不来答案。
所以用递归时，
得先把地板定好。

堆起来再解开

递归怎么凑出答案，
分两步。
往下走时，
先把答案搁一边，
不停调用自己，堆起来。
一碰到地板，
这回倒着爬上来，
把堆着的一个个
合起来，凑成答案。

边下边堆，从地板倒着合。(乘(4) = 4x3x2x1 = 24)

往下走时看不到答案，
会有点憋。
可一踩到地板，
就倒着顺顺地解开。
堆得越多，
上来时要合的也越多。
所以堆得太深
就吃力，
那是后话。

和分治是一回事

回想上一课。
我们把大问题劈成两半，
各自解开，再合起来。
那个“劈开各自解”
其实就是递归。
解(8)
调用解(4)和解(4)，
那些 4 又
调用解(2)。

把劈开变成递归调用。(解(8) → 解(4)·解(4) → 解(2)×4)

所以分治和递归
不是两码事，是一回事。
劈开 = 再调用自己。
一块小到
劈不动了，那就是地板，
小答案往上合，
就是堆起再解开。
前面看的全在这儿聚到一块。

递归，一句话

递归有三根柱子。
用更小的输入调用自己，
有个停下的地板，
堆起来再倒着解开。
只要这三样齐了，
看着复杂的问题
也能悄悄甩给
“比自己小的自己”去解。

三根柱子，依次。(调用自己 → 停下的地板 → 堆起再解开)

只有一点要留神。
劈着劈着，同样的小问题
有时会被一遍遍重解。
把同一个答案反复求，
太费时间。
有个把解过一次的答案记下来
再用的窍门，
那正是下回的事。