一个简单的算法

斐波那契数列

斐波那契数列非常适合用来介绍算法，所以在我们继续之前，这里简要介绍一下斐波那契数列。

斐波那契数列以 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)