追踪斐波纳契数列的递归

Question

我试图理解用于斐波那契系列的递归机制.

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

谢谢

Answer 1

要理解这一点,我将你的fib功能重命名为fibonacci.现在假设用户输入3然后递归调用可以理解为(>用于调用并且<用于返回):

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

通过方框图¹可以更清楚地理解这一点.

_{1.取自C如何由Deitel编程.}

Answer 2

想一些随机数并绘制执行步骤(如树).我总是用笔和纸来理解算法的东西.而且,总是试图将整个程序分解为每个微小的逻辑,并确保你理解它们中的每一个.我为你画了这张图.我很抱歉这样一个可怕的艺术家.

Answer 3

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

简而言之,就是你的"堆栈跟踪"......