函数可以通过用对象去记住先前操作的结果,从而避免无谓的运算,这种优化称为 记忆(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中,递归函数是一种重要的编程技巧,它是指函数在其定义中调用自身来解决问题的方法。递归在处理树形结构、阶乘计算、斐波那契序列等问题时非常常见。然而,不恰当的使用递归可能会导致栈溢出(stack ...
在实际编程中,我们需要注意以下几点来优化递归: 1. **避免无限递归**:确保每个递归调用都有正确的退出条件,防止程序陷入无限循环。 2. **明确基本和递归情况**:明确指出何时停止递归(基本情况)和如何进行下...
理解递归的执行流程,以及如何在Python中正确实现和优化递归函数,对于提升数据可视化项目的质量和效率至关重要。通过学习和实践,你将能够创造出更加生动、直观且富有洞察力的数据可视化作品。
5. **尾递归**:在某些语言(如Scheme或现代JavaScript)中,尾递归优化可以使无限递归变为有限的堆栈空间,因为最后一项操作是递归调用。 6. **记忆化**:为了提高效率,可以使用缓存存储之前计算过的值,避免重复...
在编程领域,递归是一种强大的概念,它涉及到一个函数或过程在其定义中调用自身来解决问题的方法。在JavaScript中,递归尤其常见,因为它是一种灵活的动态类型语言,支持多种编程范式,包括函数式编程,其中递归是...
标题中提到的"fibonacci-algorithms"是一个项目,它提供了四种不同的方法来在JavaScript中计算斐波那契数。下面我们将详细探讨这四种算法: 1. **递归**: 递归算法是最直观但效率最低的方法。它基于函数自身调用...
为了优化,可以使用动态规划(如记忆化搜索)或迭代方法来避免重复计算。 总的来说,这个例子展示了如何利用递归算法解决一个具体的数学问题——找到斐波那契数列的特定位置的数值。在实际编程中,理解递归原理并...
4. **动态规划**:这是一种解决最优化问题的强大方法,通常涉及记忆化搜索和自底向上的求解策略。在训练营中,你会通过实例学习如何应用动态规划。 5. **回溯法**:一种试探性的解决问题的方法,通过撤销先前的决策...
在"recursionPractice-master"项目中,你可以期待找到使用JavaScript实现的各种递归示例,这些示例可以帮助你理解如何在实际场景中运用递归,以及如何设计和优化递归函数。通过对这些代码的分析和实践,你将能更深入...
JavaScript中的递归函数是一种强大的编程工具,它允许函数在执行过程中调用自身,以解决复杂问题。递归的核心思想是将大问题分解成相同或相似的小问题,直到达到一个基础情况,即边界条件,然后逐步返回结果。在这个...
在JavaScript实现中,这可能通过递归数据结构来实现,如对象或者数组嵌套,每个节点包含自身的属性和子节点的引用。这样可以动态地构建和操作复杂的菜单层次。 提到性能,菜单显示时间不大于1毫秒/菜单项,响应时间...
在JS中,树形菜单通常通过对象或数组表示,可以递归地表示层次关系。 2. **JS树形菜单的基本实现** - 一个基本的JS树形菜单通常包括展开/折叠节点的功能,以及点击节点触发的事件处理。这可以通过DOM操作和事件...
通过这个递归审查项目,学生不仅能提升JavaScript编程技能,还能锻炼逻辑思维能力和问题解决能力,这对于任何IT专业人员来说都是非常宝贵的经验。在实践中不断探索和改进,将有助于掌握这一复杂但强大的编程技巧。
在JavaScript中,动态规划广泛应用于背包问题、最长公共子序列、最短路径等问题,通过记忆化搜索减少重复计算,达到优化。 4. **贪心算法**:贪心策略是在每一步选择中都采取当前状态下最好或最优的选择,但不保证...
3. **记忆化搜索**:一种递归方式实现动态规划,通过缓存子问题的结果来避免重复计算。 4. **自底向上方法**:从最小的子问题开始逐步构建更大问题的解。 #### 三、动态规划算法的优化技巧 动态规划算法可以通过...
JavaScript中的尾调用优化(Tail Call Optimization,简称TCO)是一种优化策略,旨在提高递归函数的性能。在JavaScript中,当一个函数的最后一步是调用另一个函数,并且返回该调用的结果时,我们称这个调用为“尾...