聊聊斐波那契数列中递归的重复计算
.title { text-align: center }
.todo { font-family: monospace; color: rgba(255, 0, 0, 1) }
.done { color: rgba(0, 128, 0, 1) }
.tag { background-color: rgba(238, 238, 238, 1); font-family: monospace; padding: 2px; font-size: 80%; font-weight: normal }
.timestamp { color: rgba(190, 190, 190, 1) }
.timestamp-kwd { color: rgba(95, 158, 160, 1) }
.right { margin-left: auto; margin-right: 0; text-align: right }
.left { margin-left: 0; margin-right: auto; text-align: left }
.center { margin-left: auto; margin-right: auto; text-align: center }
.underline { text-decoration: underline }
#postamble p, #preamble p { font-size: 90%; margin: 0.2em }
p.verse { margin-left: 3% }
pre { border: 1px solid rgba(204, 204, 204, 1); box-shadow: 3px 3px 3px rgba(238, 238, 238, 1); padding: 8pt; font-family: monospace; overflow: auto; margin: 1.2em }
pre.src { position: relative; overflow: visible; padding-top: 1.2em }
pre.src:before { display: none; position: absolute; background-color: rgba(255, 255, 255, 1); top: -10px; right: 10px; padding: 3px; border: 1px solid rgba(0, 0, 0, 1) }
pre.src:hover:before { display: inline }
pre.src-sh:before { content: “sh” }
pre.src-bash:before { content: “sh” }
pre.src-emacs-lisp:before { content: “Emacs Lisp” }
pre.src-R:before { content: “R” }
pre.src-perl:before { content: “Perl” }
pre.src-java:before { content: “Java” }
pre.src-sql:before { content: “SQL” }
table { border-collapse: collapse }
caption.t-above { caption-side: top }
caption.t-bottom { caption-side: bottom }
td, th { vertical-align: top }
th.right { text-align: center }
th.left { text-align: center }
th.center { text-align: center }
td.right { text-align: right }
td.left { text-align: left }
td.center { text-align: center }
dt { font-weight: bold }
.footpara:nth-child(0n+2) { display: inline }
.footpara { display: block }
.footdef { margin-bottom: 1em }
.figure { padding: 1em }
.figure p { text-align: center }
.inlinetask { padding: 10px; border: 2px solid rgba(128, 128, 128, 1); margin: 10px; background: rgba(255, 255, 204, 1) }
#org-div-home-and-up { text-align: right; font-size: 70%; white-space: nowrap }
textarea { overflow-x: auto }
.linenr { font-size: smaller }
.code-highlighted { background-color: rgba(255, 255, 0, 1) }
.org-info-js_info-navigation { border-style: none }
#org-info-js_console-label { font-size: 10px; font-weight: bold; white-space: nowrap }
.org-info-js_search-highlight { background-color: rgba(255, 255, 0, 1); color: rgba(0, 0, 0, 1); font-weight: bold }
code { color: rgba(255, 0, 0, 1) }
pre.src { background-color: rgba(0, 43, 54, 1); color: rgba(131, 148, 150, 1) }
聊聊斐波那契数列中递归的重复计算
所谓的斐波纳契数列是指：
前2个数是 0 和 1 。
第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
1 递归实现
根据定义，很快就能写出递归实现：
public int fibonacci(int n) { if (n < 2) {return 0;} if (2 == n) {return 1;} return fibonacci(n - 1) + fibonacci(n - 2); }
但是，这个函数去执行的时候，会发现非常的慢。那是什么原因呢？
我们仔细观察一下，每一次递归的时候，我们都会调用两个，所以，计算时，从n、n-1、… 0会是一个金字塔，二叉树的分布，也就是靠近0的底层，会有2^n次运算，就是一个指数级运算，计算时间复杂度为O(2^n),运算速度是非常慢的。
原因是什么呢？假如，我们计算的是10，那么它相应的要计算 9 + 8，而9要计算 8 + 7， 8又要计算 7 + 6.相当于越往底层去，计算的次数越多。
10
/ \
9 8
/ \ / \
8 7 7 6
...
2 递归改进
那么避免重复计算的方法就是，每计算得到一个值，便用一个数组保存这个值，下次计算该值的时候直接引用就可以了。
public int fibonacci(int n) { int[] array = new int[n + 1]; if (n < 2) {return 0;} if (2 == n) {return 1;} array[1] = 0; array[2] = 1; return helper(array, n); } private int helper(int[] array, int n) { if (n < 2) { return 0; } if (2 == n) { return 1; } array[n] = helper(array, n - 1) + array[n - 2]; // 保存每次计算的结果 return array[n]; }
但这种方法不是尾递归的，所以，调用栈内存会比较多。
3 迭代法
用迭代法来计算是最简单，速度也最快的。
public int fibonacci(int n) { int[] array = new int[n + 1]; if (n < 2) {return 0;} if (2 == n) {return 1;} array[1] = 0; array[2] = 1; for (int i = 3; i <= n; i++) { array[i] = array[i - 1] + array[i - 2]; } return array[n]; }
版权声明：本文为yangwen0228原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。