追踪递归的斐波那契数列

Question

追踪递归的斐波那契数列

5

我正在努力理解用于斐波那契数列的递归机制。

#include<stdio.h>
int fib(int n);
int main()
{
    int x, n;
    scanf("%d", &n);
    x = fib(n);
    printf("fibonacci number %d = %d\n", n, x);
    return 0;
}
int fib(int n)
{
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        return (fib(n -1) + fib(n - 2));
    }
}

以下是该系列的代码。我可以追踪程序（n = 6）直到返回调用fib（1）并返回1的第一个术语为止。在那之后，我有点迷失了追踪执行。我尝试通过堆栈图来理解它，但我仍然感到困惑。有人能帮助我吗？还有，我如何使用gdb跟踪堆栈框架并查看堆栈框架上的变量值？

谢谢

- Vaibhav Sundriyal

它采用系统化的方法，其中f(n) = f(n - 1) + f(n - 2)。给定两个起始基本情况：f(0)和f(1)，您可以计算第n个斐波那契数。 - Obicere

4个回答

8

想一个随机数并绘制执行步骤（如树形结构）。我总是用纸和笔来理解算法。并且，始终尝试将整个程序分解为每个小逻辑，并确保您理解其中的每一个。我为您绘制了这张图表。非常抱歉我画得不好。 enter image description here

- CoderKK

+1 对于这个图表。至少你自己画了它。我喜欢它 :) - haccks

6

如果您调用 fib(4), 将会得到以下的调用链：

fib(4) = fib(3)                             + fib(2)
         = fib(2)             + fib(1)        = fib(1) + fib(0)
           = fib(1) + fib(0)    = 1             = 1      = 0
             = 1      = 0

一个好的方法是对您的函数进行以下修改:

#include<stdio.h>
int fib(int n, int m);
int main()
{
    int x, n;
    scanf("%d", &n);
    x = fib(n, n);
    printf("fibonacci number %d = %d\n", n, x);
    return 0;
}
int fib(int n, int m)
{
    printf("calling fib(%d) from fib(%d)\n", n, m);
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        return (fib(n -1, n) + fib(n - 2, n));
    }
}

这导致了

calling fib(4) from fib(4)
calling fib(3) from fib(4)
calling fib(2) from fib(3)
calling fib(1) from fib(2)
calling fib(0) from fib(2)
calling fib(1) from fib(3)
calling fib(2) from fib(4)
calling fib(1) from fib(2)
calling fib(0) from fib(2)
fibonacci number 4 = 3

这是一个简洁的"堆栈跟踪"示例...

- Floris

难道不应该是 fib(0) = 0 吗？ - haccks

@haccks 你是对的 - 是我的错。眼力真好。 - Floris

顺便提一下，斐波那契数列以 0 开始（据我所知）：0, 1, 1, 2, 3, 5, 8, 13,.... :) - haccks

1

没有，我没有问题。在我看来，它看起来很好。我只是告诉你这个系列的情况。 - haccks

1

else
{
    printf ("n is: %d\n", n);
    printf ("The program will go the %d-1 and %d-2 now.", n, n);
    return (fib(n -1) + fib(n - 2));
}

这将向您展示程序每次在新数字上运行时正在处理的数字。这样您就可以看到程序的操作。

- user3108849

序列中所描述的n的值（对于n=5）为5 4 3 2 2 3 2。在第一次n==2之前，我能理解这个操作，但在那之后我有点迷失了。你能解释一下吗？ - Vaibhav Sundriyal

1

是的，程序总是会先到达fib(n-1)，然后才是fib(n-2)，对吧？所以如果你输入5，程序会先到达5-1，接着是4-1，3-1，2-1，最后到达1。你要求返回值为1，于是它返回到2，并走到2-2，到达0后，返回到3。它总是会先到达n-1，等返回时再去到n-2部分。 - user3108849

在返回n=1后，它返回到n=2并调用fib(2-2)，即fib(0)。然后它返回到n=3并调用fib(3-2)，即fib(1)，然后返回到n=4并调用fib(2)，这又调用fib(1)返回并调用fib(0)。这正确吗？ - Vaibhav Sundriyal

@VaibhavSundriyal；请查看我的回答中的块图。 - haccks

@haccks 非常感谢。现在我对流程非常清楚了。 - Vaibhav Sundriyal

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- haccks · Accepted Answer

为了理解这个问题，我将您的fib函数重命名为fibonacci。现在假设用户输入3，则递归调用可以理解为（>表示调用，<表示返回）：

> fibonacci(3)
|   > fibonacci(2)
|   |   > fibonacci(1)
|   |   < 1
|   |   > fibonacci(0)
|   |   < 0
|   < 1
|   > fibonacci(1)
|   < 1
< 2

这可以通过块图¹更清晰地理解。

enter image description here

_{1.摘自Deitel的《C语言编程》。}