什么是斐波拉契数列 (Fibonaccisequence)
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多・斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为 “兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
使用 Golang 递归实现斐波拉契数列
package main import ( "fmt" ) func fibonacci(n int) (r int) { if n <= 2 { return 1 } return fibonacci(n-1) + fibonacci(n-2) } func main() { for i := 0; i < 10; i++ { fmt.Printf("%d, ", fibonacci(i)) } }
得到结果：
1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
斐波拉契数列的递归实现优化
由于上述代码使用了两次递归，为减少递归次数，对递归代码优化如下：
package main import ( "fmt" ) func advanceFibonacii(n int) (r int) { if n <= 2 { return 1 } result := 1 for i := 2; n > i; n-- { result += advanceFibonacii(n - 2) } return result } func main() { for i := 0; i < 10; i++ { fmt.Printf("%d, ", advanceFibonacii(i)) } }
得到结果
1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
斐波那契数列的应用
- 算法
- 斐波那契堆
- 欧几里得算法的时间复杂度
- 物理学：氢原子能级问题
- 自然界：植物的生长
- 波浪理论与股市
- 斐波那契螺旋
- 建筑学
- 据说一个小男孩参考斐波那契数列发明了太阳能电池树
- 斐波那契螺旋形的摇椅
总结
斐波那契数列非常重要，所有关于数学的书几乎都会提到。
