一个简单的算法

斐波那契数列

斐波那契数列在介绍算法方面非常有用，所以在我们继续之前，先简要介绍一下斐波那契数列。

斐波那契数列是以一位名叫斐波那契的 13 世纪意大利数学家命名的。

前两个斐波那契数是 0 和 1，下一个斐波那契数始终是前两个数的和，因此我们得到 0、1、1、2、3、5、8、13、21、...

本教程将大量使用循环和递归。所以在我们继续之前，让我们来实现三个不同版本的算法来创建斐波那契数，以简单的方式展示循环编程和递归编程的区别。

斐波那契数算法

要生成一个斐波那契数，我们只需要将前两个斐波那契数相加。

斐波那契数列是展示算法是什么的一个好方法。我们知道如何找到下一个数字的原理，所以我们可以编写一个算法来生成尽可能多的斐波那契数。

下面是生成前 20 个斐波那契数的算法。

循环与递归

为了展示循环和递归的区别，我们将实现三种不同的方法来找出斐波那契数

1. 上面斐波那契算法的实现，使用 for 循环。
2. 上面斐波那契算法的实现，使用递归。
3. 使用递归找出第 \(n\) 个斐波那契数。

1. 使用 For 循环实现

在编写代码之前，列出代码必须包含或执行的内容可能是一个好主意

• 两个变量来存储前两个斐波那契数
• 一个循环 18 次的 for 循环
• 通过将前两个数相加来创建新的斐波那契数
• 打印新的斐波那契数
• 更新存储前两个斐波那契数的变量

使用上面的列表，编写程序会更容易

prev2 = 0
prev1 = 1

print(prev2)
print(prev1)
for fibo in range(18):
    newFibo = prev1 + prev2
    print(newFibo)
    prev2 = prev1
    prev1 = newFibo

2. 使用递归实现

递归是指一个函数调用自身。

要实现斐波那契算法，我们需要与上面的代码示例中的大多数相同的内容，但我们需要用递归替换 for 循环。

要用递归替换 for 循环，我们需要将大部分代码封装在一个函数中，并且需要该函数调用自身来创建新的斐波那契数，只要生成的斐波那契数数量低于或等于 19。

我们的代码如下

print(0)
print(1)
count = 2

def fibonacci(prev1, prev2):
    global count
    if count <= 19:
        newFibo = prev1 + prev2
        print(newFibo)
        prev2 = prev1
        prev1 = newFibo
        count += 1
        fibonacci(prev1, prev2)
    else:
        return

fibonacci(1,0)

3. 使用递归找出第 \(n\) 个斐波那契数

要找出第 \(n\) 个斐波那契数，我们可以根据斐波那契数 \(n\) 的数学公式编写代码

\[F(n) = F(n-1) + F(n-2) \]

这只是意味着，例如，第 10 个斐波那契数是第 9 个和第 8 个斐波那契数的和。

在使用递归的概念时，我们可以让函数调用自身，只要 \(n\) 小于或等于 1。如果 \(n \le 1\)，则意味着代码执行已达到第一个斐波那契数 1 或 0。

代码如下

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

print(F(19))

请注意，此递归方法调用自身两次，而不仅仅是一次。这会极大地影响程序在计算机上的实际运行方式。当我们增加我们想要的斐波那契数的数量时，计算量将呈指数级增长。更具体地说，当我们想要的斐波那契数增加一倍时，函数调用的数量也将翻倍。

看看 \(F(5)\) 的函数调用次数

为了更好地理解代码，这里是递归函数如何返回值的示例，以便 \(F(5)\) 最终返回正确的值

这里有两个重要的事情需要注意：函数调用的数量，以及函数被相同参数调用的次数。

因此，尽管代码很吸引人并且展示了递归的工作方式，但实际的代码执行对于生成大的斐波那契数来说太慢且效率低下。

总结

在我们继续之前，让我们回顾一下我们到目前为止看到的内容

• 算法可以在不同的编程语言中以不同的方式实现。
• 递归和循环是可用于实现算法的两种不同的编程技术。

现在是时候继续研究我们将要看的第一个数据结构：数组。

点击“下一篇”按钮继续。

print(0)
print(1)
count = 2

def fibonacci(prev1, prev2):
    global count
    if count <= 19:
        newFibo = prev1 + prev2
        print(newFibo)
        prev2 = prev1
        prev1 = newFibo
        count += 1
        (prev1, prev2)
    else:
        return

fibonacci(1,0)