又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）
1 int Fibonacci(int n) { 2 if( n == 0 ) 3 return 0; 4 if ( n == 1 ) 5 return 1; 6 else 7 return Fibonacci(n - 2) + Fibonacci(n - 1); 8 }
解析：以上斐波那契数列是基本的递归方法，但不实用，因为在程序运行时，一旦 n 值过大易造成堆栈溢出状况而且重复严重，举例：n=4，看看程序怎么跑的：
1 int Fibonacci(int n) { 2 if( n == 0 ) 3 return 0; 4 else if ( n == 1 || n == 2) 5 return 1; 6 else if ( n == 3) 7 return 2; 8 else 9 return 3* Fibonacci(n - 3) + 2* Fibonacci(n - 4); 10 }
解析：该进阶方法通过斐波那契数列的一个简单规律可以使得冗余程度不再像第一个那般复杂重复，节省空间。矩阵快速幂详解参见：https://www.cnblogs.com/MMMMMMMW/p/12300262.html
1 int Fibonacci(int n) { 2 int f = 0, g = 1; 3 while(n -- > 0) { 4 g += f; 5 f = g - f; 6 } 7 return f; 8 }
解析：该方法中循环 n 次，因为第 n 个数字是前 n 个数字以规律相加得来，定义的 f 和 g 表示每一次第 n 个数相加时的 n - 1 和 n - 2 位 ，f 在每次运算过后都要 被 g 减去之前的数，方可得到第 n 位的数字。
图解：
原文：https://www.cnblogs.com/john1015/p/12909898.html