斐波那契数列图文详解

斐波那契数列是指具备如下特征的数列：

• 前两个数的值分别为 0 、1 或者 1、1；

• 序列中从第 3 个数字开始，它的值是通过前两个数字相加得到的，即 F(n) = F(n-1) + F(n-2)。

例如，下面的数列就是一个斐波那契数列：

1、1、2、3、5、8、13、21、34、......

下面的动画给您描述了斐波那契数列的生成过程：

图 1 斐波那契数列的生成过程

接下来，我们研究如何设计算法生成斐波那契数列。

斐波那契数列的生成

斐波那契数列的生成方法有很多，本节我们主要研究如何用递归算法生成该数列。

如下为递归实现斐波那契数列的伪代码：

fibonacci(n):       // n 表示求数列中第 n 个位置上的数的值
    if n == 1:        // 设置结束递归的限制条件
        return 1
    if n == 2:        // 设置结束递归的限制条件
        return 1
    return fibonacci(n-1) + fibonacci(n-2)    // F(n) = F(n-1) + F(n-2)
输入 n                 // 输入 n 的值
for i<-1 to n:      // 输出前 n 个数
    print fibonacci(i)

如下为递归输出斐波那契数列的 C 语言程序：

#include <stdio.h>// n 表示求数列中第 n 个位置上的数的值int fibonacci(int n) {// 设置结束递归的限制条件if (n == 1 || n == 2) {return 1;}// F(n) = F(n-1) + F(n-2)return fibonacci(n - 1) + fibonacci(n - 2);}int main(){int i;// 输出前 9 个数for (i = 1; i <= 9; i++) {printf("%d ", fibonacci(i));}return 0;}

如下为递归输出斐波那契数列的 Java 程序：

public class Demo {// n 表示求数列中第 n 个位置上的数的值public static int fibonacci(int n) {// 设置结束递归的限制条件if (n == 1 || n == 2) {return 1;}// F(n) = F(n-1) + F(n-2)return fibonacci(n - 1) + fibonacci(n - 2);}public static void main(String[] args) {// 输出前 9 个数for (int i = 1; i <= 9; i++) {System.out.print(fibonacci(i) + " ");}}}

如下为递归输出斐波那契数列的 Python 程序：

# n 表示求数列中第 n 个位置上的数的值def fibonacci(n):# 设置结束递归的限制条件if n == 1 or n == 2:return 1# F(n) = F(n-1) + F(n-2)return fibonacci(n-1) + fibonacci(n-2)# 输出前 n 个数for i in range(1,9):print(fibonacci(i),end=" ")

以上程序的输出结果均为：

1 1 2 3 5 8 13 21