转载

谈谈递归

什么是递归

小时候,我们都听过下面这则故事:

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

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

留心观察一下我们身边的世界,其实递归无处不在, 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)。

所以经过尾递归优化后,使得递归计算可以跟 whilefor-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 也是熟悉语言的好方法。

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

原文  http://io.upyun.com/2016/04/05/recursion/
正文到此结束
Loading...