斐波那契数列

简介

斐波那契数列又称黄金分割数列，是指由0和1开始，之后的每一项数字都是前两项数字的和。形式化的定义如下：

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2)，其中n > 1

斐波那契数列的前几项为：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

作用

斐波那契数列在计算机科学中有广泛的应用，比如在算法设计（动态规划、贪心算法、分治算法等）中，快速筛选数据（排序、查找等）也会用到。

使用方法

使用递归

递归是计算斐波那契数列的一种常用方法，实现简单，但因为递归的特性，容易导致栈溢出（递归层数太多）。

代码示例：

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

使用循环迭代

循环迭代是计算斐波那契数列的另一种常用方法，相较于递归，在计算大型斐波那契数列时，循环迭代的效率更高。

代码示例：

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        a, b = 0, 1
        for i in range(2, n+1):
            a, b = b, a+b
        return b

示例说明

以下是使用循环迭代计算斐波那契数列的一个示例：

# 计算前10个斐波那契数列
for i in range(10):
    print(fibonacci(i))

输出结果：

0
1
1
2
3
5
8
13
21
34

另一个示例是使用斐波那契数列在算法中的应用，比如使用斐波那契数列设计一个动态规划求解n阶爬楼梯问题的算法：

def climb_stairs(n):
    if n <= 2:
        return n
    f0, f1, f2 = 1, 1, 2
    for i in range(3, n+1):
        f0 = f1
        f1 = f2
        f2 = f0 + f1
    return f2

在此示例中，函数 climb_stairs 的参数为 n，返回值为一共有多少种爬楼梯的方法。该算法的内部实现中调用了 fibonacci 函数，用于计算斐波那契数列。