Python 中的斐波那契数列：探索编码技巧

斐波那契数列是持续练习 Python 的一种有趣方式。本文将带您用不同的 Python 技巧实现斐波那契数列：从编写高效函数、处理递归，到运用面向对象原则获得更优化的解法。

读完之后，欢迎参加我们的 Writing Functions in Python 课程，强化作用域与错误处理等概念；或试试 Intermediate Object-Oriented Programming in Python 课程，学习继承与基类。现在，让我们来尝试斐波那契数列。

速览答案

斐波那契数列从 0 和 1 开始，每个数都是前两个数之和。用 Python 生成它最简单的方法是用循环：

n = 10
a, b = 0, 1

fibonacci_numbers = []

for _ in range(n):  
    fibonacci_numbers.append(str(a)) 
    a, b = b, a + b

print(' '.join(fibonacci_numbers))

# This prints the first 10 Fibonacci numbers
# 0 1 1 2 3 5 8 13 21 34技术支持

什么是斐波那契数列？

斐波那契数列是一个在科学与自然界广泛出现的数学概念。它是一串数字序列，从 0 和 1 开始，每个数字都是前两个数字之和。这种模式构成了计算机科学、金融等领域诸多应用的基础。

斐波那契数列主要有两大特点：它的递归结构，以及与黄金比例的关系。

斐波那契数列的递归特性

斐波那契数列从 0 和 1 开始。每个新数字都是前两个数字之和。例如：

0 + 1 = 1

1 + 1 = 2

1 + 2 = 3

2 + 3 = 5

3 + 5 = 8

5 + 8 = 13

以此类推。

数学上我们写作 F(n) = F(n-1) + F(n-2)。这个序列通过不断将最后两个数相加来自我构建。首两个数字 0 和 1 是起点或基例，没有它们序列就无法成立。

这种递归模式是计算机科学中某些算法的基础。例如，编程中的递归在解决生成斐波那契数或将任务分解为更小、可管理的部分时会用到这一序列。

与黄金比例的联系

斐波那契数列与黄金比例密切相关。黄金比例是一个用 φ 表示的无理数（其值约为 1.618）。如果用某个斐波那契数除以前一个数，这个比值会越来越接近 φ。例如：

5 ÷ 3 ≈ 1.666

8 ÷ 5 ≈ 1.6

13 ÷ 8 ≈ 1.625

往后越算，越接近 1.618。这并非巧合——由于数值的增长方式，这一比值会自然地在斐波那契数列中出现。

欧几里得最早在古希腊对其进行了描述，称为“极比与中比”。自那以后，它被联系到自然中的模式，如贝壳与花朵的螺旋结构，以及艺术与建筑。

艺术中的黄金比例。 来源

斐波那契数列的实际应用

斐波那契数列在诸多领域以令人意外的方式出现。我们重点看两个最显著的应用：它在自然界中的模式，以及它在计算机科学中的用途。

自然中的斐波那契

自然界随处可见斐波那契数列。看看花朵——花瓣数常常是斐波那契数。例如，雏菊可能有 34、55 或 89 片花瓣，而百合则常见 3、5 或 8 片。这些模式帮助植物以最大化阳光与雨水的方式生长。

松果与向日葵的螺旋也遵循斐波那契数。比如向日葵的种子排列就符合该序列。令人着迷的是，如此简单的“两个数相加”能刻画自然界的诸多现象。

计算机科学中的斐波那契

斐波那契数列在算法与数据结构中也扮演关键角色。例如，斐波那契数用于搜索算法中，高效地将问题拆分为更小的部分。这个序列甚至启发了 Fibonacci 堆，这是一种用于加速某些操作（如在网络中寻找最短路径）的数据结构。

下面是一个在 Python 中生成斐波那契序列的简单示例：

def fibonacci(n):
	if n <= 1:
		return n
	return fibonacci(n - 1) + fibonacci(n - 2)

# Example usage
fibonacci_numbers = []

for i in range(10):
	fibonacci_numbers.append(str(fibonacci(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34技术支持

这个递归函数展示了斐波那契数列是如何构建的。虽然递归容易理解，但也有更优化的版本，如动态规划，可以更快地计算斐波那契数。

在密码学中，斐波那契数可用于生成安全密钥。而在人工智能中，它们用于优化神经网络，提升算法的学习与适应能力。

其他常见示例

以下是该序列在日常生活与专业领域中出现的更多例子：

艺术中：数百年来，艺术家与建筑师一直使用斐波那契数列。像帕台农神庙这样的著名建筑采用这些比例，因为它们在视觉上天然协调。
音乐中：作曲家用斐波那契数来构建节奏与旋律。例如，将全音符对应 1，二分音符对应 2，四分音符对应 3，以形成和谐的模式。
交易中：股票交易者用斐波那契数分析市场趋势。他们据此预测股票可能反转的价格区间，帮助决定买入或卖出时机。
物理学中：在量子物理中，人们在粒子的相互作用与行为里观察到斐波那契模式，显示这种序列甚至出现在自然界的最小尺度。

在 Python 中实现斐波那契数列

由于 Python 提供多种方式生成斐波那契数列，下面我将以示例分步介绍最常用的方法。

使用迭代方法

迭代法是生成斐波那契数列最简单的方法之一。它用循环计算序列中的每一项，相比递归更省内存。其工作原理如下：

我设置两个变量 a 与 b 为 0 和 1，它们代表序列的前两项。接着使用 for 循环计算后续数字。我将 a 更新为 b 的值，b 则变为先前 a 与 b 之和。

对应的 Python 代码如下：

n = 10
a, b = 0, 1

fibonacci_numbers = []

for _ in range(n):
    fibonacci_numbers.append(str(a))
    a, b = b, a + b

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34技术支持

如果您想用 while 循环替代 for 循环，可以这样写：

# Number of terms to print in the Fibonacci series
n = 10

# Initialize the first two terms
a, b = 0, 1
i = 0

fibonacci_numbers = []

while i < n:
	fibonacci_numbers.append(str(a))
	# Update the terms
	a, b = b, a + b
	i += 1

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34技术支持

两种方法都非常容易理解，非常适合初学者。

使用递归方法

递归法是生成斐波那契数的另一种方式。对于较大的序列，它不如迭代法快，但非常有助于理解序列的构建逻辑。

例如，我会创建一个名为 fibonacci_recursive 的函数。该函数接收数字 n 作为输入。如果 n 是 0 或 1，函数返回 n。这些是告诉递归何时停止的基例。对于其他数字，函数会自调用以计算前两个数字并将它们相加。

代码如下：

def fibonacci_recursive(n):
	if n <= 1:
		return n
	else:
		return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

num_terms = 10
fibonacci_numbers = []
for i in range(num_terms):
	fibonacci_numbers.append(str(fibonacci_recursive(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34技术支持

该方法对小规模序列效果良好，但随着序列增长会变慢，因为它会多次重复计算相同的值。

使用带缓存的优化递归

为解决纯递归的低效问题，我常用缓存。Python 的 lru_cache 会存储已计算的值，使函数无需重复工作。

我的做法如下：

from functools import lru_cache

@lru_cache(maxsize = None)
def fib_cache(n):
    if n == 0:
        return 0  
    elif n == 1:
        return 1
    else:
        return fib_cache(n-1) + fib_cache(n-2)

print(f"The Fibonacci Number is {fib_cache(10)}")

# The Fibonacci Number is 55技术支持

这种方法将递归的清晰性与缓存的高效性相结合。

在 Python 中实现斐波那契的更高级方法

如果您想用其他方式计算斐波那契数，下面是一些更高级的技巧：

矩阵快速幂

对于较大的 n，矩阵快速幂是计算斐波那契数最高效的方法之一。与反复重算项不同，该方法使用矩阵乘法在对数时间内得到结果。

我在 Python 中的实现如下：

import numpy as np

def fibonacci_matrix(n):
	def matrix_power(matrix, power):
		return np.linalg.matrix_power(matrix, power)
	if n == 0:
		return 0
	matrix = np.array([[1, 1], [1, 0]])
	result = matrix_power(matrix, n-1)
	return result[0][0]

fibonacci_numbers = []

for i in range(10):
	fibonacci_numbers.append(str(fibonacci_matrix(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34技术支持

在这段代码中，若 n 为 0，则返回 0 作为基例。对于其他值，利用 numpy 的 matrix_power 将矩阵提升至 (n-1) 次幂。位置 n 的斐波那契数在结果矩阵的左上角元素中。

比奈公式（Binet's formula）

比奈公式可直接计算第 n 个斐波那契数，无需迭代或递归。它基于黄金比例 φ，通过数学表达式瞬时得到结果。

公式为：

其中：

φ = (1 + √5) / 2，即黄金比例。
1 - φ 是 φ 的共轭。

下面是比奈公式的 Python 代码：

import math

def fibonacci_binet(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((phi ** n - (1 - phi) ** n) / math.sqrt(5))

# Find the 10th Fibonacci number
n = 10
result = fibonacci_binet(n)
print(f"The Fibonacci Number of {n}th term is {result}" )

# The Fibonacci Number of 10th term is 55技术支持

在这段代码中，函数 fibonacci_binet(n) 使用比奈公式计算第 n 个斐波那契数。函数内我将 phi（黄金比例）计算为 (1 + math.sqrt(5)) / 2，用 math.sqrt() 计算 5 的平方根。随后应用公式 (phi ** n - (1 - phi) ** n) / math.sqrt(5) 直接求得第 n 个斐波那契数。最后用 round() 处理可能存在的浮点微小误差。

数组

您甚至可以用数组来生成并存储整个斐波那契数列。当您需要同时获取多个项时，这会很有帮助。

代码如下：

def fibonacci(n):
    if n <= 0:
        return "Incorrect Output"
    data = [0, 1]  # Initialize list with first two Fibonacci terms: 0 and 1
    if n > 2:
        for i in range(2, n):  # Start loop from the third term
            data.append(data[i-1] + data[i-2])  # Calculate next term as sum of previous two
    return data[n-1]  # Return the nth term

print(f"Fibonacci Number: {fibonacci(10)}")

# Fibonacci Number: 34技术支持

回溯

回溯也是一个可选方案，尤其当我想把递归与记忆化结合以获得更好性能时。

代码如下：

def fibonacci_backtracking(n, computed ={0: 0, 1: 1}):
    if n in computed:
        return computed[n]
    computed[n] = fibonacci_backtracking(n - 1) + fibonacci_backtracking(n - 2)
    return computed[n]

n = 10
result = fibonacci_backtracking(n)
print(f"The {n}th Fibonacci term is {result}")

# The 10th Fibonacci term is 55技术支持

Python 中斐波那契算法的复杂度

我们已经看了不少示例！现在从时间与空间复杂度的角度比较它们的差异。正如前面所述，有些方法运行更快但更耗内存，而另一些更慢但占用更少空间。我准备了下表来比较各方法的效率。

方法	时间复杂度	空间复杂度
迭代（For 循环）	O(n)	O(1)
迭代（While 循环）	O(n)	O(1)
简单递归	O(2ⁿ)	O(n)
记忆化/缓存	O(n)	O(n)
基于数组	O(n)	O(n)
回溯方法	O(2ⁿ)	O(2ⁿ)
矩阵快速幂	O(log n)	O(log n)

在上表中，各项时间与空间复杂度含义如下：

时间复杂度

O(n)：算法对序列迭代一遍，每个元素执行固定数量的操作。耗时随输入规模 n 线性增长。
O(1)：用固定数量的操作计算斐波那契数，无需迭代或递归。
O(2ⁿ)：算法对每个输入进行两次递归调用，随着 n 增加，函数调用数呈指数增长。
O(log n)：运行时间与输入规模 n 的对数成比例增长。

空间复杂度

O(n)：算法使用的内存与输入数量 n 成正比。此处每个元素占用固定空间。
O(1)：内存使用量与输入规模无关，保持不变。
O(2ⁿ)：由于每个分支都会创建新状态而使用指数级空间。
O(log n)：中间的矩阵乘法使用对数级内存。

结语

如您所见，在 Python 中可以用多种方法计算斐波那契数，从简单循环到诸如矩阵快速幂与比奈公式等高级技巧。每种方法都有其优点与取舍。

希望您不仅学到了斐波那契数列的知识，也加深了对 Python 编程的理解。若想进一步探索 Python 及相关主题，欢迎查看我们的 Introduction to Python 课程。您也可以尝试完整的 Python Developer 职业路径，学习编程技巧，甚至开始开发自己的包！

作者

Laiba Siddiqui

LinkedIn Twitter

我是内容策略专家，热衷于将复杂主题化繁为简。我曾帮助 Splunk、Hackernoon 和 Tiiny Host 等公司为其受众打造兼具吸引力与信息量的内容。

Python 中的斐波那契数列常见问题

斐波那契数列用于什么？

斐波那契数列被用于数学、计算机科学与自然研究等领域，用于建模增长模式并优化算法。

斐波那契数列如何计算？

斐波那契数列的计算方法是把前两个数字相加得到下一个数字，从 0 和 1 开始。

自然界中斐波那契数列的例子有哪些？

示例包括茎上叶序的排列、树木的分枝，以及多种水果与花朵的形态。

如何在 Python 中实现斐波那契数列？

您可以使用迭代或递归的方法来实现，许多编程教程中都提供了 Python 代码示例。

斐波那契数列第 n 项的公式是什么？

第 n 项可以用比奈公式计算。该公式涉及黄金比例，提供一种直接的计算方法。

主题

Python 数据分析数据科学

主题

技术

Python 中的斐波那契数列：学习并探索编码技巧

使用 AI 探索

速览答案

什么是斐波那契数列？

斐波那契数列的递归特性

与黄金比例的联系

斐波那契数列的实际应用

自然中的斐波那契

计算机科学中的斐波那契

其他常见示例

在 Python 中实现斐波那契数列

使用迭代方法

使用递归方法

使用带缓存的优化递归

在 Python 中实现斐波那契的更高级方法

矩阵快速幂

比奈公式（Binet's formula）

数组

回溯

Python 中斐波那契算法的复杂度

结语

Python 中的斐波那契数列常见问题

主题

与 DataCamp 一起学习 Python

Python 入门

Python 面向对象编程进阶

Python 工具箱

主题

技术

与 DataCamp 一起学习 Python

Python 入门

Python 面向对象编程进阶

Python 工具箱