练习 斐波纳契闭包

问题

让我们用函数做些好玩的事情。

实现一个 fibonacci 函数,它返回一个函数(闭包),该闭包返回一个斐波纳契数列 `(0, 1, 1, 2, 3, 5, ...)`。

背景知识

斐波纳契数列

斐波纳契数列的关键点有下面3个:
1. F0=0
2. F1=1
3. Fn=F(n-1)+F(n-2)(n>=2,n∈N*)

实现思路

  1. 采用闭包方式实现
  2. 采用递归函数实现

递归优化

  1. 目前用PHP实现时,发现递归超过30层,即计算30个数之后,会非常慢。
  2. 定位原因,函数调用是通过栈来实现,嵌套层数较多,递归需要保存每次的函数调用,造成性能降低。
  3. 优化方案是,采用尾递归。

实现代码

GitHub

参考链接

  1. 练习:斐波纳契闭包
  2. go语言实现斐波数列
  3. 匿名函数
  4. 学习一下闭包函数 – Closures
  5. 递归为什么那么慢?递归的改进算法
  6. C语言用递归求斐波那契数,让你发现递归的缺陷和效率瓶颈

发表评论

电子邮件地址不会被公开。 必填项已用*标注