注: 本文节选于 Dan Mantyla 的Functional Programming in JavaScript一书的第二章. 是递归一个简单初步. 后续会翻译稍微深入的章节. 另外, 个人英文水平有限, 敬请包涵.
递归很可能是最有名的函数式编程技巧. 如果你至今还了解它, 可以简单说下, 递归函数就是调用自身的函数.
当一个函数调用自身时, 奇怪的事情会发生. 它运作起来既像一个循环 (多次执行同样的代码), 又像一个函数栈.
使用递归要非常小心, 避免无限循环 (或者说, 无限递归). 就像循环一样, 必须有一个条件来判断何时停止. 它被称为递归的基本情形 (base case).
一个例子如下:
javascript 代码
- var foo = function(n) {
- if (n <0) {
- // 基本情形
- return 'hello';
- } else {
- // 递归情形
- return foo(n - 1);
- }
- }
- console.log(foo(5));
把任何一个循环转化为递归算法和把任何一个递归算法转化为循环, 都是可能的. 对于一些不适合使用循环的一些情况, 使用递归算法是更合适的, 并且几乎是必需的.
一个很好的例子就是树遍历. 使用递归函数不难实现遍历一棵树, 而使用循环就相对复杂, 还需要维护一个栈. 那样就与函数式编程的精神相违背.
javascript 代码
- var getLeafs = function(node) {
- if (node.childNodes.length == 0) {
- // 基本情形
- return node.innerText;
- } else {
- // 递归情形
- return node.childNodes.map(getLeafs);
- }
- };
译注: 此处代码应该是伪代码. 原作者有时凭感觉写代码, 我给出两个版本的测试.
版本一 dom 树, 测试案例:
html 代码
- <ul id="tree">
- <li>1</li>
- <li>2
- <ul>
- <li>2.1</li>
- <li>2.2</li>
- </ul>
- </li>
- <li>3
- <ul>
- <li>3.1</li>
- <li>3.2
- <ul>
- <li>3.2.1</li>
- </ul>
- </li>
- <li>3.3</li>
- </ul>
- </li>
- </ul>
- <script>
- var getLeafs = function(node) {
- if (node.children.length == 0) {
- return node.innerText;
- } else {
- return [].map.call(node.children, getLeafs);
- }
- };
- alert(getLeafs(tree));// 数组是嵌套数组的, 应该要展平
- </script>
版本 2, 自己封装节点
javascript 代码
- var TreeNode = function(text) {
- this.innerText = text;
- this.childNodes = [];
- }
- TreeNode.prototype.appendChild = function(child) {
- this.childNodes.push(child);
- return this;
- }
- var root = new TreeNode('root');
- var node1 = new TreeNode('1');
- var node11 = new TreeNode('1.1');
- var node111 = new TreeNode('1.1.1');
- var node12 = new TreeNode('1.2');
- var node2 = new TreeNode('2');
- root.appendChild(node1).appendChild(node2);
- node1.appendChild(node11).appendChild(node12);
- node11.appendChild(node111);
- var getLeafs = function(node) {
- if (node.childNodes.length == 0) {
- return node.innerText;
- } else {
- return node.childNodes.map(getLeafs);
- }
- };
- console.log(getLeafs(root).toString().split(','));// 简单展平
分而治之 (Divide and conquer)
除了不使用 for 和 while 循环来迭代外, 递归还有其他有趣的地方. 有一个算法设计被称为 "Divide and conquer", 递归地把问题拆分成更小的相同问题, 直到它们足够小到可以解决.
一个具有历史意义的例子就是 Euclidan 算法, 求两个数的最大公约数.
javascript 代码
- function gcd(a, b) {
- if (b == 0) {
- // 基本情形
- return a;
- } else {
- // 递归情形
- return gcd(b, a % b);
- }
- }
- console.log(gcd(12, 8));
- console.log(gcd(100, 20));
在理论中,"Divide and conquer" 算法工作的相当好, 但是有没有在真实世界中使用的例子呢? 有的, JS 中的数组排序的方法不是十分好, 不仅仅因为它的排序是在原数组上进行的 (这就意味着数据不是不可变的), 也因为它是不可靠的和僵硬的. 如果使用 "Divide and conquer", 我们可以做得更好.
归并排序算法使用 "Divide and conquer" 算法高效地给数组排序. 它数组分成更小的子数组, 递归排序后, 然后再把子数组合并起来.
JS 完整实现大概需要 40 行代码. 然而使用伪代码很少, 如下:
javascript 代码
- var mergeSort = function(arr) {
- if (arr.length < 2) {
- // 基本情形: 0 或者 1 个元素的数组是不需要排序的
- return arr;
- } else {
- // 递归情形: 拆分数组, 排序, 然后合并
- var middle = Math.floor(arr.length / 2);
- // divide
- var left = mergeSort(arr.slice(0, middle));
- var right = mergeSort(arr.slice(middle));
- // conquer
- // 使用一个辅助函数把两个数组合并起来, 并返回一个新数组
- return merge(left, right);
- }
- };
译注: 说是伪代码, 倒不是很 "伪", 下面是个人补充的完整算法:
javascript 代码
- var mergeSort = function(arr) {
- if (arr.length < 2) {
- // 基本情形: 0 或者 1 个元素的数组是不需要排序的
- return arr;
- } else {
- // 递归情形: 拆分数组, 排序, 然后合并
- var middle = Math.floor(arr.length / 2);
- // divide
- var left = mergeSort(arr.slice(0, middle));
- var right = mergeSort(arr.slice(middle));
- // conquer
- // 使用一个辅助函数把两个数组合并起来, 并返回一个新数组
- return merge(left, right);
- }
- };
- var merge = function(left, right) {
- var result = [], i = 0, j = 0;
- // 两边选出较小的那个
- while(i < left.length && j < right.length) {
- var which = left[i] < right[j] ? left[i++] : right[j++];
- result.push(which);
- }
- // 如果左边剩余
- while (i < left.length) {
- result.push(left[i++]);
- }
- // 如果右边剩余
- while (j < right.length) {
- result.push(right[j++]);
- }
- return result;
- };
- var r = mergeSort([1, 9, 7, 3, 8, 5, 2, 4, 6]);
- console.log(r);
本文完.
来源: http://www.qdfuns.com/article/17398/f942fbd5141f457c32edf17ed339e3e6.html