用memoization优化递归算法[JS/PHP实现]

递归函数,通过把一个大而复杂问题简化为许多但规模较小的问题,以同一个相似模式来计算,降低了解题的难度;通过调用自身函数,极大地减少了函数代码量的优点而为开发者喜爱。但因其不断调用自身函数开辟新栈,且大量传入同样参数,得到同样的结果,重复同一行为,也会浪费大量的内存。

以经典问题,斐波那契数列为例:

斐波那契数列指的是这样一个数列: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,求其第N项的值。

对数列进行分析,我们发现,从自三项开始,第N项的值就等于其前两项之和,即第N-1和第N-2项的和。所以我们可以这样写func(n)=func(n-1)+func(n-2)

代码如下:

1 function fibonacci(n){
2     if((n==0)||(n==1)){
3         return n;
4     }else{
5       return fibonacci(n-1)+fibonacci(n-2);//调用自身函数实现递归
6     }
7 }

分析代码我们发现,计算第N项的值总要计算第0项或第1项等较小的项的值,且会进行多次运算,结果相同。在此函数内,其边界项(0、1项)简便,若是进行边界项复杂的函数,内存会大量浪费。

memoization的思想是通过定义一个数组,用来存放计算过的数据,在需要的时候直接从数组中取出,而不必再次计算,从而省去大量不必要的动作。

以下是JS实现方式:

var fibonacci=function(n){
    var cache=[];//定义一个空数组用来存放计算好的数据
  if((n==0)||(n==1)){
    return n;
  }else{
    cache[n-1]=cache[n-1]||fibonacci(n-1);//应用||或运算符“短路”的特性,若在数组中找到其值,则直接使用数组内的值,若没有,再进行计算,并将值存入数组
    cache[n-2]=cache[n-2]||fibonacci(n-2);
    return cache[n-1]+cache[n-2];//返回数组中的值
  }
}

由上可以看出,在计算过一次后,数据被存入数组,再次调用时便会优先找到数组内的值而免于大量计算,从而提升效率。

以下是PHP实现(其实差不多。。。)

function fibonacci($n){
  $cache=[];
  if(($n==0)||($n==1)){
    return $n;
  }else{
    cacehe[$n-1]=cache[$n-1]||fibonacci($n-1);
    cacehe[$n-2]=cache[$n-2]||fibonacci($n-2);
    return cache[$n-1]+cache[$n-2];
  }
}

开始总结笔记了,如有错误,请各位不吝指正,谢谢。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏天天

jQuery选择器(20171026)

992
来自专栏数据科学与人工智能

【Python环境】Python面试题汇总(一)

拿网络上关于Python的面试题汇总了,给出了自认为合理的答案,有些题目不错,可以从中学到点什么,答案如不妥,请指正...... +++++++++++++++...

2346
来自专栏web前端教室

javascript 红皮高程(9)

这两天把JS的Number类型过了一遍,真是遍地是坑啊,如果这里出一些面试题,我100%要栽在这里。 NaN,undefined,null,Infinity,i...

2028
来自专栏SDNLAB

POF技术分享(三):Packet处理流程

前言: 之前对POF基本原理、POF交换机源码结构进行解读,但是,要想完成POF交换机的二次开发和拓展,有必要对POF交换机特有的数据包处理流程、POF交换机和...

34712
来自专栏desperate633

LintCode Backpack VI题目分析代码

Given an integer array nums with all positive numbers and no duplicates, find th...

512
来自专栏狮乐园

多维数组取值问题

给予一个多维数组和一个描述取值路径的一维数组, 通过调用函数f返回取值路径描述的值,如 f([[1, 2], [3, 4], [5, 6]], [0, 0]) ...

683
来自专栏大数据文摘

谷歌R语言格式指南

1543
来自专栏信数据得永生

JavaScript 编程精解 中文第三版 五、高阶函数

28110
来自专栏Python爬虫与算法进阶

PEP8规则及Pycharm应用

PEP8 PEP是 Python Enhancement Proposal 的缩写,翻译过来就是 Python增强建议书 PEP8 是什么呢,简单说就是一种编码...

3395
来自专栏犀利豆的技术空间

Redis 的基础数据结构(一) 可变字符串、链表、字典

这周开始学习 Redis,看看Redis是怎么实现的。所以会写一系列关于 Redis的文章。这篇文章关于 Redis 的基础数据。阅读这篇文章你可以了解:

723

扫码关注云+社区