迹忆客 专注技术分享

这篇文章将解释如何在 C++ 中使用递归函数实现斐波那契数列。 为此，我们将首先简要介绍递归函数。

C++ 中的递归函数

递归函数在其自身内部调用自身，使用此概念称为递归。 这个概念在很多方面都很有用，一些功能可以只使用递归来实现。

上图展示了递归的概念。 在main函数中，调用了一个函数recurse，在那个函数中，又调用了recurse。

这将创建一个递归调用，程序将继续在此函数中迭代，直到满足某些条件。 通常，递归函数中使用 if...else 结构，一条路径进行递归调用，另一条路径退出函数； 否则会出现无限递归。

递归从函数内部多次重复调用函数。 递归条件再次调用该函数，直到满足基本情况。

基本情况包含在函数内部，只要满足基本情况的条件，它就会终止执行。

代码：

void recursiveFun (int x )
{
    if (x == 0)
    return;
    x = x-1;
    recursiveFun(x);
}

上面的函数一旦用参数 x 调用，将递归地用 x 的减少值调用自身（即 [x-1, x-2, ..., x-(x-1)]）直到 x 变为零。 当遇到值为零的 x 时，程序将停止生成新的递归调用并开始从下到上返回值（如果有的话）。

虽然递归可以用来解决几乎所有的问题，但在某些特定的情况下它确实是有益的。 它通常用于处理遵循层次结构模式的难题和问题； 它通过解决较小的子问题来解决主要问题。

递归类型

直接递归和间接递归是递归的两种类型。

直接递归

递归函数通过直接递归直接在自己的函数体中调用自己。

void recursion ()
{
    ....
    recursion();

}

在代码中，我们可以看到函数在自己的函数体或括号中调用自己。

间接递归

在间接递归中，该函数在任何其他函数的主体中间接调用。

void func1()
{
    ...
    func2();
    }
    void func2()
    {
    ...
    func1();
}

斐波那契数列

斐波那契数列是一组整数，其中每个连续的数字都是前两个数字的总和。 前两个数 0 和 1，第三个数是前两个数相加的结果。

斐波那契数列的计算公式为：

例如 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

我们可以看到第三个元素1是0+1的和。 同样，第四个数字 2 是前面数字的总和 **(1+1=2)**。

因此我们可以预测该系列的下一个元素是 21+34 = 55。

C++ 中的斐波那契数列

为了实现斐波那契数列，我们可以实现一个递归函数，它可以接受一个数字作为输入，并打印出该数量的斐波那契数列。 例如，如果用户输入 8，我们将打印该系列的 8 个数字。

代码：

#include <iostream>
using namespace std;

int fibonacci (int num)
{
    if (num <= 1)
    return num;
    return fibonacci(num-1) + fibonacci (num-2);
}

int main()
{
    int num;
    cout<<"Enter a number: ";
    cin>> num;
    for (int a =0; a < num; a++)
    {
        cout<<fibonacci(a)<<" ";
    }
    return 0;
}

在主函数中，我们提示用户输入一个数字。 之后，我们迭代了一个从 0 到输入数字 num 的循环，并将迭代器变量 a 传递给斐波那契函数。

该循环将迭代 num 次用户输入的数字。 在 Fibonacci 函数中，我们有一个 if 条件来检查数字是否小于 1，然后它会返回该数字。

否则，它将为 num-1 和 num-2 调用斐波那契函数，因为该系列的每个下一个数字都是通过对前两个数字（即 n-1 和 n-2）求和来计算的。

输出：

用户输入了数字 9，因此打印出包含 9 个值的斐波那契数列。