复杂度与递归函数

> LeekScript 教程

警告： 本文的数学含量很高（至少以本百科的标准而言）。如无医嘱，请勿服用。

说正经的：这里我要讲的是递归函数（见递归详解）的优化。本文比较适合对函数式编程和编程理论感兴趣的人。

写递归函数的时候，要知道自己在得到结果前会做多少次调用，并不总是那么容易；有时候甚至不知道到底能不能得到结果。递归详解教程给出了一些优化递归函数的思路，但没有做复杂度分析，也没有讨论正确性；所以这里我要通过例子来说明几种理清头绪的方法。

这份例子清单并不求穷尽，对你自己的每一个算法，都得仔细分析它究竟执行了哪些操作。

接下来就看你的了：把这些思路搬到你自己的算法上；如果你发现别的值得一提的例子，也欢迎写到这里来！

最初的几个例子

有些简单的递归函数，复杂度很容易分析。递归教程里的第一个例子就是这样：

function sumN(n) { if (n === 0) { return 0; } else { return n + sumN(n - 1); } }

这里很简单：容易看出，如果给这个函数一个（正的！）整数 n，它会把 n 加到 0 到 n-1 的和上，而这个和是它调用自身算出来的。于是我们做的是 n + (n-1 + ... + (0)...)，也就是 n 次加法和 n 次函数调用，复杂度为 O(n)。

不过，如果输入的是负整数，这个函数会造成栈溢出（stack overflow）：它会一直加负数，永远到不了 0。同理，如果给的不是整数，一次次减 1 也永远到不了 0。所以要留意递归函数的'''正确性'''：如果你没有考虑到所有情况，或者用了一个与你编写时设想不符的输入，就可能遇到很不愉快的意外。

优化教程则给出了一个复杂度为 O(2^n) 的函数例子：

function getAllCombos(liste_items){ var nb_items = count(liste_items);

if(nb_items == 1) { return [[], liste_items]; }

var sous_liste = subArray(liste_items, 1, nb_items - 1); var liste_combos_partielles = getAllCombos(sous_liste); // 递归调用 var m = count(liste_combos_partielles);

//然后把组合列表复制一份：原来的那些保留，再加上同样的组合、每个都带上 liste_items 的第一个元素 for(var i=0; i P(n) = 2*P(n-1)。再加上 P(1) = 2，就得到 P(n) = 2 * ... * 2 = 2^n，因此复杂度（至少）是指数级的。接着还能证明这个函数的复杂度确实就是指数级（不会更大）：每次调用都用 subArray 建一个长度为 n-1 的数组（代价：O(n)），然后做 m 次 push，m 是部分组合数组的长度，即 2^(n-1)（代价：K * 2^(n-1)，其中 K 是一次 push 的代价），这一项盖过了 subArray 的代价，于是复杂度就由 push 的次数 P(n) 决定。

我这里要展开的正是这个思路：先得到一个递推公式，再由它推出调用次数的上界公式，最后结合函数在递归调用之外还做了什么，推出复杂度。后面我基本不会再谈正确性（只在最后提一下），但请把这个概念记在心里……

在下文中，C(n) 一律表示所研究函数的代价。

简单递推：C(n) = f(C(n-1))

这里的“简单”并不是说复杂度会很友好，也不是说一定容易算。它的意思是：我们面对的是一阶递推，也就是一个用 C(n-1) 表示 C(n) 的式子。

幂之和：形如 C(n) = a * C(n-1) + b 的递推

先从简单的开始。我要研究的第一个例子相当蠢，但它也用来引入我的记法。你在这里学不到什么了不起的复杂度知识，不过至少本页会把简单情形交代清楚。

再看一个非常简单的函数（而且没什么用，写得也相当糟糕，因为它把同一个函数调用写了两遍，但我需要一个简单的例子）：

function sumPowers(n , k) { //n 为整数，k 任意 if (n === 0) { return 0; } else { return n**k + (sumPowers(n - 1 , k) + sumPowers(n - 1 , k))/2; } }

这里的代价 C(n) 只按整数 n 来分析，因为在 LeekScript 中乘方的代价是固定的。如果要按输入的规模（也就是 n 的比特数）来算代价，那各个复杂度里还得再加一层指数。但这里的目的是研究 C(n) = a * C(n-1) + b 这类数列，所以我只讨论关于 n 的复杂度，而不是关于它的比特数的复杂度。

这个函数和前面研究的那个很像，只是除了做一次加法之外还顺手算了一次乘方。在 LeekScript 中，* 运算符消耗 140 个操作数（和 pow 函数一样），加法和减法各消耗 1 个，除法 5 个，if 1 个，比较 n === 0 1 个，带两个参数的函数调用 5 个。因此代价函数 C(n) 对所有 n>0 满足 C(n) = 161 + 2C(n-1)，且 C(0)= 2。

现在我们来想想，由此怎么估计代价。我们有一个由 C(n) = a C(n-1)+ b 和 C(0) = c 定义的数列，其中 a ≠ 1。思路是把它化成更好用的形式 u(n) = a u(n-1)。为此，令 u(n)=C(n) + b/(a-1)。于是可以写出：

C(n) = a C(n-1) + b ⇒ C(n) = a C(n-1) + (a-1)b/(a-1) ⇒ C(n) = a C(n-1) + ab/(a-1) - b/(a-1) ⇒ C(n) + b/(a-1) = a C(n-1) + a*b/(a-1) ⇒ u(n) = a u(n-1)

这样，对所有 n >= 0 都有：

u(n) = a^n u(0)

而且 u(0) 很容易算：u(0) = C(0) + b/(a-1) = c + b/(a-1)。于是可以推出任意 n 对应的 u(n)：u(n) = a^n * (c + b/(a-1))。再回到 u(n) 由 C(n) 给出的定义，就得到：

C(n) = u(n) - b/(a-1) = a^n * (c + b/(a-1)) - b/(a-1)

这个公式说不上好看，但它告诉了我们什么呢？它告诉我们代价是 O(a^n)：b 和 c 都被吸收进（乘性和加性的）常数里了。这个函数的代价是以 a 为底的指数级，这里 a 等于 2。其实早该料到：真正费钱的，最终并不是用 ** 算乘方，而是傻乎乎地把同样的东西反复算了无数遍。 教训： 写递归函数时，绝对不要重复计算没有必要重复的东西！

那如果我们聪明一点，避免重复计算呢？

function sumPowers(n , k) { //n 为整数，k 任意 if (n === 0) { return 0; } else { return n**k + sumPowers(n - 1 , k); } }

这一次我们会得到 C(n) = 149 + C(n-1)。于是就落到了前面没有处理的 a = 1 的情形。

而这种情形要简单得多：直接递推就得到 C(n) = 149n + C(0) = 149n + 2，也就是线性复杂度，其中的常数由循环里所做操作的代价决定。

矩阵的行列式（非常糟糕的方法）：非线性递推

如果你学过一点数学，大概知道矩阵是什么：一张数字的表格，带有加法、与基域（这里就取 ℝ 吧）中元素相乘，以及矩阵之间相乘的运算法则。我们来看方阵的行列式的计算，这是研究方阵时相当有用的工具。计算行列式的一种方法如下：

function det(M){ //输入 M：n 阶方阵，表示为一个长度为 n 的数组，其中每个元素又是一个长度为 n 的数字数组。 var n = count(M); if(n === 1) { return M[0][0]; // 如果矩阵只有 1 阶，它的行列式就等于它唯一的那个值 } else { //否则…… var output = 0; var firstLine = shift(M);// ……取出第一行…… for(var i=0; iC 表示成矩阵行数的函数（或者列数，反正我取的是方阵，两者一样）。

n = 1 时的代价：没多少，几个操作而已（注：count 在 LeekScript 中是常数时间的）。 n > 1 时的代价：

各种零碎的固定代价
1 次 shift，它是 O(n) 的（我想是吧）
n² 次 remove，它应该也是 O(n) 的
n 次对 det 函数的调用，输入规模为 n-1。

所以我们得到形如 C(n) = n * C(n-1) + a * n^3 + 一些零碎项的东西。

先说一点：我们有 C(n) > n * C(n-1)。由此很容易推出，这玩意儿的复杂度至少是 O(n!)。

反过来也可以给出上界：对某个大于 a 的数 b（以及足够大的 n），有 C(n) ⩽ n * C(n-1) + b * n^3。我们来研究由 u(n) = n * u(n-1) + b * n^3（n>1）和 u(1)=1 定义的数列（u(1) 其实并不等于 1，但这不会改变复杂度，只会改变被 O 藏起来的那个常数）。用递推可得：

!Suite_rec_determinant_matrices

i^2/((i-1)!) 这个级数确实收敛到一个有限的极限。于是得到 u(n) ⩽ k * n!，其中 k 是某个实数。所以 C(n) 的复杂度至多是 O(n!)。结合前面得到的结论，可以断定 C(n) 的复杂度就是 O(n!)。

这种不写等式、而是设法'''比较'''的思路，往往很有用：说到底，我们要的是一个 O(f(n))，而不是精确的估计；能说出复杂度“至少这么大”以说明一个函数很费，或者“最坏也就这么大”以说明它很省，这就已经很有意思了！

形如 C(n) = f(C(n/a)) 的递推，其中 a 是一个固定的数

这类递推在使用二分法或分治类算法时自然会出现。它们给出的复杂度一般都带对数。

在有序数组中二分查找

LeekScript 自带一个在数组中查找的函数。不过，如果我们知道数组是有序的（因为事先排过序，或者它天生就是有序的），那就有办法查得比那个函数更快：

因此最多做 log(n) 步。每一步都加上一个代价 a，所以这个函数的代价是 a*log(n)。这个算法的复杂度于是是 O(log(n))（顺便回答可能会有的疑问：写成 O(ln(n)) 也一样，各种对数之间只差一个比例系数）。

但要注意：这并不表示就该把你所有的数组都排一遍序。查找的代价固然降下来了，可排序本身的代价是 O(n log(n))，比直接用 LeekScript 原生函数查找还要大。如果你要在一个数组里查很多次，先排序可能是个好主意；如果只查那么几次，那肯定不划算。

归并排序

归并排序算法（顾名思义）是一种给数组排序的算法。也有一些更省内存的版本，但实现起来比我下面要给你的这个稍微复杂一点。和所有排序算法一样，时间复杂度不可能好过 O(n log(n))。

这个算法基于以下原理：如果数组长度为 1，那它必然是有序的。否则，把数组一分为二，分别给每一半排序，再把两个数组归并起来，得到一个有序数组。

// 把两个有序数组归并成一个、并保持顺序的函数 function fusion(@array1, @array2){ //输入：两个有序数组 var output = []; var l = count(array1), m = count(array2); var i = 0, j=0; //i 和 j 用来记录在各自数组中推进到了哪里 while(i+j 1 的情况下）对两个长度减半的输入各做一次 fusionSort，再把得到的两个数组归并一次。先看 fusion 的代价。fusion 函数主要就是一个大 while，循环次数为两个输入数组长度之和。所以它的复杂度是 O(l+m)，其中 l 和 m 是输入数组的长度。这里它作用在两个长度为 n/2 的数组上，所以复杂度是 O(n)。于是代价形如：n>1 时 C(n) = a + bn + 2C(n/2)，其中 a 和 b 是常数，另有 C(1) = a。现在来数步数：因为每次长度都减半，我们要找满足 n/(2^k)=1 的数 k。和二分查找的情形一样，这个数是 floor(log(n))，再往后就落到基本情形 n=1 了。

把得到的复杂度展开一点：C(n) = a + bn + 2C(n/2) = a + bn + 2(a + b*(n/2) + 2 * C(n/4)) = a + 2a + bn + bn + 4C(n/4)。由于这一步在落到基本情形之前会重复 floor(log(n)) 次，就得到代价 C(n) = a2^(floor(log(n))+1) + bnfloor(log(n))。确实，i 从 0 到 floor(log(n)) 的 2^i * a 之和等于 a * 2^(floor(log(n)) + 1)。

用 log(n) 放大 floor(log(n))，就得到 `C(n) array[b]){ //如果两端的元素顺序反了，就交换它们 var value = array[a]; array[a] = array[b]; array[b] = value; } if(b - a + 1 > 2){ // 如果数组长度 > 2，就按三分之一来排序 var t = (b - a + 1)/3; stoogeSortBetween(array, a, ceil(b - t)); stoogeSortBetween(array, floor(a + t), b); stoogeSortBetween(array, a, ceil(b - t)); } }

function stoogeSort(@array){ stoogeSortBetween(array, 0, count(array) - 1); }

var array = [2, 5, 8, 3, 4, 7, 6, 1, 9, 11, 10, 17]; stoogeSort(array); debug(array); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 17]

这种排序虽然写起来简单（而且难得地是原地的，也就是不额外占内存），实际上效率相当低。要看清这一点，我们来数递归调用的次数。由于每次调用所做的操作（可能的一次交换，以及一次对剩余待排长度的判断）与数组长度无关，操作数将直接是调用次数的一个倍数。所以我把这个次数记作 C(n)。

由于函数会在原长度 2/3 的长度上自我调用三次，我们得到下面的递推公式： C(n) = 3 * C(2n/3)。于是，为了知道要乘多少次 3，就得找到满足 (2/3)^k * n = 2 的数 k，届时便有 C(n) = 3^k * C(2)（而 C(2) 不过是交换两个元素所需的操作数）。

这给出 n/2 = (3/2)^k，于是 log(n/2) = k * log(3/2)，即 k = log(n/2)/log(1.5)。于是得到 C(n) = 3^(log(n/2)/log(1.5)) * C(2)，再稍微摆弄一下对数和指数，就得到 C(n) = (n/2)^(log(3)/log(1.5)) * C(2)，因此 C(n) = O(n^(log(3)/log(1.5))) ≈ O(n^2.71)。

所以这段代码的复杂度是多项式级的，但比简单排序的复杂度还大（例如插入排序，它是 O(n^2) 的）。总之，这种排序不但直觉上更绕，跑起来还比那些简单排序更慢。所以可以说，它就是个废物！

练习： 好奇的读者可以想想：如果改成按''四分之一''来排会怎么样，也就是每次排两个四分之一组成的一段（就像上面每次排两个三分之一那样）。还可以走得更远：五分之一，等等。特别地会发现，如果切成 k 段而 k>3，那就得排不止 k 次，于是在每一步的排序次数上吃亏，却在每一步数组长度的缩减上占便宜。如果一路推到 k = count(array)/2，我们会得到哪一种经典排序？

二阶递推：C(n)=f(C(n-1) , C(n-2)

遗憾的是，世界并不总像上面那么美好，有时会碰到更复杂的递推。斐波那契数列就是一个经典例子：递归教程已经给你讲过一种方法，用来降低下面这种朴素写法带来的复杂度，但这种情形在别的算法里也会出现，所以我还是拿它当例子讲一讲。

斐波那契

斐波那契数列在数学上由 u(0)=1、u(1)=1 以及 n>1 时 u(n) = u(n-1) + u(n-2) 定义。翻译成代码就是：

function fibonacci(n){ if(n 1 时函数会以 n-1 和 n-2 为参数调用自身两次，我们有 C(n) = 2 + C(n-1) + C(n-2)（对 fibonacci(n-1) 和 fibonacci(n-2) 的这两次调用，加上这两次调用各自引发的递归调用）。另外，n 等于 0 或 1 时没有递归调用，所以 C(0) = 0、C(1) = 0。注意这个递推关系可以改写成 C(n) + 2 = (C(n-1) + 2) + (C(n-2) + 2)。于是我们令 u(n) = C(n) + 2，问题就变成研究下面这个数列：

u(0) = 2, u(1) = 2, 且 n>1 时 u(n) = u(n-1) + u(n-2)

可以看出，这个数列正好是斐波那契数列的两倍：斐波那契数列几乎就是它自己的代价。

好，接下来就是研究这个东西了。为此，我直接甩给你一个定理；想要解释的人，欢迎到游戏的聊天里找我：

“定理：设 u(n) 是 ℝ 中的一个数列，且对 n > 1 满足 u(n) = au(n-1) + bu(n-2)。若 a²+4b > 0，则存在 ℝ 中的 c 和 d，使得 u(n) = c(x_1)^n + d(x_2)^n，其中 x_1 和 x_2 是 X²-aX-b 的两个根。若 a²+4b = 0，则存在 ℝ 中的 c 和 d，使得 u(n) = (c + dn)(x_1)^n，其中 x_1 是 X²-aX-b 的唯一根。”

在我们关心的情形里，a = 1、b = 1。X² - X - 1 的根是 x_1 = (1+sqrt(5))/2（也就是所谓的黄金比例）和 x_2 = (1-sqrt(5))/2。于是定理告诉我们，存在 c 和 d，使得 u(n) = c ((1+sqrt(5))/2)^n + d ((1-sqrt(5))/2)^n。我们用 u(0) 和 u(1) 的值把 c 和 d 算出来：

2 = u(0) = c ((1+sqrt(5))/2)^0 + d ((1-sqrt(5))/2)^0 = c + d

2 = u(1) = c ((1+sqrt(5))/2) + d ((1-sqrt(5))/2)

把这两个方程稍微整理一下，就得到：

c = 1 + 1/sqrt(5) 以及 d = 1 - 1/sqrt(5)

于是 u(n) = (1 + 1/sqrt(5)) * ((1+sqrt(5))/2)^n + (1 - 1/sqrt(5)) * ((1-sqrt(5))/2)^n)，最终便得到：

C(n) = (1 + 1/sqrt(5)) * ((1+sqrt(5))/2)^n + (1 - 1/sqrt(5)) * ((1-sqrt(5))/2)^n) - 2。

好吧，这个公式挺难看的，因为我把计算过程都写出来了；不过其中真正重要的部分在下面。其实做复杂度分析时，完全可以不去算那些常数！

剩下要记住的就是这些：n 趋于无穷时 ((1-sqrt(5))/2)^n 趋于 0（因为 0 ((1+sqrt(5))/2)^n 趋于无穷（因为 1 fibonacci 函数的复杂度是 O(((1+sqrt(5))/2)^n)：这样写出来的算法是指数复杂度，而递归教程里给出的算法是线性时间的。'''所以很重要的一点是'''：碰到这类递推时，一定要看看能不能用上记忆化或者尾递归！

顺便说一句，在这个具体例子里我们还做得更好（记忆化？收起来吧，Pump）：我们给出了一个常数时间就能算出函数值的算法（确实会因为经过浮点数而有舍入误差，但一个 round 就能搞定）！

function fibonacci(n){ return (1 + 1/sqrt(5))/2 * ((1+sqrt(5))/2)n + (1 - 1/sqrt(5))/2 * ((1-sqrt(5))/2)n; }

形式幂级数

到这里就真的要动数学了。快逃吧，可怜的家伙们！

下面我要借助一个例子，介绍一种相当强大的组合学技巧，用来研究更复杂的递推关系。

Dyck 路径

假设你有一张像下面这样的地图，蓝色格子和红色格子在水平方向上相隔 n 格（对我们的韭葱来说，这就是一条长度为 2n 的路径）：

!Dyck_grid

而你出于某种神秘的原因，想找出所有从蓝色格子通到红色格子、且从不逆向而行（也就是从不往左退）的路径（这种路径叫做Dyck 路径）。于是每一步有两种可能的走法：往右下走，或者往右上走。

为此，我们来写一个递归算法，它的输入是允许的向下和向上移动次数（注意，既然从最上面出发，那只有先下去过才能往上走）：

function getDyckPaths(n){ return getDyckPathsAux(0,n); }

getDyckPaths(3); // 给出 down, down, down, up, up, up], [down, down, up, down, up, up], [down, down, up, up, down, up], [down, up, down, down, up, up], [down, up, down, up, down, up getDyckPaths(17); // 给出从蓝色格子到红色格子的所有路径（好吧，前提是它没有把 2000 万操作数远远撑爆）

这个函数的复杂度不好估：一般来说确实有两种选择（往右下或往右上），所以可能会以为是指数复杂度；但实际上，一旦走到绿色格子上，怎么走就被定死了：

!Dick_grid_forced_moves

在浅绿色格子上只能往上走，在深绿色格子上只能往下走。

所以我们来数一数可能的路径条数，以此研究复杂度。记 N(n) 为 getDyckPaths(n) 返回的路径条数，也就是在同一行上相隔 n 格的两个格子之间、始终向右走的路径条数。

如果 n = 0，就只有一条路径：空路径（原地不动的那条）。否则，对每一条路径都有两种情况：要么它在到达终点之前又回到了起点和终点所在的那一行，要么它没有回去过。

如果它没有回去过，我们来看起点和终点所在那一行正下方的一行：这条路径会先往下走，之后再也不会越到这第二行之上（否则它就会回到第一行），最后再往上走。

!Dick_grid_case1

这种情况下，问题就归结为数浅蓝色格子和粉色格子之间的 Dyck 路径：一共有 N(n-1) 种可能。

如果它回到了第一行，那可能不止回去一次。设 k 是使得路径在 2k 步之后回到第一行的最大整数（要回到同一高度，上行和下行的次数必须一样多，所以才是 2k 这种形式）。于是可以把这条路径拆成两条更小的 Dyck 路径：

!Dick_grid_case2

如果强制要求经过紫色格子，我们就得到两条 Dyck 路径：一条从蓝色格子到紫色格子，另一条从紫色格子到红色格子。于是第一条路径有 N(k) 种可能，第二条有 N(n-k-1) 种（确实如此：我们取的是尽可能大的 k，所以在紫色格子和红色格子之间，路径不会再回到第一行，这就归到了前一种情况），总共就是 N(k)*N(n-k-1) 种。

于是可以写出：N(n) = N(n-1) + somme(N(k)N(n-k-1), k=1..n-1)（somme 即求和），这就给出递推公式 N(n) = somme(N(k)N(n-k-1), k=0..n-1)。

然后……我们就有点犯难了。这个递推公式乍一看一点也不好用，里面又是一个大求和，又是乘积。而这正是数学登场的时候！

我们来看下面这个（形式）级数（我不会讨论它的收敛性）： S(X) = somme(N(n) X^n, n=0..infinity)。于是有：

!Dyck_calculs_1

眼熟的话（当然，得有点经验）能认出这是一个卷积乘积，于是得到：

!Dyck_calculs_2

这样一来，问题就归结为借助这个关系把 S 表示成 X 的函数。为此注意到，S(X) 满足一个二次方程，判别式为 1-4X。于是取 S(X)= (1-sqrt(1-4X))/2X（可以证明另一个解不合适：它的主导项会是 1/X，那就全乱套了）。

那怎么从这里得到 N(n) 的值呢？靠一个了不起的工具：（幂）级数展开。这里我们有：

!Dyck_calculs_3

而在这个展开式中，按定义，各项系数正是 N(i)。于是我们得到下面这个漂亮的公式：N(n) = (2n)!/((n+1)!n!)。这些数就是所谓的''卡塔兰数''。

由此可以直接得出复杂度：对找到的每一条路径，我们都得通过添加与路径长度一样多的元素来把它造出来，也就是 2n 个。于是复杂度会是 O(2n * (2n)!/((n+1)!n!) = O(4^n / sqrt(n))（这两个 O 之间等价关系的推导我就不折磨你了，想知道的话，它来自斯特林公式）。相比一开始可能猜到的指数复杂度，我们省下了一个 sqrt(n) 的因子。这不算多，但也聊胜于无。

别被这一个例子误导：难的地方很少在“级数展开”这一步。通常麻烦的是如何从递推公式得到一个函数方程或微分方程，再把它解出来。这个工具相当强大，但有时候需要很强的数学功底！

呼。好了，当我们不再满足于“咳咳，看上去像是平方级的吧”、而是稍微认真一点分析复杂度时会遇到什么，你已经见识过了。

那就可以进入那些你永远不会遇到的复杂度了！

怪物级的情形

正常情况下你不会碰到这些情形，但这不表示它们不存在！这一节只是想说明：有时候复杂度可以大得吓人。它某种意义上只是聊备一格：如果你的算法有这种量级的复杂度，那除了极小的输入之外，你基本别指望能让它跑完。

阿克曼函数

这个函数是 Ackermann 创造的（名字就是这么来的），主要出于理论上的考虑：它在历史上是最早的几个非原始递归函数的例子之一（另一个是苏丹函数）。

function Ackermann(m,n){ if(m === 0) return n + 1; if(n === 0) return Ackermann(m - 1, 1); return Ackermann(m - 1, Ackermann(m, n - 1)); }

这个函数究竟算的是什么，远不是一眼就能看出来的。甚至连它为什么一定会停下来都不明显。其实可以这样证明它会停：在整数对上引入一个''字典序''：当 aAckermann(m, n - 1) 确实是在更小的整数对上调用，因为 n-1Ackermann(m - 1, Ackermann(m, n - 1)) 也是在更小的整数对上调用，因为 `m-1Ackermann(4,n) = 2^(2^(...)) - 3，其中乘方迭代了 n 次：对给定的 m，函数会把它在 m-1 时所做的运算重复 n 次。

那么下面这个函数的复杂度又该怎么说呢？

function A(n){ return Ackermann(n,n); }

先注意一点：函数对它返回的值所做的唯一操作，就是在 m 等于 0 的情况下加 1。比如对 A(2)，计算过程大致是这样的：

Ackermann(2,2) = Ackermann(1, Ackermann(2,1)) = Ackermann(1, Ackermann(1, Ackermann(2,0))) // n = 0 的情况 = Ackermann(1, Ackermann(1, Ackermann(1,1))) = Ackermann(1, Ackermann(1, Ackermann(0, Ackermann(1, 0)))) // n = 0 的情况 = Ackermann(1, Ackermann(1, Ackermann(0, Ackermann(0, 1)))) // m = 0 的情况 = Ackermann(1, Ackermann(1, Ackermann(0, 2))) // Ackermann(0,1) 等于 2，替换掉：我们做了一次加法。 = Ackermann(1, Ackermann(1, 3)) //Ackermann(0,2) 等于 3，替换掉：第二次加法。 = Ackermann(1, Ackermann(0, Ackermann(1,2))) = Ackermann(1, Ackermann(0, Ackermann(0, Ackermann(1,1)))) = Ackermann(1, Ackermann(0, Ackermann(0, Ackermann(0, Ackermann(1,0))))) // n = 0 的情况 = Ackermann(1, Ackermann(0, Ackermann(0, Ackermann(0, Ackermann(0,1))))) // m = 0 的情况 = Ackermann(1, Ackermann(0, Ackermann(0, Ackermann(0, 2)))) // Ackermann(0,1) 等于 2，替换掉：第三次加法。 = Ackermann(1, Ackermann(0, Ackermann(0, 3))) // Ackermann(0,2) 等于 3，替换掉：第四次加法。 = Ackermann(1, Ackermann(0, 4)) // Ackermann(0,3) 等于 4，替换掉：第五次加法。 = Ackermann(1, 5) // Ackermann(0,4) 等于 5，替换掉：第六次加法。 = Ackermann(0, Ackermann(1,4)) = Ackermann(0, Ackermann(0, Ackermann(1,3))) = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(1,2)))) = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, Ackermann(1,1))))) = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, Ackermann(0, Ackermann(1,0)))))) // n = 0 的情况 = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, Ackermann(0, Ackermann(0,1)))))) //m = 0 的情况：终于可以做我们的加法了！ = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, Ackermann(0, 2))))) // 第七次加法 = Ackermann(0, Ackermann(0, Ackermann(0,Ackermann(0, 3)))) // 第八次加法 = Ackermann(0, Ackermann(0, Ackermann(0,4))) // 第九次加法 = Ackermann(0, Ackermann(0, 5)) // 第十次加法 = Ackermann(0, 6) // 第十一次加法 = 7 // 第十二次加法，计算结束。

所以，算一个 A(2) 用了三十来行计算、十来次加法。既然最终结果完全靠一次次加 1 得到，A(n) 的复杂度会比 A(n) 本身还大，而这甚至没法用常见的运算写出来！所以我们给不出一个“简单”的复杂度。

实际操作起来嘛……A(2) 还是算得动的，我刚刚就在这儿算了一遍，总共 27 次递归调用和 12 次加法。A(3) 等于 61，算它需要 2432 次递归调用。A(4) 等于 2^(2^65536))-3，想算它只会让韭葱直接崩溃。所以它涨得非常、非常快！

叙拉古数列

由某个起始整数确定的叙拉古数列，是一个在数学上如下定义的数列：

u(0) = 一个正整数 n u(i) = 若 u(i-1) 为偶数，则为 u(i-1)/2 否则为 3*u(i-1) + 1

注意，如果数列在某一刻取到值 1，那么之后它就会周期性地重复同样的值：从 1 到 4，再到 2，再回到 1，如此循环。

于是很容易写出一个函数：输入起始整数，计算对应的叙拉古数列，直到落到 1 为止：

function syracuse(n){ if(n === 1) {return "计算结束";} if(n%2 === 0) { return syracuse(n/2); } else { return syracuse(3*n + 1); } }

不管输入是什么，这个函数都会停下来吗？呃……我不知道。其实谁也不知道：这个函数是否终止，是一个悬而未决的问题！所以目前根本没法给出这种函数的复杂度。因此要当心：一个递归函数看着简单，不等于它的复杂度就容易分析……