怎么工作 算法里递归 怎么用

再调用自己

解法调用它自己，听起来有点怪，其实很简单。
要解“解(5)”，只要解“解(4)”；要解“解(4)”，只要解“解(3)”。
就是用更小的输入，再调用同一个解法。

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

盒子里有一模一样的盒子，那里面又有一模一样的盒子，就像镜子里的镜子。
变的只有一样：输入每次小一格。
小了又小，总有一天会变成一下子就能解决的很小的问题。

停下的地板

如果只是一个劲儿地调用自己，会怎样？会没完没了地往下走。
所以递归一定要有一块写着“到这儿停”的地板。
比如“输入变成 1 时，不再调用，直接给出答案”这样的约定。

比一比有地板 vs 没地板。有的话到 1 就停，没有的话会没完没了地往下走。

有地板，往下走到那里就稳稳停住，再从那里带着答案往上走。
没有地板，就会一路掉进 0、负数，永远得不出答案。
所以用递归时，要先定好地板。

先堆起来，再解开

递归得出答案，分成两步。
往下走时，先把答案搁一搁，一边不停调用自己一边往上堆。
碰到地板后，再倒过来往上走，把堆起来的东西一个个合起来，得出答案。

边往下走边堆，再从地板倒着合起来。（乘(4) = 4x3x2x1 = 24）

往下走时看不到答案，可能有点憋闷。
可一碰到地板，就倒着顺顺当当地解开了。堆得越多，往上走时要合的也越多。
还要记住，堆得太深，连电脑也会吃不消。

和分治是一回事

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

把切分变成递归调用。（解(8) → 解(4)·解(4) → 解(2)×4）

所以分治和递归不是两回事，而是一回事。切开 = 再调用自己。
块小到切不开时，那就是地板；小答案往上合并，就是先堆起来再解开的过程。
前面看过的，全都汇到这里。

一句话说递归

递归靠三根柱子撑着：用更小的输入调用自己，有一块让它停下的地板，先堆起来再倒着解开。
只要这三样齐了，看起来复杂的问题，也能悄悄交给“比我小的我”去解决。

按顺序点这三根柱子来总结。（调用自己 → 停下的地板 → 堆起再解开）

不过有一点要当心。切着切着，有时会把同一个小问题一遍遍地重复解。
同样的答案一再重算，太浪费时间。
有个办法是把解过的答案记下来，下次直接用，那就是下一课的内容。