`
maziheng
  • 浏览: 58166 次
  • 性别: Icon_minigender_1
  • 来自: 济南
社区版块
存档分类
最新评论

Js中通过记忆来优化递归方法

阅读更多

函数可以通过用对象去记住先前操作的结果,从而避免无谓的运算,这种优化称为 记忆(Memoization).

1、求数字之和基本递归方法

其中fibonacci为一般常用的递归方法,能满足基本要求,但存在重复调用的现象

var count =0;//记录遍历次数
var fibonacci = function(n){
	count++;
	return n<2 ? n:fibonacci(n-1)+fibonacci(n-2);
}
//遍历11次后fibonacci()被调用了453次 ,我们调用了11次
function menoizationMethod1(){
	var htmlStr = "";
	for ( var i = 0; i <=10; i++) {
		var tmp_count = count;
		htmlStr +="参数值:"+i+"\t和:"+fibonacci(i)+"\t该参数值下遍历次数:"+ (count-tmp_count)+"\t累计遍历次数:"+count+"<br/>";
	}
	document.getElementById("memoization1").innerHTML = htmlStr;
	count = 0;
}
 <button onclick="menoizationMethod1();">传统递归</button>
  <div id='memoization1'></div>

 2、求数字之和(同过记忆优化递归方法)

var count =0;//记录遍历次数
var fibonacci2 =function(){
	var memo = [0,1];
	var fib = function(n){
		var result = memo[n];
		count++;
		if(typeof result !== 'number'){
			result = fib(n-1) + fib(n-2);
			memo[n] = result;
		}
		return result;
	}
	return fib;
}();
//遍历11次后fibonacci()被调用了29次 ,我们调用了11次
function menoizationMethod2(){
	var htmlStr = "";
	for ( var i = 0; i <=10; i++) {
		var tmp_count = count;
		htmlStr +="参数值:"+i+"\t和:"+fibonacci2(i)+"\t该参数值下遍历次数:"+ (count-tmp_count)+"\t累计遍历次数:"+count+"<br/>";
	}
	document.getElementById("memoization2").innerHTML = htmlStr;
	count = 0;
}
    <button onclick="menoizationMethod2();">记忆递归</button>
    <div id='memoization2'></div>

3、形式一般化

//此类函数形式一般化
var count =0;//记录遍历次数
var memoizer = function (memo,fundamenta1){
	var shell = function(n){
		count++;
		var result = memo[n];
		if(typeof result !== 'number'){
			result = fundamenta1(shell,n);
			memo[n] = result;
		}
		return result;
	}
	return shell;
}
//计算数字累积和
function memoizerSumMethod(){
	var htmlStr = "";
	var fib1 = memoizer([0,1],function(shell,n){
		return shell(n-1)+shell(n-2);
	});
	for ( var i = 0; i <=10; i++) {
		var tmp_count = count;
		htmlStr +="参数值:"+i+"\t和:"+fib1(i)+"\t该参数值下遍历次数:"+ (count-tmp_count)+"\t累计遍历次数:"+count+"<br/>";
	}
	document.getElementById("memoization3").innerHTML = htmlStr;
	count = 0;
}
//计算数字乘积(阶乘)
function memoizerMultiplyMethod(){
	var htmlStr = "";
	var fib2 = memoizer([1,1],function(shell,n){
		return n*shell(n-1);
	});
	for ( var i = 0; i <=10; i++) {
		var tmp_count = count;
		htmlStr +="参数值:"+i+"\t乘积:"+fib2(i)+"\t该参数值下遍历次数:"+ (count-tmp_count)+"\t累计遍历次数:"+count+"<br/>";
	}
	document.getElementById("memoization4").innerHTML = htmlStr;
	count = 0;
}

 

    <button onclick="memoizerSumMethod();">计算数字累积和</button>
    <div id='memoization3'></div>
    <button onclick="memoizerMultiplyMethod();">计算数字累积和</button>
    <div id='memoization4'></div>

 

分享到:
评论

相关推荐

    斐波那契记忆优化法优化JavaScript

    用斐波那契记忆优化法优化递归,提高代码运行效率,这个是JavaScript版

    javascript 用记忆函数快速计算递归函数

    在JavaScript中,递归函数是一种常见的编程范式,其中函数调用自身来解决问题。然而,在处理复杂或者大量的输入时,递归可能会导致大量的重复计算,消耗大量资源,从而降低程序的运行效率。为了解决这个问题,可以...

    javascript中递归函数用法注意点

    在JavaScript中,递归函数是一种重要的编程技巧,它是指函数在其定义中调用自身来解决问题的方法。递归在处理树形结构、阶乘计算、斐波那契序列等问题时非常常见。然而,不恰当的使用递归可能会导致栈溢出(stack ...

    js代码-小递归递归

    在实际编程中,我们需要注意以下几点来优化递归: 1. **避免无限递归**:确保每个递归调用都有正确的退出条件,防止程序陷入无限循环。 2. **明确基本和递归情况**:明确指出何时停止递归(基本情况)和如何进行下...

    基于python的数据可视化-21-递归的执行流程.ev4.rar

    理解递归的执行流程,以及如何在Python中正确实现和优化递归函数,对于提升数据可视化项目的质量和效率至关重要。通过学习和实践,你将能够创造出更加生动、直观且富有洞察力的数据可视化作品。

    JavaScript递归函数定义与用法实例分析

    5. **尾递归**:在某些语言(如Scheme或现代JavaScript)中,尾递归优化可以使无限递归变为有限的堆栈空间,因为最后一项操作是递归调用。 6. **记忆化**:为了提高效率,可以使用缓存存储之前计算过的值,避免重复...

    递归

    在编程领域,递归是一种强大的概念,它涉及到一个函数或过程在其定义中调用自身来解决问题的方法。在JavaScript中,递归尤其常见,因为它是一种灵活的动态类型语言,支持多种编程范式,包括函数式编程,其中递归是...

    fibonacci-algorithms:这是4种用于在JavaScript中计算给定斐波那契数的示例算法。 递归,记忆,自下而上并使用Binet公式

    标题中提到的"fibonacci-algorithms"是一个项目,它提供了四种不同的方法来在JavaScript中计算斐波那契数。下面我们将详细探讨这四种算法: 1. **递归**: 递归算法是最直观但效率最低的方法。它基于函数自身调用...

    使用递归算法求第30位数的值

    为了优化,可以使用动态规划(如记忆化搜索)或迭代方法来避免重复计算。 总的来说,这个例子展示了如何利用递归算法解决一个具体的数学问题——找到斐波那契数列的特定位置的数值。在实际编程中,理解递归原理并...

    javascript算法训练营

    4. **动态规划**:这是一种解决最优化问题的强大方法,通常涉及记忆化搜索和自底向上的求解策略。在训练营中,你会通过实例学习如何应用动态规划。 5. **回溯法**:一种试探性的解决问题的方法,通过撤销先前的决策...

    recursionPractice:利用递归练习和进一步理解递归的函数

    在"recursionPractice-master"项目中,你可以期待找到使用JavaScript实现的各种递归示例,这些示例可以帮助你理解如何在实际场景中运用递归,以及如何设计和优化递归函数。通过对这些代码的分析和实践,你将能更深入...

    基于JS递归函数细化认识及实用实例(推荐)

    JavaScript中的递归函数是一种强大的编程工具,它允许函数在执行过程中调用自身,以解决复杂问题。递归的核心思想是将大问题分解成相同或相似的小问题,直到达到一个基础情况,即边界条件,然后逐步返回结果。在这个...

    树形菜单javascript(兼容IE,Firfox,刷新记忆)

    在JavaScript实现中,这可能通过递归数据结构来实现,如对象或者数组嵌套,每个节点包含自身的属性和子节点的引用。这样可以动态地构建和操作复杂的菜单层次。 提到性能,菜单显示时间不大于1毫秒/菜单项,响应时间...

    JS树形菜单集合(最全)

    在JS中,树形菜单通常通过对象或数组表示,可以递归地表示层次关系。 2. **JS树形菜单的基本实现** - 一个基本的JS树形菜单通常包括展开/折叠节点的功能,以及点击节点触发的事件处理。这可以通过DOM操作和事件...

    递归审查

    通过这个递归审查项目,学生不仅能提升JavaScript编程技能,还能锻炼逻辑思维能力和问题解决能力,这对于任何IT专业人员来说都是非常宝贵的经验。在实践中不断探索和改进,将有助于掌握这一复杂但强大的编程技巧。

    Algorithm:个人算法刷题总结,利用JS语言,每道题尝试优化最优解或最简洁的方法

    在JavaScript中,动态规划广泛应用于背包问题、最长公共子序列、最短路径等问题,通过记忆化搜索减少重复计算,达到优化。 4. **贪心算法**:贪心策略是在每一步选择中都采取当前状态下最好或最优的选择,但不保证...

    动态规划算法优化

    3. **记忆化搜索**:一种递归方式实现动态规划,通过缓存子问题的结果来避免重复计算。 4. **自底向上方法**:从最小的子问题开始逐步构建更大问题的解。 #### 三、动态规划算法的优化技巧 动态规划算法可以通过...

    js代码-尾调用优化tco

    JavaScript中的尾调用优化(Tail Call Optimization,简称TCO)是一种优化策略,旨在提高递归函数的性能。在JavaScript中,当一个函数的最后一步是调用另一个函数,并且返回该调用的结果时,我们称这个调用为“尾...

Global site tag (gtag.js) - Google Analytics