UPYUN Engineering Blog

谈谈递归

2016/04/05 • WUKL

什么是递归

小时候，我们都听过下面这则故事：

从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事，讲的什么呢？「从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事，讲的什么呢？『从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事，讲的什么呢？……』」

这个故事自己套着自己，没完没了，像是某种特征在不断地重复，这就是递归了。

留心观察一下我们身边的世界，其实递归无处不在，GNU、PHP，多肉植物、松塔的螺线、向日葵的花盘、蕨类植物的叶子 ，平行镜中的像、拍自己的摄像机等等，都有某种自相似的特征。

在计算机科学里，递归指的是一种通过重复将问题分解为同类的子问题而解决问题的方法。套用程序的概念，就是函数执行过程中直接或间接地调用自身。

用递归来解决问题

由递归的概念可知，如果某个问题有一些自相似的特征，可以分解为子问题，那么它就可以被递归定义。如果问题被递归定义了，也差不多解决了。

我们来看一个具体例子：

假设现在有 5 个人、5 个座位，那这几个人的位置分布情况有几种。我们先来列举一下：

第 1 个人： 有 5 种选择
第 2 个人： 有 (5 - 1) 种选择
第 3 个人： 有 (5 - 2) 种选择
第 4 个人： 有 (5 - 3) 种选择
第 5 个人： 有 (5 - 4) 种选择

那么 5 个人总共的选择数是：

5 * (5 - 1) * (5 - 2) * (5 - 3) * (5 - 4)

同理，如果总共是 n 个人、n 个座位，那么所有可能的情况数 f(n) 可以表示为：

f(n) = n * (n - 1) * … * 2 * 1

这里的未知数 n 有无数种可能，我们不可能把所有的情况都列举出来，然后得到结果。要解决这样的问题，就要运用递归的思想，找到各个情况的共同模式，切分成小的有限的问题，然后尝试着把它描述出来。

我们先把 n <= 5 的情况列举出来：

f(1) =                 1
f(2) =             2 * 1
f(3) =         3 * 2 * 1
f(4) =     4 * 3 * 2 * 1
f(5) = 5 * 4 * 3 * 2 * 1

通过对比可以观察到一个现象：

f(1) = 1
f(2) = 2 * f(1)
f(3) = 3 * f(2)
f(4) = 4 * f(3)
f(5) = 5 * f(4)

我们找到了一个共同模式，描述出来就是，对于 f(n) 来说，它的值是参数 n 和前一步的值的乘积，前一步和后一步的参数之间相差 1，所以我们很自然就想到用这个 1 做切分，即：

f(n) = n * f(n - 1)

这样我们就定义了这个函数 f，它会在执行的过程中调用自己，又称为递归函数，用 JavaScript 实现就是这样：

var f = function(n) {
  return n * f(n - 1);
}

简单分析一下，这个函数每执行一次，参数 n 就少 1，最终它会到达 0，之后还会进一步到负数，看起来好像永远都得不到结果。

我们回到命题，当 n 到达 0 时，f(0) 指的就是「 在 0 个人、0 个座位时的位置分布情况」，没有意义，是 Empty product，值为 1。而 n 是负数时就更没有意义了，所以 n 应该是一个自然数：

f(0) = 1
f(n) = n * f(n - 1)

这里的 n = 0 就是递归函数 f 的一个临界条件（edge case），当达到临界条件时，递归函数继续执行没有意义，此时递归结束。在定义递归函数的时候，设定合适的临界条件很重要，否则容易陷入死循环。

相应的，我们的代码也要改变：

// 参数 n 是自然数，后文不再说明
var f = function(n) {
  if (n === 0) return 1;
  return n * f(n - 1);
}

如果不用 if-else switch ? : 之类的条件判断语句，能不能实现类似的效果呢？

var f = function(n) {
  return [1][n] || n * f(n - 1);
}

由此，我们就通过定义递归函数 f 描述了这个问题，对于任意的自然数 n，我们只需执行 f(n) 就可以得到答案。

用递归的思路来解决问题，并不是写出具体的求解步骤，而是试着把问题描述出来，考虑有哪些共同模式，怎么切分，何处结束，以及何处执行递归。

递归函数的优化

当 n = 5 时，我们把上面这个函数完整的执行过程模拟出来：

f(5)
5 * f(4)
5 * (4 * f(3))
5 * (4 * (3 * f(2)))
5 * (4 * (3 * (2 * f(1))))
5 * (4 * (3 * (2 * (1 * f(0)))))
5 * (4 * (3 * (2 * (1 * 1))))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

我们可以看到，随着 f(5) 这个函数的执行，需要记录的中间状态的数目一直在变，先增后减。在空间消耗上，表现就是栈先累积后收缩，整个计算过程空间复杂度是 O(n)，当 n 很大的时候会栈溢出（Stack overflow）。

我们思考一下另一种方案，刚才的执行是从 n 开始，一步步计算，直到临界条件 0 为止。现在试着倒过来，由 1 开始，一步步计算，直到 n 为止，当然，此时的临界条件也相应的变为「超过 n」。

实现起来应该就是这样：

var f = function(n) {
  return f2(n, 1, 1);
};

var f2 = function(n, i, result) {
  if (i > n) {
    return result;
  } else {
    return f2(n, i + 1, result * i);
  }
};

我们引入了另一个函数 f2 来完成从 1 到 n 的递归。函数 f2 在尾位置（也就是函数执行的最后）调用自身，这样的递归称为尾递归（Tail recursion）。

不少编程语言（包括 ES6）都支持对这样的函数进行空间优化，也叫尾递归优化（Tail-call optimization）。

具体是怎么进行尾递归优化的呢？

我们回顾一下函数 f2 的定义，因为函数 f2 每次执行的最后是函数调用，而下一步执行所需要的状态都是通过参数传递的，那么当前栈就可以清空被重用。比如，在计算第 3 步的时候，之前的第 1 步、第 2 步的中间状态都不需要了，只保留第 3 步执行需要的参数就行。

我们把优化后的步骤列出来：

f(5)
f2(5, 1, 1)
f2(5, 2, 1)
f2(5, 3, 2)
f2(5, 4, 6)
f2(5, 5, 24)
f2(5, 6, 120)
120

可以看出，这种方案随着计算的增加，消耗的空间一直不变，占用恒量的内存，和迭代程序一样，它的空间复杂度是 O(1)。

所以经过尾递归优化后，使得递归计算可以跟 while、for-loop 等迭代式计算的效率基本相当。

递归和不动点组合子

我们再来看一下目前的递归函数：

var f = function(n) {
  return [1][n] || n * f(n - 1);
}

它是通过在具名函数 f 体内，引用函数定义的变量名 f 来实现自我调用，我们只有在运行时才知道 f 是什么，这就带来了两个问题：

  1. 函数定义的变量名，是一个自由变量，很容易被改变，当然这个可以通过闭包的方式解决。
  2. 不适用于匿名函数。

我们需要另一种在函数体内完成自我调用的方法，即找到下面这个函数里的 self（注：arguments.callee 在 ES5 严格模式下不可用 ）。

function(n) {
  return [1][n] || n * self(n - 1);
}

// self = ?

既然不能使用自由变量的方式调用自身，我们可以选择约束变量，即把自身 self 通过参数的方式传进去。那么就会变成这样：

// 先声明我们需要的目标函数 fact
// fact(5) => 120
var fact;

// 这里引入了一个高阶函数 f，接收函数 self 作为参数
// self 是指向目标函数自身的函数，也就是 fact
// self = fact
var f = function(self) {
  return function(n) {
    return [1][n] || n * self(n - 1);
  };
};

fact = f(self);

因为 self = fact、fact = f(self)，所以：

self = f(self)

我们先暂停一下，打开计算器，随便输入一个数字，一直按 cos 键，经过 cos(cos(...cos(x))) 之后，输出结果会稳定于值 v ，也就是说：

v = cos(v)

此时，函数的参数和返回值相同，我们称这个值是这个函数的不动点（Fix-point）。

回到这个例子，我们现在知道 self 就是高阶函数 f 的不动点。

于是我们的问题就变成了找出函数 f 的不动点。

假设存在一个函数 Y，我们把函数 f 作为参数传给它后，它可以返回 f 的不动点 self，即：

self = Y(f)

前面我们已经知道，self 指向的就是 fact，那我们的目标函数 fact 也就可以通过 Y 得到：

fact = Y(f)

现在我们的问题变成了，找到这个 Y。

好，下面我们就从最初的函数起，一步一步推导出这个 Y。先来回顾一下最初的函数：

function(n) {
  return [1][n] || n * self(n - 1);
}

这里的 self 指向其所在函数自身，因为是匿名函数，没法直接引用定义，需要通过参数的方式传进去：

function(n, self) {
  return [1][n] || n * self(n - 1, self);
}

现在我们给这个函数绑定一个名字 f，这样就变成了：

var f = function(n, self) {
  return [1][n] || n * self(n - 1, self);
};

f(5, self)

刚才我们已经知道 self 指向的是自身，也就是现在的绑定名 f，即 self = f，因此我们在 f 调用的地方可以直接用 f 代替参数 self 传给 f(5, self) ，即：

var f = function(n, self) {
  return [1][n] || n * self(n - 1, self);
};

f(5, f) // => 120

现在这个函数虽然可用，但变成了一个二元函数，我们要的其实是一元函数，所以要做柯里化（Currying）。

先来看一下下面这个小例子，简单了解一下什么是柯里化：

var foo = function(x, y) {
  return x + y;
};
foo(1, 2) // => 3

foo = function(y) {
  return function (x) {
    return x + y;
  };
};
foo(2)(1) // => 3

// 像上面这样从 foo(x, y) 到 foo(y)(x) 的变化就是柯里化

现在对函数 f 做柯里化：

var f = function(self) {
  return function(n) {
    // 此时 self 是指向函数 f
    // 原来的 f 柯里化后调用方式变成了 f(f)(n)
    // 所以 self 也要相应的变为 self(self)(n - 1)
    return [1][n] || n * self(self)(n - 1);
  };
};

f(f)(5) // => 120

现在的问题是我们的函数里混杂了 self(self) ，应该将它拿到函数外部，通过参数的方式传给 f：

var g = function(h) {
  // 把原来 f 内部的 self(self) 拿出来，放到新声明的函数 x 里
  // 此时 x(n) 应该等于原来的 self(self)(n)
  // 再把 x 作为参数传回给 f
  var x = function(n) {
    return h(h)(n);
  };

  // 此时，函数 f 变回了最初的形式
  // f 的参数 self 也相应的变回了指向函数 f 的不动点
  var f = function(self) {
    return function(n) {
      return [1][n] || n * self(n - 1);
    };
  };

  return f(x);
};

g(g)(5) // => 120

现在我们可以把 f 拿出来放到函数 g 的外面：

var f = function(self) {
  return function(n) {
    return [1][n] || n * self(n - 1);
  };
};

var g = function(h) {
  var x = function(n) {
    return h(h)(n);
  };
  return f(x);
};

var fact = g(g);

fact(5) // => 120

函数 g 里面的 f 是一个自由变量，我们再做转化，让 f 也成为一个约束变量，即通过参数的方式传递。这就需要把函数 g 和 fact 定义的部分（即 g(g)）一起放入闭包 wrap 里：

var f = function(self) {
  return function(n) {
    return [1][n] || n * self(n - 1);
  };
};

var wrap = function(f) {
  var g = function(h) {
    var x = function(n) {
      return h(h)(n);
    };
    return f(x);
  };
  return g(g);
};

var fact = wrap(f);

fact(5) // => 120

这样转化后得到的函数 wrap，其实就是我们要找的 Y，把它单独拿出来：

var Y = function(f) {
  var g = function(h) {
    var x = function(n) {
      return h(h)(n);
    };
    return f(x);
  };
  return g(g);
};

精简一下，去掉所有的中间变量：

var Y = function(f) {
  return (function(g) {
    return g(g);
  })(function(h) {
    return f(function(n) {
      return h(h)(n);
    });
  });
};

用函数 f 测试一下吧：

var f = Y(function(self) {
  return function(n) {
    return [1][n] || n * self(n - 1);
  };
});

f(5) // => 120

但现在的它还有一个小缺点，就是只支持一个参数，我们再稍微改一下，让它支持任意参数：

var Y = function(f) {
  return (function(g) {
    return g(g);
  })(function(h) {
    return f(function() {
      return h(h).apply(null, arguments);
    });
  });
};

好了，这就是最终版 Y，我们拿之前实现的尾递归函数测试一下：

var f = Y(function(self) {
  return function(n, i, result) {
    if (i > n) {
      return result;
    } else {
      return self(n, i + 1, result * i);
    }
  };
});

var fact = function(n) {
  return f(n, 1, 1);
};

fact(5) // => 120

那现在我们就找到了这个 Y，它的正式名字叫 Y 组合子（Y combinator），最初被 Haskell Curry 发现，用于 λ 演算 。不过我们找到的这个 Y 和 Haskell Curry 最初发现的有点不一样，我们实现的是适用于 JavaScript 这种传值调用的语言，也叫做 Z 组合子，它还有一个更接近最初版的变体是这个样子的：

var Z = function(f) {
  return (function(g) {
    return function(x) {
      return f(g(g))(x);
    };
  })(function(g) {
    return function(x) {
      return f(g(g))(x);
    };
  });
}

Y 组合子是不动点组合子（Fix-point combinator）的一个实现，用于计算高阶函数的不动点。不动点组合子避免了把函数定义混淆在函数自身的命名空间内，使得程序执行过程更加流式（streamable）。它适用于任何支持匿名函数的语言，在匿名函数体内，因为没法引用到函数定义自身，没法递归，但有了不动点组合子后，我们只需把这个匿名函数稍加变化，作为参数传给它，就可以定义递归函数了。

递归和自产生程序

艾舍尔（M. C. Escher）著名的作品《画手》 ，看起来就像是自己在画自己。那是否也有这样一个程序，自己打印出自己呢？

我们还是以 JavaScript 作为演示语言，先来看下打印的方法：

console.log('hello')
// => hello

接着试着打印出上面这条语句：

console.log("console.log('hello')")
// => console.log('hello')

由此可以看到，虽然已经可以打印出程序，但打印出来的只是部分程序（只有参数部分），我们的目标是打印出整个程序。

仔细观察一下，这里存在着某种自相似的特征，即 打印"打印'打印'" 这样的形式，也就是说，可以用递归的思路来解决。但这里并不像上面这个例子这么直观地得到递归定义，我们先尝试模拟一下这种自相似结构，构造一个打印函数 print，在调用的时候把函数 print 作为参数传回给自身：

// 参数 s 是一个函数，打印前先转化成 String
function print(s) { console.log(s.toString()) }
print(print)
// => function print(s) { console.log(s.toString()) }

但现在有两条语句，我们用函数体代替函数名作为参数，从而合并为一条：

(function (s) { console.log(s.toString()) })(function (s) { console.log(s.toString()) })
// => function (s) { console.log(s.toString()) }

看来这样只打印出一半，我们稍作变化，让它打印出两半：

(function (s) { console.log(s.toString() + s.toString()) })(function (s) { console.log(s.toString() + s.toString()) })
// => function (s) { console.log(s.toString() + s.toString()) }function (s) { console.log(s.toString() + s.toString()) }

在 Javascript 里，操作符 + 只接受数值类型（Number）或字符串类型（String）的操作数，当作用于其他类型时，会先调用 valueOf() 或 toString() 进行转化。在这里，参数 s 是函数，s + s 会默认调用 s.toString() ，所以上面的语句可以简化为：

(function (s) { console.log(s + s) })(function (s) { console.log(s + s) })
// => function (s) { console.log(s + s) }function (s) { console.log(s + s) }

看起来已经很接近了，现在只需要把前后缺少的小括号加上去：

(function (s) { console.log( '(' + s + ')(' + s + ')' )})(function (s) { console.log( '(' + s + ')(' + s + ')' )})
// => (function (s) { console.log( '(' + s + ')(' + s + ')' )})(function (s) { console.log( '(' + s + ')(' + s + ')' )})

可以看到，我们成功地打印出了自身，而这个打印自身的程序，有个正式名字叫自产生程序（Quine，以逻辑学家 Willard van Orman Quine 命名），顾名思义，就是把程序自身的源码打印出来。

事实上，只要是具备打印功能的图灵完备语言都有自己的 Quine 程序，而且各种各样，几乎有无限多的版本。因为简单优雅的 Quine 程序往往需要用到一些语言技巧，所以找到这样的 Quine 也是熟悉语言的好方法。


最后，看完文章，对递归有没有比较清晰的认识呢，有什么想法，给我们留言吧。