【译】JS递归初步

原创 老姚 随笔 我也来说说系列 408阅读 2017-05-08 00:23:23 举报

注:本文节选于Dan Mantyla的《Functional Programming in JavaScript》一书的第二章。是递归一个简单初步。后续会翻译稍微深入的章节。另外,个人英文水平有限,敬请包涵。
递归很可能是最有名的函数式编程技巧。如果你至今还了解它,可以简单说下,递归函数就是调用自身的函数。
当一个函数调用自身时,奇怪的事情会发生。它运作起来既像一个循环(多次执行同样的代码),又像一个函数栈。
使用递归要非常小心,避免无限循环(或者说,无限递归)。就像循环一样,必须有一个条件来判断何时停止。它被称为递归的基本情形(base case)。
一个例子如下:
javascript 代码

把任何一个循环转化为递归算法和把任何一个递归算法转化为循环,都是可能的。对于一些不适合使用循环的一些情况,使用递归算法是更合适的,并且几乎是必需的。
一个很好的例子就是树遍历。使用递归函数不难实现遍历一棵树,而使用循环就相对复杂,还需要维护一个栈。那样就与函数式编程的精神相违背。
javascript 代码

译注:此处代码应该是伪代码。原作者有时凭感觉写代码,我给出两个版本的测试。
版本一dom树,测试案例:
html 代码

版本2,自己封装节点
javascript 代码

分而治之(Divide and conquer)

除了不使用for和while循环来迭代外,递归还有其他有趣的地方。有一个算法设计被称为“Divide and conquer”,递归地把问题拆分成更小的相同问题,直到它们足够小到可以解决。
一个具有历史意义的例子就是Euclidan算法,求两个数的最大公约数。
javascript 代码

在理论中,“Divide and conquer”算法工作的相当好,但是有没有在真实世界中使用的例子呢?有的,JS中的数组排序的方法不是十分好,不仅仅因为它的排序是在原数组上进行的(这就意味着数据不是不可变的),也因为它是不可靠的和僵硬的。如果使用“Divide and conquer”,我们可以做得更好。
归并排序算法使用“Divide and conquer”算法高效地给数组排序。它数组分成更小的子数组,递归排序后,然后再把子数组合并起来。
JS完整实现大概需要40行代码。然而使用伪代码很少,如下:
javascript 代码

译注:说是伪代码,倒不是很“伪”,下面是个人补充的完整算法:
javascript 代码

本文完。

评论 ( 1 )
最新评论