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

Question

代码 1：

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

fibonacci如果您还没有完成对它的解释，您将如何使用它？我已经能够理解在其他情况下使用递归，例如：

代码 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并且该方法将停止递归调用自身。n=1但是，在代码 2 的情况下，如果是 2 和 3 和 5 的起点，我看不出它如何能够从 1 中获取自身，依此类推。另外，我看不出这条线是如何return fibonacci (n-1) + fibonacci (n-2)工作的，因为fibonacci (n-2)必须在某种意义上包含fibonacci (n-1)才能工作，但它还没有。

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

score 12 · Accepted Answer

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

考虑以下文本说明：

要对编号的块进行排序：

选择一个随机块。
如果它是唯一的块，请停止。
将数字较小的块移到左侧，将数字较大的块移到右侧。
对编号较低的块进行排序。
对编号较高的块进行排序。

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

score 3 · Accepted Answer

在代码 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 才能工作，但事实并非如此还在那里。

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

（还可以仔细看看Spike 的评论）

假设你调用fibonacci(3)，那么fibonacci的调用栈会是这样的：（Veer 提供了更详细的解释）

n=3。斐波那契(3)  
n=3。fibonacci(2) // 调用 fibonacci(n-1)
   n=2。fibonacci(1) // 调用 fibonacci(n-1)
      n=1。返回 1
   n=2。fibonacci(0) // 调用 fibonacci(n-2)
      n=0。返回 1
   n=2。加起来，返回 2
n=3。fibonacci(1) //调用 fibonacci(n-2)
   n=1。返回 1
n=3。加起来，返回 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);
}

score 2 · Accepted Answer

诀窍是对 fibonacci() 的第一次调用不会返回，直到它对 fibonacci() 的调用返回。

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

一旦你开始考虑它，它就会很漂亮，直到你的堆栈溢出。

score 2 · Accepted Answer

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

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

事实上，这就是C 程序中所有标识符的工作方式，而不仅仅是递归标识符。编译器确定已声明的事物，然后通过程序将这些事物的用途指向事物实际所在的位置（过于简单化）。

score 2 · Accepted Answer

让我考虑 n=3 的执行情况。希望能帮助到你。

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

return fibonacci (2) + fibonacci (1);

拆分语句：

求斐波那契 (2) 的值
查找 fibonacci(1) 的值
// 注意它不是 fib(n-2) 并且它不需要 fib(n-1) 来执行它。它是独立的。这也适用于步骤 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 步
求斐波那契 (1) 的值
1. 如果执行
2. 返回值“1”
添加两个值
1. sum=2+1 //来自步骤 1.5。和 2.2。
返回总和值 //sum=3

score 1 · Accepted Answer

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

score 1 · Accepted Answer

1

尝试调试并使用手表了解变量的状态

于 2010-03-09T05:22:45.197 回答

score 1 · Accepted Answer

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

score 0 · Accepted Answer

我将通过一个示例解释您的 PC 在执行那段代码时正在做什么：

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

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

但是有一个问题，我们不知道“fibonacci (n-1)”和“fibonacci (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) 实际上做了什么。

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

9 回答 9

Related

Reference