递归函数如何迭代？

Question

可能是一个非常初级的问题，但一直令人难以置信。

我有一个斐波那契数列的例子。

fib(int n) {
    if (n <= 1) { //Base Case
        return n;
    }

    return fib(n - 1) + fib(n - 2)
}

所以我主要对理解函数如何迭代有问题，但它仍然没有有道理，当我一步一步打印每个迭代时。

算法本身有效，但序列如何随着时间变小，最终满足基本情况的条件？

例如，如果我们传入 n=6，第一个数字应该是 9，下一步 n=11，然后它会变得更大。但是当我打印它时，算法从 6-0 开始倒计时，然后我得到 0 到 2 之间的随机数，直到它给我正确的数字。

Answer 1

当你传入 n=6 时，你的函数被调用了两次，分别是 n=5 和 n=4

对于 n=5，它被调用两次，n=4 和 n=3

对于 n=4，它被调用两次，n=3 和 n=2，

...等等

最终，所有调用都变为 n=1 或 n=0，其中您的第一个 if 语句停止递归。

Answer 2

您声明您已打印所有值以了解发生了什么。
我怀疑您只打印了值，没有说明该值出现的原因。
这是修改后的代码版本，它告诉您有关值的更详细的故事。
请注意，该程序非常健忘，无法记住计算和使用后的值。如果再次需要相同的值，它会很乐意再次计算。

#include <stdio.h>

fib(int n){
    int retValue=0;
  printf("Trying to determine fibonacci at index %d.", n);
  if(n<=1){ //Base Case
    printf(" Easy, it is %d.\n", n);
    return n;
    }
   printf(" No idea. But I could sum up the fibonaccis at index %d and index %d.\n", n-1, n-2);
   retValue= fib(n-1)+fib(n-2);
   printf("I now know the fibonaccis at index %d and at index %d, their sum is %d.\n", n-1, n-2, retValue);
   return retValue;
}

int main()
{
    const int TryWith = 6;
    
    printf ("The fibonacci at index %d is %d.\n", TryWith, fib(TryWith));

    return 0;
}

输出为：

Trying to determine fibonacci at index 6. No idea. But I could sum up the fibonaccis at index 5 and index 4.
Trying to determine fibonacci at index 5. No idea. But I could sum up the fibonaccis at index 4 and index 3.
Trying to determine fibonacci at index 4. No idea. But I could sum up the fibonaccis at index 3 and index 2.
Trying to determine fibonacci at index 3. No idea. But I could sum up the fibonaccis at index 2 and index 1.
Trying to determine fibonacci at index 2. No idea. But I could sum up the fibonaccis at index 1 and index 0.
Trying to determine fibonacci at index 1. Easy, it is 1.
Trying to determine fibonacci at index 0. Easy, it is 0.
I now know the fibonaccis at index 1 and at index 0, their sum is 1.
Trying to determine fibonacci at index 1. Easy, it is 1.
I now know the fibonaccis at index 2 and at index 1, their sum is 2.
Trying to determine fibonacci at index 2. No idea. But I could sum up the fibonaccis at index 1 and index 0.
Trying to determine fibonacci at index 1. Easy, it is 1.
Trying to determine fibonacci at index 0. Easy, it is 0.
I now know the fibonaccis at index 1 and at index 0, their sum is 1.
I now know the fibonaccis at index 3 and at index 2, their sum is 3.
Trying to determine fibonacci at index 3. No idea. But I could sum up the fibonaccis at index 2 and index 1.
Trying to determine fibonacci at index 2. No idea. But I could sum up the fibonaccis at index 1 and index 0.
Trying to determine fibonacci at index 1. Easy, it is 1.
Trying to determine fibonacci at index 0. Easy, it is 0.
I now know the fibonaccis at index 1 and at index 0, their sum is 1.
Trying to determine fibonacci at index 1. Easy, it is 1.
I now know the fibonaccis at index 2 and at index 1, their sum is 2.
I now know the fibonaccis at index 4 and at index 3, their sum is 5.
Trying to determine fibonacci at index 4. No idea. But I could sum up the fibonaccis at index 3 and index 2.
Trying to determine fibonacci at index 3. No idea. But I could sum up the fibonaccis at index 2 and index 1.
Trying to determine fibonacci at index 2. No idea. But I could sum up the fibonaccis at index 1 and index 0.
Trying to determine fibonacci at index 1. Easy, it is 1.
Trying to determine fibonacci at index 0. Easy, it is 0.
I now know the fibonaccis at index 1 and at index 0, their sum is 1.
Trying to determine fibonacci at index 1. Easy, it is 1.
I now know the fibonaccis at index 2 and at index 1, their sum is 2.
Trying to determine fibonacci at index 2. No idea. But I could sum up the fibonaccis at index 1 and index 0.
Trying to determine fibonacci at index 1. Easy, it is 1.
Trying to determine fibonacci at index 0. Easy, it is 0.
I now know the fibonaccis at index 1 and at index 0, their sum is 1.
I now know the fibonaccis at index 3 and at index 2, their sum is 3.
I now know the fibonaccis at index 5 and at index 4, their sum is 8.
The fibonacci at index 6 is 8.

Answer 3

n 永远不会改变。它不会变小。相反，每个调用都有自己的 n.

让我们看一个更简单但非常相似的例子。

int fact(int n) {
   if (n <= 1) {
      return 1;
   }

  return n * fact(n-1);
}

fact(1) 是 1。那很简单。
fact(2) 是 2 * fact(1)。由上可知，fact(1)是1，所以fact(2)是2 * 1，也就是2.
fact(3)就是3 * fact(2)，就是3 * 2，就是6。
fact(4)就是4 * fact(3)，就是4 * 6，就是24。
fact(5)就是5 * fact(4)，就是5 * 24，就是120。
等等

斐波那契非常相似。

fib(0) 是 1
fib(1) 是 1
fib(2)就是fib(1) + fib(0)，就是1 + 1，就是2
fib(3)就是fib(2) + fib(1)，也就是2 + 1，就是3
fib(4)就是fib(3) + fib(2)，就是3 + 2，就是5
fib(5)就是fib(4) + fib(3)，就是5 + 3，就是8
等

这比上面暗示的要多得多。

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

fib(5) 总共调用了 15 次 fib！

fib(0): 1 个调用。
fib(1)：1 个电话。
fib(2): 3 个调用。
fib(3)：5 个调用。
fib(4): 9 次调用。
fib(5): 15 次调用。
等

（这个数列和斐波那契数列非常相似！）

Answer 4

递归函数的基本特征是它调用自身。递归函数并不像您所理解的那样迭代。相反，它会反复出现 occurs。

在你的 fib 函数中，调用自身的部分在 return.

return fib(n - 1) + fib(n - 2)

在这种情况下，它实际上调用了自己两次。首先，输入变量减 1 fib(n - 1)，其次输入变量减 2 fib(n - 2)，它一直调用自己，直到 n 小于或等于 1。一旦到达在这种情况下，函数开始 return 返回数字。首先，它 returns 0 和 1 但之后它开始 return 将数字相加。执行步骤见@cptFracassa的回答。

注意事项；如果递归函数没有 base/exit 情况，那么它只会不断地调用自己，直到您终止进程或机器发生错误。在您的情况下，基本情况是 if 最终停止调用自身而只是 return 一个数字。

Answer 5

了解递归函数如何迭代的一种方法是尝试使用传统的命令式循环来实现递归算法。

函数调用通常被解释为将一些数据压入调用堆栈的操作，然后调整堆栈引用框架，然后调用的函数对堆栈顶部的参数进行操作。函数调用的 return 从调用堆栈弹出数据，函数结果在调用点 returned 给调用者。

递归调用只是一个函数调用自身。要仅使用命令式循环来模拟调用，我们需要一个堆栈。让我们首先定义一些栈操作，以及栈帧是什么样的。

#define MAX_STACK_SIZE 256

typedef struct {
    enum { INIT, ONE, DONE } ra;
    int n;
    int result;
} frame_type;

#define PUSH(...) stack[head++] = ((frame_type){__VA_ARGS__})
#define POP()     stack[--head]
#define TOP()     stack[head-1]
#define EMPTY()   (head == 0)

ra 模拟一个 return 地址，这是被调用函数知道如何 return 给调用者的方式。 n是入参，result是存放函数调用结果的地方。

递归调用将用循环模拟。 CALL() 宏显示保留正确的 return 地址，将新的堆栈帧压入堆栈以启动递归调用，并使用 continue 重新启动循环，从而使用新的函数启动函数堆栈框架。

#define CALL(N) \
        TOP().ra = top.ra + 1; \
        PUSH(INIT, (N), 0); \
        continue

RET() 宏从递归调用中模拟 returning。它弹出当前函数调用堆栈帧，然后将计算结果存储到调用者的结果变量中。使用 continue 重新启动循环允许调用者在被调用函数的 return 之后的适当位置继续。

#define RET(X) \
        POP(); \
        TOP().result += (X); \
        continue

那么现在，让我们看看 fib() 函数使用这些宏会是什么样子。

A stack 和 head 被定义为为函数提供一个实际堆栈以使用宏进行操作。然后，有一些引导代码为 stack 初始函数调用提供一些起始上下文。

while 实现了传统的命令式循环，用于模拟递归迭代。 top用于保留当前栈帧，switch语句用于跳转到适当的return地址。

int fib(int n) {
    frame_type stack[MAX_STACK_SIZE];
    int head = 0;

    PUSH(DONE, 0, 0); // Bootstrapping call
    PUSH(INIT, n, 0);
    while (head > 1) {
        frame_type top = TOP();
        switch (top.ra) {
        case INIT: if (top.n < 2) {
                       RET(top.n);
                   } else {
                       CALL(top.n-1);
        case ONE:      CALL(top.n-2);
                   }
        case DONE: if (head == 1) break;
                   RET(top.result);
        }
    }
    POP();
    assert(EMPTY());
    return stack->result;
}

Try it online!

递归函数如何迭代？

How does a recursive function iterate?

c

algorithm

recursion

fibonacci