Javascript 高性能之递归，迭代，查表法详解及实例_网络技术

Javascript 高性能之递归，迭代，查表法详解及实例

发布时间 - 2026-01-10 22:22:54 点击率：次

Javascript 高性能之递归，迭代，查表法详解

递归

概念：函数通过直接调用自身，或者两个函数之间的互相调用，来达到一定的目的，比如排序，阶乘等

简单的递归

阶乘

function factorial(n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

递归实现排序

/*
  排序且合并数组
 */
function myMerge(left, right) {
  // 保存最后结果的数组
  var res = [];

  // 有一个数组结束了就结束排序，一般情况下，两个数组长度应该保持一样
  while (left.length > 0 && right.length > 0) {
    if ( left[0] < right[0] ) {
      // 把left第一个成员删除，存储到新数组res中
      res.push(left.shift());
    } else {
      res.push(right.shift());
    }
  }

  // 如果还有剩余直接合并到新数组
  return res.concat(left).concat(right);
}

/*
  递归方式
 */
function recursion(items) {
  if (items.length == 1) {
    return items;
  }

  var middle = Math.floor(items.length / 2),
    left = items.slice(0, middle), // 取数组前半部分
    right = items.slice(middle);  // 取数组后半部分

  // 递归排序
  return myMerge(recursion(left), recursion(right));
}

迭代

每个浏览器对递归都有调用栈上限的问题，且如果不小心使用也很容易造成死循环导致程序崩溃。如果考虑到性能问题，可以使用迭代来代替递归，因为运行循环总比反复调用函数的开销少很多

/*
  迭代方式，不使用递归，可以避免出现栈溢出问题
 */

function iteration(items) {
  if (items.length == 1) {
    return items;
  }

  var work = [];

  // 将items成员全部转化成数组，保存到数组中
  for (var i = 0, len = items.length; i < len; i++) {
    work.push([items[i]]);
  }
  work.push([]); // 数组长度为奇数时

  // 迭代
  for (var lim = len; lim > 1; lim = (lim + 1) / 2) {
    for (var j = 0, k = 0; k < lim; j++, k+=2) {
      work[j] = myMerge(work[k], work[k + 1]);
    }
    work[j] = [];  // 数组长度为奇数时
  }

  return work[0];
}

/* 迭代过程分析
  假设： var test = [1, 3, 9, 7, 4, 8, 6, 5, 0, 2]; // len == 10
  work = [[1], [3], [9], [7], [4], [8], [6], [5], [0], [2], []]; // len == 11;

  // 迭代(二分法)
  a) lim: 11 > 1
    1) k = 0, work[0] = myMerge([1], [3]) ==> work[0] = [1, 3]
    2) k = 2, work[1] = myMerge([9], [7]) ==> work[1] = [7, 9]
    3) k = 4, work[2] = myMerge([4], [8]) ==> work[2] = [4, 8]
    4) k = 6, work[3] = myMerge([6], [5]) ==> work[3] = [5, 6]
    5) k = 8, work[4] = myMerge([0], [2]) ==> work[4] = [0, 2]
    > 在后面添加个空数组是为了数组长度为奇数时的情况，能有个对象做比较，否则会出现越界错误
  b) lim: 6 > 1, work = [[1,3], [7,9], [4,8], [5,6], [0,2], []];
    1) k = 0, work[0] = myMerge([1,3], [7,9]) ==> work[0] = [1, 3, 7, 9]
    2) k = 2, work[1] = myMerge([4,8], [5,6]) ==> work[1] = [4, 5, 6, 8]
    3) k = 4, work[2] = myMerge([0,2], [])  ==> work[2] = [0,2]
    > 最后一个[]会被myMerge函数给合并，所以不用担心添加的空数组对后续产生影响
  c) lim: 3 > 1, work = [[1, 3, 7, 9], [4, 5, 6, 8], [0, 2], []];
    1) k = 0, work[0] = myMerge([1, 3, 7, 9], [4, 5, 6, 8]) ==> work[0] = [1,3,4,5,6,7,8,9]
    2) k = 2, work[1] = myMerge([0, 2], []) ==> work[1] = [0, 2]
  d) lim: 2, work = [[1,3,4,5,6,7,8,9], [0,2], []];
    1) k = 0, work[0] = myMerge([1,3,4,5,6,7,8,9], [0,2]) ==> work[0] = [0,1,2,3,4,5,6,7,8,9]
    > 至此排序整个过程全部完成

  // 关键点
  a) 将数组中的每个元素数组化，以便后续存放已经排好序的元素
  b) k的取值，k+=2, 每次取两个数组进行比较，形成一个新的数组
  c) 一定要在比较完之后附加空数组，否则会在数组个数为奇数个的时候出现访问越界错误
  d) 最外层循环的lim的取值, lim = (lim + 1) / 2即原数组长度的一半，作为内循环终止的条件


*/

递归优化，查表法-Memoization(记忆): 函数可以用对象去记住先前操纵的成果，从而能避免无谓的运算

避免重复工作，将执行过的运算或操作，缓存起来，如果后续有相同的操作可直接从缓存中查找，没有则进行递归，可大大减少递归的工作量，提高性能。

var count = 0;

function factorial(n) {

  console.log("factorial count = " + count++);

  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

// var f1 = factorial(6);
// var f2 = factorial(5);
// var f3 = factorial(4);
// >>>>> 结果是函数被调用了：18次

/*
  递归优化：查表法，通过缓存
 */
function memFactorial(n) {

  console.log("memFactorial count = " + count++);

  // JS中函数即可视为一个对象，所以可以直接通过函数名＋点语法给此对象添加属性
  if (!memFactorial.cache) { 
    memFactorial.cache = {
      "0": 1,
      "1": 1
    };
  }

  // hasOwnProperty(n)可以判断对象中是否存在该属性，不会查找原型（但是"in"会先查实例再原型）
  if (!memFactorial.cache.hasOwnProperty(n)) {
    // 缓存中不存在的情况下再进行递归，并且将新数组缓存起来
    memFactorial.cache[n] = n * memFactorial(n - 1);
  }

  // 最终数据都可以在缓存中找到
  return memFactorial.cache[n];
}


var f1 = memFactorial(6);
var f2 = memFactorial(5);
var f3 = memFactorial(4);

// >>>>> 结果是函数被调用了：只有8次，大大的减少了函数被调用的次数

Memoization通用版，但不建议使用，建议自己手动在普通版中实现函数内容

通用版需要缓存特定参数的函数调用结果，即，传入的参数不同，调用函数的时候，其结果需要缓存起来

/*
  递归优化通用版，性能不如普通版，需要缓存每次调用结果, 即内部函数  
 */ 
function memoize(func, cache) {
  // 缓存池
  cache = cache || {};  // 没有则新建

  var result = function(arg) {
    // console.log("memoize count = " + count++);
    if (!cache.hasOwnProperty(arg)) {
      cache[arg] = func(arg);
    }
  };

  return result;
}  

// 使用
// 将阶乘函数缓存起来
// 只是优化了cache的通用性，但损失了一部分性能
var memOpfactorial = memoize(factorial, {"0": 1, "1": 1});

var f1 = memOpfactorial(6);
var f2 = memOpfactorial(5);
var f3 = memOpfactorial(4);

// 结果次数依旧是：18次。因此不推荐使用

总结

谨慎使用递归，以防造成死循环，程序崩溃，或者调用栈溢出；
学会使用迭代来替代递归，可以避免递归调用栈或死循环问题出现；
查表法，递归的优化版：Memoization减少重复工作，提升性能。但不推荐使用通用版，相比普通版会损失部分性能。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# Javascript # 递归 # 迭代 # 查表法 # JS # 迭代高性能 # 高性能 # js中递归函数的使用介绍 # JavaScript的递归之递归与循环示例介绍 # JS 树形递归实例代码 # JavaScript Array Flatten 与递归使用介绍 # JavaScript 语言的递归编程 # JS中递归函数 # 总结javascript中的六种迭代器 # js数组的五种迭代方法及两种归并方法(推荐) # javaScript数组迭代方法详解 # JS的数组迭代方法 # 浅谈javascript 迭代方法 # JavaScript中的迭代器和生成器详解 # js 数组实现一个类似ruby的迭代器 # 推荐使用 # 长度为 # 但不 # 到新 # 组中 # 都有 # 有个 # 结果是 # 第一个 # 可以用 # 会在 # 也很 # 希望能 # 考虑到 # 可以直接 # 可以使用 # 大大的 # 在后面

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：Win10如何优化内存使用_Win10内存优化技巧【攻略】

下一篇：thinkphp项目怎么部署

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：Win10如何优化内存使用_Win10内存优化技巧【攻略】

下一篇：thinkphp项目怎么部署