数一摞书：拿一本数 1，再拿一本数 2，一本一本地数；或者把问题变成"最上面一本 + 剩下那摞有多少本"，对剩下那摞重复同一动作，直到剩 0 本。前者是迭代，后者就是递归。

递归能把任何问题变成「对自身的调用」，但具体怎么「变小」决定了策略。减而治之是最朴素的一条：从规模 n 退回 n-1，把子问题做完，再补回当前这步——里面藏着递归设计的整套思维。

从「减而治之」我们把问题递归变小求解，但递归一旦深起来，脑子里就乱成一团——怎么才能看清它在做什么？这就要靠递归跟踪。

递归跟踪让我们看清了每一次调用的开销，但调用树一旦指数级膨胀，手工追踪就不再现实。我们需要一个数学工具，把整棵调用结构压缩成一行——这就是递推方程。

: 数组倒置：定义、要点与典型应用

上一节的减而治之，每步只把问题缩小一点点。但有些问题更顺手——一刀切成几块，各算各的，最后拼起来。这就是分而治之。

上页刚拆完分而治之的'分-解-合'骨架。这页拿最经典的例子——二分递归求数组和——把它填满。注意：每个层级同时发出两个递归调用，正是'分'字最直观的体现。

求数组最大值，最直白的做法是从头扫到尾记一个当前最大——这是迭代。Max2 则把数组对半劈开，各自递归求最大，再比一次。思路简单，但时空代价和迭代版本差别显著。

上一节的数组求和，把两半递归结果直接相加；Max2 也是这个套路，但'合'起来不再是加法，而是两场比较。同一个二分递归框架，换了一种归并动作。

• ✓递归本质是问题规模的自我引用，复杂度取决于递推关系而非写法
• ✓减而治之：每层减一个常数项，时间通常呈 O(n)
• ✓分而治之：规模折半加合并，T(n)=aT(n/b)+f(n) 是骨架
• ✓递归跟踪表把调用-返回翻译成实例树，是分析时空代价的利器
• ✓同一问题可有多种递归分解，需用复杂度下界判定最优

先自己想，再点开参考答案对照——每个问题都值得琢磨几分钟。