用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 条评论
登录 后参与评论

相关文章

来自专栏Petrichor的专栏

Dataset 列表:机器学习研究

In computer vision, face images have been used extensively to develop face recog...

1781
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

6326
来自专栏菩提树下的杨过

linq to sql取出随机记录/多表查询/将查询出的结果生成xml

在手写sql的年代,如果想从sqlserver数据库随机取几条数据,可以利用order by NewId()轻松实现,要实现多表查询也可以用select * f...

2236
来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1866
来自专栏一个会写诗的程序员的博客

java.sql.SQLException: connection holder is null

java.sql.SQLException: connection holder is null

1481
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2608
来自专栏码匠的流水账

spring security reactive获取security context

本文主要研究下reactive模式下的spring security context的获取。

2112
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1172
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2732
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2908

扫码关注云+社区