使用迭代和递归找到第n个斐波那契数

    #include <iostream>
    using namespace std;

    unsigned long long fibonacci(unsigned long long n);

    unsigned long long fibonacci(unsigned long long n){
        if(n<=1)
            return n;                                //base case
        return fibonacci(n-1) + fibonacci(n-2);      //recursive case
    }

    int main(){
        unsigned int a {};
        cout << "Enter number: ";
        cin >> a;
        cout << fibonacci(a) << endl;
        return 0;
    }

#include <iostream>
using namespace std;
int main() {
    int n{};
    unsigned long long t1{0}, t2{1};
    unsigned long long sum{};
    cout << "Enter the number of terms: ";
    cin >> n;
    cout << "Fibonacci Series: ";
    for (int i{2}; i < n; ++i) {
        sum = t1 + t2;
        t1 = t2;
        t2 = sum;
    }
    cout << t2;
    return 0;
}

#1 楼

为什么大多数人（在Internet上）建议使用递归，因为它更容易编写程序？从逻辑上讲，我认为我们应该以一种快速而简单的方式编写它。


这是一个可以理解的问题。我在2004年写了一篇有关该主题的文章，您可以在这里阅读：

https://docs.microsoft.com/en-us/archive/blogs/ericlippert/how-not-to -teach-recursion

总结：有两个很好的理由教人们使用递归来解决Fib：


首先，因为它清楚地说明了你今天学到了。单纯将递归定义转换为递归函数通常会导致性能下降。对于初学者来说，这是一个重要的教训。 （练习：对于给定的n，您的幼稚递归程序执行了几次加法？答案可能会让您感到惊讶。）
第二，因为第一课使我们有机会带领初学者学习如何编写递归

不幸的是，正如您所发现的那样，互联网上的许多人还没有内化过通过fib进行递归教学仅是对错误使用递归以及如何进行递归的说明的有用方法。

如果人们尝试教递归通过提供好坏的递归算法来做到这一点，那就更好了。教了如何发现并避免不良情况。


还有比这两种方法更好的方法吗？


您很快就会学到的另一课是，问“哪个更好？”是一种肯定的方式来获得答复：“您能描述一个明确的指标以改善生活吗？”

因此：您能描述一个明确的指标以改善生活吗？我们的目标是打印出第n个fib号，您可以采用比任何一种解决方案都“更好”的方法：

做完了只能容纳这么多fib号码。您可以在Internet上查找它们，将它们复制到您的程序中，并且您有一个简短，快速的fib程序，根本没有循环。这对我来说是“更好”。 />
这些方法是否复杂？进入循环”。

这是一个见解的问题。让我这样说吧。

我在编译器团队工作，并采访了很多人。我的标准编码问题涉及在二叉树上编写一种简单的递归算法，该算法在以幼稚的方式编写时效率不高，但是可以通过进行一些简单的重构来使其高效。如果应聘者无法编写清晰，直接，有效的代码，那将是一件容易的事。

有趣的地方是当我问“假设您必须从遍历这棵树；您怎么做？”

有消除递归的标准技术。动态编程减少了递归。您可以创建一个显式堆栈并使用循环。您可以使整个算法尾部递归，并使用支持尾部调用的语言。您可以在共同通话中使用一种语言。您可以使用连续传递样式并构建“蹦床”执行循环。

从新手的角度来看，其中一些技巧非常复杂。我问这个问题是因为我想知道开发者工具箱中的内容。

#2 楼

如其他答案所述，您的迭代算法要优于递归算法，因为前者会记住先前的中间结果（或至少一个这样的结果），而后者则不会。当然，可以编写可记住先前结果的递归算法。

对于斐波那契数，这很简单，因为您只需要记住一个这样的结果。为了便于阅读，请使用C ++ 17的元组拆包语法： 。足够聪明的编译器可以优化成对打包和解包的开销，以使函数调用开销（请参阅编译器资源管理器）成为递归算法相对于迭代算法的唯一缺点。 br />
我将函数声明括在自己的命名空间detail::fibonacci_impl和子命名空间fibonacci(n)中。 ）放入一个单独的命名空间。对于要在自己的程序之外使用的声明（例如，编程库），强烈建议这样做，以避免名称遮盖问题和一般的混淆。

如果您的库声明的内容是通常只打算从该库内部使用它，通常将其放在一个子命名空间中，该子命名空间的名称指示其预期的性质。我遇到的有关此类子命名空间名称的示例包括：fibonacci(n-1)，pair，mynamespace或更短的mynamespace::detail。

#3 楼

在递归版本的代码中，您不需要功能原型unsigned long long fibonacci(unsigned long long n);。

您提到的代码中不应包含using namespace std;语句。

我们可以不能回答


为什么大多数人（在互联网上）建议使用递归，因为它更容易编写程序？（从逻辑上讲，我认为我们应该以某种方式编写它快速而简单）


，因为它是一种意见。

在迭代版本中，您还应该具有fibonacci(unsigned long long n)函数，以简化main()。 />

#4 楼

David Foerster的__fibonacci_impl既具有矩阵表示形式，可以将矩阵变成对角线形状，从而求出两个指数函数之差，其中后者的绝对值小于

 const double sqr5 = sqrt(5);
 const double phi = 0.5 * (sqr5+1);

 double Fn = floor( pow(phi,n) / sqr5 + 0.5); // n<=70

#5 楼

有没有比这两种方法更好的方法？这些方法是否复杂？


有更好的方法，尽管不是那么复杂，但很少有人能够开发这样的方法（例如Lucas序列关系）可以自己使用，而无需依赖某些参考。对于问题中所示的递归版本，对fibonacci（n）进行实例（调用）的次数将2 * fibonacci（n + 1）-1.

对于更好的方法，可以通过提高2 x 2矩阵= {{ 1,1}，{1,0}}乘幂通过重复平方得到幂，但这需要12个变量。使用基于Lucas序列关系的方法，可以将其减少为5个变量。

示例代码； c和d用于重复平方，而a和b是累加结果，最终为a = fib（n + 1），b = fib（n）。

注意：较早的编译器可能缺少<inttypes.h>或<stdint.h>。如果不存在<inttypes.h>（Visual Studio 2010），请为uint64_t使用编译器特定的格式字符串。如果不存在<stdint.h>（Visual Studio 2005），请使用typedef ... uint64_t（通常是unsigned long long）和适当的格式字符串。

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

uint64_t fib(uint64_t n)
{
    uint64_t a, b, c, d;
    a = d = 1;
    b = c = 0;
    while (1) {
        if (n & 1) {
            uint64_t ad = a*d;
            a = ad + a*c + b*d;
            b = ad + b*c;
        }
        n >>= 1;
        if (n == 0)
            break;
        {
            uint64_t dd = d*d;
            d = dd + 2 * d*c;
            c = dd + c*c;
        }
    }
    return b;
}

int main(void)
{
    uint64_t n;
    for (n = 0; n <= 93; n++)
        printf("%20" PRIu64 " %20" PRIu64 "\n", n, fib(n));
    return 0;
}

代码基于Lucas斐波那契数的序列关系。

https://en.wikipedia.org/wiki/Lucas_sequence#Other_relations

具体来说，这些等式：

初始状态：

F(m)   = F(m-1) + F(m-2)
F(m+n) = F(m+1) F(n) + F(m) F(n-1)
F(2n)  = F(n) L(n) = F(n) (F(n+1) + F(n-1))
       = F(n)((F(n) + F(n-1)) + F(n-1))
       = F(n) F(n) + 2 F(n) F(n-1)

n被视为2的幂的和：2 ^ a + 2 ^ b + ...
对于每个迭代i（从0开始），让p = 2 ^ i，然后

a = F(1) = 1
b = F(0) = 0
c = F(0) = 0
d = F(1) = 1

要前进到下一个迭代，c和d是前进到F（n的2的次幂）：

c = F(p-1)
d = F(p)

在计算a和b时，令m = n的当前累积位数之和：

d' = F(2p) = F(p) F(p+1) + F(p) F(p-1)
   = F(p)(F(p) + F(p-1)) + F(p) F(p-1)
   = F(p) F(p) + F(p) F(p-1) + F(p) F(p-1)
   = F(p) F(p) + 2 F(p) F(p-1)
   = d d + 2 c d

c' = F(2p-1) = F(p+p-1) = F(p+1) F(p-1) + F(p) F(p-2)
   = (F(p) + F(p-1)) F(p-1) + F(p) (F(p) - F(p-1))
   = F(p) F(p-1) + F(p-1) F(p-1) + F(p) F(p) - F(p) F(p-1)
   = F(p) F(p) + F(p-1) F(p-1)
   = d d + c c

将n中的a和b更新为1，对应于p = 2的当前功率：

b = F(m)
a = F(m+1)

请注意，如果b'是uint64_t的最大值，则a'将溢出，但这不是问题。但是，可以对算法进行修改，以使完成后a = fib（n-1）：

a' = F(m+1+p) = F(m+2) F(p) + F(m+1) F(p-1)
   = (F(m+1)+F(m)) F(p) + F(m+1) F(p-1)
   = F(m+1) F(p) + F(m) F(p) + F(m) F(p-1)
   = a d + b d + b c

b' = F(m+p) = F(m+1) F(p) + F(m) F(p-1)
   = a d + b c

#6 楼

通过使用该迭代解决方案，您可以间接使用动态编程（DP）

问题1的答案：

在某些情况下递归可能会更快。

例如，假设您的二维道路尺寸为n * m。道路上有障碍物，所以您不能通过它们。

目的是检查是否存在从左上角到右下角的任何路径（您只能移动右或向下）。

递归解将获胜，因为在最佳和最差情况下迭代解决方案将分别采用O(N * M)，但在最佳情况下将采用O(N + M)，而在最坏情况下将采用O(N * M) 。

这里给出了一个具有详细解释的迭代解决方案，但是我找不到递归解决方案的任何来源。

问题2的答案：

您的递归解决方案比迭代解决方案要慢得多，因为您没有使用备忘录。

记忆起来并不难理解。

请尝试访问此链接：https://www.quora.com/How-should-I-explain-dynamic-programming-to-a-4岁的孩子

#7 楼

评估渐进复杂度，例如使用gmp库显示，rcgldr的算法以O（log（n））互斥来实现有效的矩阵幂，在所提出的算法中性能最佳。


n步的直接迭代需要O（n ^ 1.60）的时间。 （n ^ 1.25）时间
时间为O（n ^ 1.029）的rcgldr算法。该图显示了n上以秒为单位的Fn的评估时间，两个轴均以10为底的对数，

#8 楼

尽管这个问题已经有很多答案，但其中一个是可以接受的，但我想指出的是，OP提出的（朴素的）递归解决方案比迭代版本的复杂性差得多。但是，完全有可能将问题分解为要由用户调用的主要功能，以及将其递归进行工作的内部帮助功能。下面的代码与OP的迭代解决方案具有相同的复杂度（实际上，它将由一个好的编译器编译为一个迭代解决方案），并且基本上由两个单行组成：

unsigned long long
fibonacci_internal(unsigned long long n,
                   unsigned long long t1,
                   unsigned long long t2) {
    return (n == 0) ? t1 : fibonacci_internal(n - 1, t2, t2 + t1);
}

unsigned long long fibonacci(unsigned long long n) {
    return fibonacci_internal(n, 0, 1);
}

编辑：修正了代码中的错字。递归调用发生在返回之前的逻辑分支的末尾，而在递归调用和返回之间没有其他操作。这称为尾递归。有关更多信息，请访问https://stackoverflow.com/questions/33923。 OP的原始函数在递归调用和返回之间添加了附加功能，因此它不是尾递归，递归调用必须使用额外的堆栈帧，并且编译器无法将其转换为迭代解决方案。

#9 楼

关于递归与迭代代码的争论是无止境的。有人说递归代码更“紧凑”并且更易于理解。在两种情况下（递归或迭代），当n即fib（n）的值增大时，系统上都会有一些“负载”。因此，fib（ 5）将立即计算出来，但是fib（40）会在稍有延迟后显示。当然，您的数据类型也必须足够大才能保存结果.CI认为64位系统上的unsigned long long int是可以获取的最大数据，此外，您可能还想尝试将中间结果保存在数组。那么唯一的约束将是内存。

#10 楼

Binet给出的方程式：

fib [n] =（phi ^ n-（-phi）^（-n））/ sqrt（5）其中phi =（1 + sqrt（5）） / 2

将给出准确的答案（与上述fib [n] = phi ^ n / sqrt（5）+ 1/2的答案不同），当n的值大于70时，该值会分解）。

由于可以直接计算，因此不需要迭代和递归。

#11 楼

最后，向

表示敬意，何时应该使用递归？

鉴于对算法的形式验证，您将编写一个不变式，它是该算法的数学模型，对然后您证明的任何变量和参数。当您的结果无论如何都定义为递归时（如斐波那契或阶乘级数所得出的那样），可以通过完全归纳来进行证明，其中归纳步骤很简单就是递归定义。例如，数量众多，则不会多次实例化函数的开销。

像C ++这样的运行时环境中，递归深度至关重要。您必须没有StackOverflow；如最初示例中那样，递归深度为O（n）是不可接受的！

因此，只要您可以控制渐近递归深度，并且运行时在评估中间结果时大部分是递归的

以下是对斐波那契数进行数位求值的算法，它使用了两个根据Binet公式和双曲函数的关系得出的整数序列；复杂度和递归深度为O（log（n））。

#include <iostream>

typedef unsigned long long N;

static void FibRec(int n, N& S, N&C)
{
    if (n >= 1)
    {
        N S1, C1;
        FibRec(n >> 1, S1, C1);
        if ((n >> 1) & 1)
        {
            C = (5 * C1 * C1 + S1 * S1) >> 1;
        }
        else
        {
            C = (C1 * C1 + 5 * S1 * S1) >> 1;
        }
        S= C1 * S1;
        if (n & 1)
        {
            N Cn0 = C;
            C = (C + S) >> 1;
            S= (5 * S+ Cn0) >> 1;
        }
    }
    else
    {
        S = 0;
        C = 2;
    }
}


N fibonacci(int n)
{
    N S, C;
    FibRec(n, S,C);
    return (n & 1) ? C : S;
}


int main()
{
    for (int n = 0; n<=93; n++)
    {
        std::cout << "Fib[" << n << "] = " << fibonacci(n) << std::endl;
    }
}