用js优美的写各种斐波那契数列

fibonacci

在阅读BuckleScript官方文档时,发现一个斐波那契的code让我眼前一亮,实现思路是我从未想到过的。犹记得初学编程时斐波那契数列让我理解的递归的威力,现又让我从新认识了递归。这里我会总结我所有价值的斐波那契数列实现。如后续有新的认知会在文章末尾处更新。

让我从新认识递归的code(代码是Ocaml,后面我会转换为js)

let fib n =
  let rec aux n a b =
    if n = 0 then a
    else
      aux (n - 1) b (a+b)
  in aux n 1 1

这段代码会在后面js的版本介绍

正常递归版本

先说下正常的递归版本,这个版本在我初学编程时经常遇到的,它让我知道了递归的强大。

function fibonacci (n) {
   if(n==0) return 0
   else if(n==1) return 1
   else return fibonacci(n-1) + fibonacci(n-2)
}

代码优美逻辑清晰。但是这个版本有一个问题即存在大量的重复计算。如:当n为5的时候要计算fibonacci(4) + fibonacci(3)当n为4的要计算fibonacci(3) + fibonacci(2) ,这时fibonacci(3)就是重复计算了。运行 fibonacci(50) 等半天才会出结果。

for循环版本

递归有性能问题,用循环来做。

function fibonacci(n){
  var last = 1
  var last2 = 0
  var current = last2
  for(var i=1;i<=n;i++){
    last2 = last
    last = current
    current = last + last2
  }
  return current
}

这个版本没有重复计算问题,速度也明显快了很多。这并不代表循环比递归好。循环的问题在于状态变量太多,为了实现fibonacci这里使用了4个状态变量(last,last2,current,i) 而状态变量 在写、修改、删除的过程中需要格外小心,它会让我有不安全感。状态变量多了阅读起来也不那么优美了。

去除重复计算的递归版本

这个就是文章开头的例子转换为js的版本

function fib(n){
  function fib_(n,a,b){
    if(n==0)  return a
    else return fib_(n-1,b,a+b)
   }
   return fib_(n,0,1)
}

把前两位数字做成参数巧妙的避免了重复计算,性能也有明显的提升。n做递减运算,前两位数字做递增(斐波那契数列的递增),这段代码一个减,一个增,初看时有点费脑力。按照我的习惯一般是全增,让n从0开始到n。

使用记忆函数优化正常递归版本

正常版本fibonacci是纯函数(什么是纯函数?)纯函数可以用记忆函数进行优化,把那些需要重复计算的都放到缓存中。

function memozi(fn){
  var r = {}
  return function(n){
    if(r[n] == null){
      r[n] = fn(n)
      return r[n]
    }else{
        return r[n]
    }
  }
}

var fibfn = memozi(function(n){
    if(n==0){
        return 0
    }else if(n==1){
        return 1
    }else{
        return fibfn(n-1) + fibfn(n-2)
    }
})

既达到了性能提升的目的,又不破坏代码本身的优雅。

有趣的惰性序列

fibonacci本身是一个数列,只不过无限大。直接使用一个无限大的"数组" 来存储fibonacci 不就好了
不过js中没有无限大的数组,需要自己动手构造一个。

// 空序列
var _empty = {"@placeholder@":"@@"}
var _end = _empty
// 序对构造 惰性序列的值只有在需要用到的时候才进行求值 这里用function来代表
function pair(a,fn){
  return {
    left:a,
    right:fn
  }
}
function isFunction(p){
  return Object.prototype.toString.call(p) == "[object Function]"
}
function left(p){
  return p.left
}
function right(p){
  if(isEmpty(p.right)){
    return p.right
  }else if(isFunction(p.right)){
    return p.right(p)
  }else{
    throw "序列的第二个参数必须是一个函数"
  }
}
function isEmpty(seq){
  return seq == _empty
}
function isArrEmpty(arr){
  return arr.length == 0
}

function toArray(seq){
  if(isEmpty(seq)){
    return []
  }else{
    return [left(seq)].concat(toArray(right(seq)))
  }
}
function toSeq(arr){
  if(isArrEmpty(arr)){
    return _end
  }else{
    return pair(arr[0],p=>toSeq(arr.slice(1)))
  }
}
function map(fn,seq){
  if(isEmpty(seq)){
    return _end
  }else{
    return pair(fn(left(seq)),p=>map(fn,right(seq)))
  }
}
function take(n,seq){
  if(isEmpty(seq)){
    return _end
  }else if(n==0){
    return _end
  }else{
    return pair(left(seq),p=>take(n-1,right(seq)))
  }
}

function zip(fn,seq1,seq2){
  if(isEmpty(seq1)){
    return _end
  }else if(isEmpty(seq2)){
    return _end
  }else{
    var l1 = left(seq1)
    var l2 = left(seq2)
    return pair(fn(l1,l2),p=>zip(fn,right(seq1),right(seq2)))
  }
}

var fibonacci = pair(0,p=>pair(1,p1=>zip((a,b)=>a+b,p,p1)))

可以在console下运行 toArray(take(20,fibonacci))看看输出结果 ,运行toArray(take(30,fibonacci))结果出现需要等待一段时间,不要toArray(fibonacci)这样会卡死,因为fibonacci是无穷大的 toArray会一直求值直到内存耗尽。上面这段代码每个函数代码行数都是聊聊几行,直接看代码分析胜过冗余的文字解释。

这个惰性fibonacci 也有性能问题,跟第一个递归版本的是一样的有大量的重复计算,最直接的解决办法是加缓存即求值过的值不要再重新求值了。

惰性序列优化版本

// 空序列
var _empty = {"@placeholder@":"@@"}
var _end = _empty
// 序对构造 惰性序列的值只有在需要用到的时候才进行求值 这里用function来代表
function pair(a,fn){
  return {
    left:a,
    right:fn,
    rightCache:null
  }
}
function isFunction(p){
  return Object.prototype.toString.call(p) == "[object Function]"
}
function left(p){
  return p.left
}
function right(p){
  if(isEmpty(p.right)){
    return p.right
  }else if(isFunction(p.right)){
    if(p.rightCache != null){
      return p.rightCache
    }else{
      p.rightCache = p.right(p)
      return p.rightCache
    }
  }else{
    throw "序列的第二个参数必须是一个函数"
  }
}
function isEmpty(seq){
  return seq == _empty
}
function isArrEmpty(arr){
  return arr.length == 0
}

function toArray(seq){
  if(isEmpty(seq)){
    return []
  }else{
    return [left(seq)].concat(toArray(right(seq)))
  }
}
function toSeq(arr){
  if(isArrEmpty(arr)){
    return _end
  }else{
    return pair(arr[0],p=>toSeq(arr.slice(1)))
  }
}
function map(fn,seq){
  if(isEmpty(seq)){
    return _end
  }else{
    return pair(fn(left(seq)),p=>map(fn,right(seq)))
  }
}
function take(n,seq){
  if(isEmpty(seq)){
    return _end
  }else if(n==0){
    return _end
  }else{
    return pair(left(seq),p=>take(n-1,right(seq)))
  }
}

function zip(fn,seq1,seq2){
  if(isEmpty(seq1)){
    return _end
  }else if(isEmpty(seq2)){
    return _end
  }else{
    var l1 = left(seq1)
    var l2 = left(seq2)
    return pair(fn(l1,l2),p=>zip(fn,right(seq1),right(seq2)))
  }
}

var fibonacci = pair(0,p=>pair(1,p1=>zip((a,b)=>a+b,p,p1)))

调用 toArray(take(30,fibSeq)) 对比下上一个版本 速度上有质的提升,点击这里在线运行上面的代码

纯箭头函数版本

条件苛刻一些,使用匿名函数实现fibonacci功能,正常的递归版本上面有提到如下:

let fib = n => n > 1 ? fib(n-1) + fib(n-2) : n

把fib名字去掉就是匿名版本,但去掉fib就无法递归也就是调用自身了。事实上是可以间接的调用自身,代码如下:( 注:不知道怎么描述好 )

(f=>n=>n>1?f(f)(n-1)+f(f)(n-2):n)(f=>n=>n>1?f(f)(n-1)+f(f)(n-2):n)(10)

返回 55。用f来巧妙的代表剪头函数本身

在线运行上面的代码

Y Combinator + 箭头函数版本

将上面的箭头函数调用自身的功能抽象出来就是Y Combinator (注: 谢谢李思立的补充

let Y = f => (g=>f(a=>g(g)(a)))(g=>f(a=>g(g)(a)))

现在可以这样写剪头函数版本的代码了

Y(f=>n=>n>1?f(n-1)+f(n-2):n)(10)

f代表箭头函数自身,使用f进行递归。在线运行上面代码

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,839评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,543评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,116评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,371评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,384评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,111评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,416评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,053评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,558评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,007评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,117评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,756评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,324评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,315评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,539评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,578评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,877评论 2 345

推荐阅读更多精彩内容