这里的递归是如何工作的？

Question

代码 1：

public static int fibonacci (int n){ 
    if (n == 0 || n == 1) { 
        return 1; 
    } else { 
        return fibonacci (n-1) + fibonacci (n-2); 
    }        
} 

如果您还没有解释完斐波那契的含义，那么如何使用斐波那契呢？我已经能够理解在其他情况下使用递归，如下所示：

代码 2：

class two 
{
    public static void two (int n) 
    {
        if (n>0) 
        {
            System.out.println (n) ;
            two (n-1) ;
        }
        else
        {
            return ;
        }
    } 

    public static void main (String[] arg) 
    {
        two (12) ;
    }
}

但是，在代码 2 的情况下，n 最终将达到不满足 的点n>0 并且该方法将停止递归调用自身。不过，就代码 2 而言，如果 n=1 是 2、3 和 5 等的起点，我不知道它如何能够从 1 开始。另外，我不明白 return fibonacci (n-1) + fibonacci (n-2) 行如何工作，因为 fibonacci (n-2) 必须包含从某种意义上说，fibonacci (n-1) 才能发挥作用，但目前还没有。

我正在看的书说它会起作用。它是如何运作的？

Answer 1

好吧，抛开编译器实际上对代码做了什么（它很可怕，但很漂亮）以及 CPU 实际如何解释代码（同样），有一个相当简单的解决方案。

考虑这些文本说明：

要对编号块进行排序：

1. 选择一个随机块。
2. 如果它是唯一的块，则停止。
3. 移动方块
   左侧的数字较低，
   右边的数字更大。
4. 对编号较低的块进行排序。
5. 对编号较大的块进行排序。

当您看到说明 4 和 5 时，系统会要求您重新开始整个过程​​。然而，这不是问题，因为您仍然知道如何开始该过程，并且当一切最终解决时，您将获得一堆已排序的块。你可以用纸条盖住说明，遵循它们也不会更困难。

Answer 2

在代码 2 的情况下，虽然 n 最终会到达一个不满足 n>0 的点，并且该方法将停止递归调用自身

以使其看起来相似，您可以替换条件 if (n == 0 || n == 1) 与 if (n < 2)

另外，我不明白“return fibonacci (n-1) + fibonacci (n-2)”行如何工作，因为 fibonacci n-2 在某种意义上必须包含 fibonacci n-1 才能工作，但它还没有。

我怀疑您想写：“因为斐波那契 n-1 在某种意义上必须包含斐波那契 n-2”
如果我是对的，那么您将从下面的示例中看到，实际上 fibonacci (n-2) 对于每个递归级别都会被调用两次 (fibonacci(1)在示例中）：
1. 在当前步骤执行fibonacci (n-2)时
2. 在下一步执行斐波那契 ((n-1)-1) 时

（另请仔细查看Spike 的评论）

假设您调用fibonacci(3)，则斐波那契的调用堆栈将如下所示：
（Veer 提供了更详细的解释）

n=3. fibonacci(3)  
n=3. fibonacci(2) // call to fibonacci(n-1)
   n=2. fibonacci(1) // call to fibonacci(n-1)
      n=1. returns 1
   n=2. fibonacci(0) // call to fibonacci(n-2)
      n=0. returns 1
   n=2. add up, returns 2
n=3. fibonacci(1) //call to fibonacci(n-2)
   n=1. returns 1
n=3. add up, returns 2 + 1

请注意，相加fibonacci(n) 仅在所有较小参数的函数返回后才发生（即 fibonacci(n-1)、fibonacci(n-2) >... fibonacci(2), fibonacci(1), fibonacci(0))

查看 调用堆栈 对于更大的数字，您可以运行此代码。

public static String doIndent( int tabCount ){
    String one_tab = new String("   ");
    String result = new String("");
    for( int i=0; i < tabCount; ++i )
       result += one_tab;
    return result;
}

public static int fibonacci( int n, int recursion_level )
{
    String prefix = doIndent(recursion_level) + "n=" + n + ". ";

    if (n == 0 || n == 1){
        System.out.println( prefix + "bottommost level, returning 1" );
        return 1;
    }
    else{
        System.out.println( prefix + "left fibonacci(" + (n-1) + ")" );
        int n_1 = fibonacci( n-1, recursion_level + 1 );

        System.out.println( prefix + "right fibonacci(" + (n-2) + ")" );
        int n_2 = fibonacci( n-2, recursion_level + 1 );

        System.out.println( prefix + "returning " + (n_1 + n_2) );
        return n_1 + n_2;
    }
}

public static void main( String[] args )
{
    fibonacci(5, 0);
}

Answer 3

诀窍在于，对 fibonacci() 的第一次调用只有在对 fibonacci() 的调用返回后才会返回。

你最终会在堆栈上调用一个又一个的 fibonacci() ，没有一个返回，直到你到达 n == 0 || 的基本情况。 n == 1。 此时，fibonacci() 调用的（可能很大）堆栈开始回退到第一个调用。

一旦你集中注意力，它就会变得很漂亮，直到你的堆栈溢出。

Answer 4

“如果你还没有解释完斐波那契是什么，你怎么能使用斐波那契呢？”

这是质疑递归的一种有趣的方式。以下是部分答案：当您定义斐波那契数时，它还没有被定义，但它已经被声明了。编译器知道有一个叫做 Fibonacci 的东西，并且它将是一个 int 类型的函数 -> int 并且它将在程序运行时被定义。

事实上，这就是 C 程序中所有标识符的工作方式，而不仅仅是递归标识符。编译器确定声明了哪些内容，然后遍历程序，将这些内容的使用指向这些内容的实际位置（严重过度简化）。

Answer 5

让我演练考虑 n=3 的执行过程。希望有帮助。

当n=3时=> if 条件失败，else 执行

return fibonacci (2) + fibonacci (1);  

拆分语句：

1. 求斐波那契(2) 的值
2. 求斐波那契(1) 的值
   // 请注意，它不是 fib(n-2)，也不需要 fib(n-1) 来执行。它是独立的。这也适用于步骤 1。
3. 将两个值相加
4. 返回总和

执行方式（扩展上述四个步骤）：

1. 查找斐波那契（2）的值

   1. 如果失败，则执行
   2. 斐波那契(1)
      1. 如果执行
      2. 值“1”返回到步骤 1.2。控制进入步骤1.3。
   3. 斐波那契(0)
      1. 如果执行
      2. 值“1”返回到步骤 1.3。然后控制进入步骤1.4。
   4. 同时添加
      1. sum=1+1=2 //来自步骤 1.2.2。和1.3.2。
   5. return sum // 值“2”返回到步骤 1。控制转到步骤 2

2. 查找 fibonacci(1) 的值

   1. 如果执行
   2. 返回值“1”

3. 将两个值相加

   1. sum=2+1 //来自步骤 1.5。和2.2。
4. 返回求和值 //sum=3

Answer 6

尝试自己画一个插图，你最终会看到它是如何工作的。请注意，当进行函数调用时，它将首先获取其返回值。简单的。

Answer 7

尝试调试并使用监视来了解变量的状态

Answer 8

了解递归还需要了解调用堆栈的工作原理，即函数如何相互调用。
如果函数没有在 n==0 或 n==1 时停止的条件，则函数将永远递归地调用自身。
它之所以有效，是因为最终，该函数将逐渐消失并返回 1。此时，返回 fibonacci (n-1) + fibonacci (n-2) 也将返回一个值，并且调用堆栈实际上会被清理干净迅速地。

Answer 9

我将用一个例子来解释你的电脑在执行这段代码时正在做什么：

想象你站在一个非常大的房间里。在这个房间旁边的房间里有大量的纸、笔和桌子。现在我们要计算斐波那契（3）：

我们拿一张桌子并将其放在房间的某个地方。我们在桌子上放一张纸，并在上面写上“n=3”。然后我们问自己“嗯，3 等于 0 还是 1？”。答案是否定的，所以我们会做“return fibonacci (n-1) + fibonacci (n-2);”。

然而有一个问题，我们不知道“斐波那契 (n-1)”和“斐波那契 (n-2)”实际上是做什么的。因此，我们再拿两张桌子，将它们放在原始桌子的左侧和右侧，并在两张桌子上贴上一张纸，上面写着“n=2”和“n=1”。

我们从左表开始，想知道“2 等于 0 还是 1？”。当然答案是否定的，所以我们再次在这个表旁边放置两个表，分别是“n=1”和“n=0”。

还在关注吗？这就是房间的样子：

n=1

n=2 n=3 n=1

n=0

我们从“n=1”的表开始，嘿，1 等于 1，所以我们实际上可以返回一些东西有用！我们在另一张纸上写下“1”，然后回到上面有“n=2”的表格。我们把纸放在桌子上，然后走到另一张桌子，因为我们仍然不知道要对另一张桌子做什么。

“n=0”当然也返回1，所以我们把它写在纸上，回到n=2表并将纸放在那里。此时，这张表上有两张纸，其返回值为“n=1”和“n=0”的表，所以我们可以计算出这个方法调用的结果实际上是2，所以我们把它写在纸上，放在桌子上，上面写着“n=3”。

然后我们一直向右走到上面有“n=1”的桌子，我们可以立即在纸上写下1，然后将其放回到上面有“n=3”的桌子上。之后，我们终于有足够的信息表明 fibonacci(3) 返回 3。

---

重要的是要知道您正在编写的代码只不过是一个菜谱。编译器所做的就是将该配方转换为您的 PC 可以理解的另一个配方。如果代码完全是伪造的，就像这样：

    public static int NotUseful()
    {
        return NotUseful();
    }

将简单地无限循环，或者像我的示例一样，您将继续放置越来越多的表，而实际上却没有任何有用的地方。您的编译器不关心 fibonacci(n-1) 或 fibonacci(n-2) 实际做什么。