斐波那契数列的跟踪递归

Vaibhav Sundriyal 发表于 Dev

Vaibhav Sundriyal

我试图了解斐波那契数列的递归机制。

#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跟踪堆栈框架并查看堆栈框架上的变量值？

谢谢

弗洛里斯

如果您致电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

简而言之，就是您的“堆栈跟踪” ...

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。