函数的递归调用

递归(recursion)是经常遇到的一个概念。当函数调用自身,或调用另外一个函数,但这个函数的调用树中的某个地方又调用了自己时,递归就发生了。

对任何类型的程序来说,递归都是一个非常有用的技术——很多数学公式在本质上都是递归。而且,对树进行遍历时,递归也是非常有用的,这是一个可能会在 Web 程序中出现的构造。我们还可以使用递归深入理解函数在 JavaScript 中是如何工作的。

从最简单的开始。

普通命名函数中的递归

有很多常见的递归函数示例。其中一个是用于检测回文——相当于递归技术的“Hello World”。

回文的非递归定义是“一个短语,不管从哪个方向读都是相同的”,我们可以用它来实现一个函数,用于创建反向字符串并和字符串本身进行比较。但是复制字符串从多方面来产不是简洁的解决方案,其中一个原因就是需要分配并创建新的字符串。

通过利用回文的更多数学定义,我们要可以想出一个更简洁的解决方案,这些定义如下所示:

  1. 单个与零个字符都是一个回文。
  2. 如果字符串的第一个字符和最后一个字符相同。将这前后两个排除后,其它的字符串仍是一个回文的话,我们称原字符串是一个回文。

基于上述定义实现的代码:

运行结果,符合预期:
is_palindrome

方法中的递归

在这一小节,我们将回文检测函数数包装成一个对象的方法,这会便结构变得更复杂,因为会将递归函数变成一个匿名函数赋值给对象的一个属性,代码如下:

在该函数内,我们通过对象的charFunc.isPalindrome()属性递归调用了函数自身,我们不能像前一个例子中那样直接使用函数的名称进行调用,因为它根本就没用名称,代码关系如图:

method-recursion
图一:此时的函数,现在是一个方法,它通过对象的 isPalindrome 属性引用自身

这就是代码关系,但因为我们在函数上使用了非直接(indirect)引用——也就是 charFunc 对象的 isPalindrome 属性才能进行递归。这并不是明智之举。让我们看看为什么会有问题。

引用丢失的问题

前一个例子依赖于:一个进行递归调用的对象属性引用。与函数的实际名称不同,这种引用可能是暂时的,这种依赖方式会导致我们很混乱。

让我们修改一下前面的例子,添加一个新对象,假设是strFunc,该对象也引用charFunc对象上的匿名递归函数,代码如下:

运行报错:

lost_reference
图二:引用丢失,运行报错

我们来分解下代码,我们给strFunc对象复制了原来函数的引用(#1),所以现在charFunc.isPalindromegstrFunc.isPalindrome都引用了同样的匿名函数。图三展示了该关系图。A 部分(从图一中可以了解到)显示了 charFunc 对象创建后的结构,而 B 部分显示了 strFunc 对象创建后的结构。

lost_reference_pic
图三:两个对象引用相同的函数,但函数引用自身的时候只是能过其中一个函数。

所以,如果charFunc消失的话,会发生什么?strFunc能保留该匿名函数吗?我们重新给charFunc对象赋值了一个空对象(#2),图三所示的 C 部分。匿名函数仍然存在,而且可以通过strFunc.isPalindrome属性进行引用,但是charFunc.isPalindrome已经不存在了。而isPalindrome函数是通过原有的charFunc.isPalindrome属性引用进行递归调用自身的,所以函数在调用的时候出现错误。

通过完善原本对递归函数的精略定义,我们可以修复解决这个问题。在匿名函数中不再使用显式的charFunc引用,而是使用函数上下文(this)进行引用,救命如下:

谨记,当一个函数作为方法被调用时,函数上下文指的是调用该方法的那个对象。调 charFunc.isPalindrome() 时,this对象 引用的是charFunc;而调用 strFunc.isPalindrome() 时,this对象引用的则是samurai,都很好用。

使用函数上下文(this)可以使我们的isPalindrome方法更加强大,这种方式在刚开始声明方法的时候就应该使用。但是,问题真的解决了吗?……

内联命名函数

上一小节,我们想出的解决方案在函数作为对象的方法进行递归时是很完美的。但实际上,不管是否作为方法进行递归调用,使用函数上下文的这个技巧都是常见且可接受的方式。

但是,现在又有了另外一个问题。解决方案取决于:给对象定义方法时,该方法名称必须为isPalindrome()如果方法名称不一样会怎么样呢?或者如果该函数的其中一个引用不是对象属性又如何呢?我们的解决方案只能在特定的情况下才能使用,也就是将函数作为方法且所有方法的属性名称都一样。如何才能开发出更通过的匿名递归函数?

考虑一种特别的方式:如果我们给匿名函数取个名字会怎么样?

刚开始,这会让人感觉匪夷所思,作为方法使用的匿名函数有取名的必要吗?但是,使用表达式(function expression)定义函数时,函数名称是可选的(《JS权威指南》章节:4.3)。实际上,不管是作为 callback 定义的还是作为方法定义,给任何函数字面量取名都没有什么错。

这些函数不再是匿名函数了(anonymous)了,最好叫它们内联函数(inline function),从而避免使用匿名命名函数(anonymous named function)而产生矛盾。

下面的改进代码使用了这种技术:

运行结果,符合预期:

inline_function
使用内联函数改进后的代码运行结果

一切代码运行正常,因为清除charFunc对象的isPalindrome属性时,并没有影响给内联函数所取的用于递归调用的名字。

给匿名函数取名带来的威力可以进一步扩大。它甚至可以用于普通的变量赋值,如下所示:

运行结果:
identity of an inline function

尽管可以给匿名函数命名,但这些名称只能在自身函数内部才可见,内联函数的名称和变量名称有点像,它们的作用域仅限于声明它们的函数。并且,变量的name属性与内联函数的名称是一致的。

通过学习递归函数,我们知道了对函数引用的不同方式,包括以下几类

  • 通过名称引用
  • 作为一个方法进行引用(通过对象的属性名称)
  • 通过内联名称进行引用

发表评论

电子邮件地址不会被公开。 必填项已用*标注