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

Code 1:

代码1:

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

How can you use fibonacci if you haven't gotten done explaining what it is yet? I've been able to understand using recursion in other cases like this:

如果你还没有解释它是什么，你怎么能使用fibonacci ?我能够理解在其他情况下使用递归:

Code 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) ;
    }
}

In the case of code 2, though, n will eventually reach a point at which it doesn't satisfy n>0 and the method will stop calling itself recursively. In the case of code 2, though, I don't see how it would be able to get itself from 1 if n=1 was the starting point to 2 and 3 and 5 and so on. Also, I don't see how the line return fibonacci (n-1) + fibonacci (n-2) would work since fibonacci (n-2) has to contain in some sense fibonacci (n-1) in order to work, but it isn't there yet.

在代码2的情况下，n最终会到达一个不满足n>的点，这个方法会停止递归地调用自己。在代码2的情况下，我不知道如果n=1是2 3 5的起始点，它是如何从1开始的。另外，我也不知道返回fibonacci (n-1) + fibonacci (n-2)的行是如何工作的，因为fibonacci (n-2)必须包含某种意义上的fibonacci (n-1)才能工作，但是还没有。

The book I'm looking at says it will work. How does it work?

我正在看的那本书说它会有用的。它是如何工作的呢?

9 个解决方案

#1

Well, putting aside what a compiler actually does to your code (it's horrible, yet beautiful) and what how a CPU actually interprets your code (likewise), there's a fairly simple solution.

抛开编译器对代码的实际作用(它很糟糕，但很漂亮)和CPU对代码的实际解释(同样)，有一个相当简单的解决方案。

Consider these text instructions:

考虑这些文本指令:

To sort numbered blocks:

分类编号:

1. pick a random block.
2. 选择一个随机的块。
3. if it is the only block, stop.
4. 如果它是唯一的块，停止。
5. move the blocks with lower numbers to the left side, higher numbers to the right.
6. 把数字较小的方块移到左边，数字较大的方块移到右边。
7. sort the lower-numbered blocks.
8. 那种形式的块。
9. sort the higher-numbered blocks.
10. 排序编号较大的块。

When you get to instructions 4 and 5, you are being asked to start the whole process over again. However, this isn't a problem, because you still know how to start the process, and when it all works out in the end, you've got a bunch of sorted blocks. You could cover the instructions with slips of paper and they wouldn't be any harder to follow.

当你得到指令4和5，你被要求重新开始整个过程。然而，这并不是问题，因为你仍然知道如何开始这个过程，当它最终完成时，你得到了一堆有序的块。你可以用一张张纸盖住说明书，这样就不会很难遵循了。

#2

In the case of code 2 though n will eventualy reach a point at which it doesnt satisfy n>0 and the method will stop calling itself recursivly

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

to make it look similar you can replace condition if (n == 0 || n == 1) with if (n < 2)

为了使它看起来相似，如果(n == 0 || | n == 1)和if (n < 2)

Also i don't see how the line `return fibonacci (n-1) + fibonacci (n-2) would work since fibbonacci n-2 has to contain in some sense fibonacci n-1 in order to wrok but it isn't there yet.

我也不知道这一行'返回fibonacci (n-1) + fibonacci (n-2)是如何工作的，因为fibbonacci n-2必须包含某种意义上的fibonacci n-1才能实现wrok，但它还没有实现。

I suspect you wanted to write: "since fibbonacci n-1 has to contain in some sense fibonacci n-2"
If I'm right, then you will see from the example below, that actually fibonacci (n-2) will be called twice for every recursion level (fibonacci(1) in the example):
1. when executing fibonacci (n-2) on the current step
2. when executing fibonacci ((n-1)-1) on the next step

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

(Also take a closer look at the Spike's comment)

(也可以仔细看看斯派克的评论)

Suppose you call fibonacci(3), then call stack for fibonacci will be like this:
(Veer provided more detailed explanation)

假设您调用fibonacci(3)，那么对fibonacci的调用堆栈应该是这样的:(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

Note, that adding up in fibonacci(n) takes place only after all functions for smaller args return (i.e. fibonacci(n-1), fibonacci(n-2)... fibonacci(2), fibonacci(1), fibonacci(0))

注意，斐波那契数列(n)中的累加只在所有函数之后发生，以获得较小的args返回(即斐波那契数列(n-1)、斐波那契数列(n-2)……斐波纳契(2),斐波纳契(1),斐波纳契(0))

To see what is going on with call stack for bigger numbers you could run this code.

要了解调用堆栈的情况，您可以运行这段代码。

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);
}

#3

The trick is that the first call to fibonacci() doesn't return until its calls to fibonacci() have returned.

诀窍在于，第一个对fibonacci()的调用直到它对fibonacci()的调用返回时才返回。

You end up with call after call to fibonacci() on the stack, none of which return, until you get to the base case of n == 0 || n == 1. At this point the (potentially huge) stack of fibonacci() calls starts to unwind back towards the first call.

最后调用堆栈上的fibonacci()，直到得到n = 0 || n = 1的基本情况。此时，fibonacci()调用的堆栈(可能很大)开始向第一个调用展开。

Once you get your mind around it, it's kind of beautiful, until your stack overflows.

一旦你把注意力放在它上面，它就会变得很美，直到你的堆栈溢出。

#4

"How can you use Fibonacci if you haven't gotten done explaining what it is yet?"

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

This is an interesting way to question recursion. Here's part of an answer: While you're defining Fibonacci, it hasn't been defined yet, but it has been declared. The compiler knows that there is a thing called Fibonacci, and that it will be a function of type int -> int and that it will be defined whenever the program runs.

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

In fact, this is how all identifiers in C programs work, not just recursive ones. The compiler determines what things have been declared, and then goes through the program pointing uses of those things to where the things actually are (gross oversimplification).

实际上，这就是C程序中所有标识符的工作方式，而不仅仅是递归标识符。编译器确定已声明的内容，然后通过程序将这些内容的使用指向实际的内容(粗略地过度简化)。

#5

Let me walkthrough the execution considering n=3. Hope it helps.

考虑到n=3，让我粗略地看一下执行过程。希望它可以帮助。

When n=3 => if condition fails and else executes

当n=3 =>时，如果条件失败，则执行else

return fibonacci (2) + fibonacci (1);  

Split the statement:

将声明:

1. Find the value of fibonacci(2)
2. 找到fibonacci(2)的值
3. Find the value of fibonacci(1)
   // Note that it is not fib(n-2) and it is not going to require fib(n-1) for its execution. It is independent. This applies to step 1 also.
4. 找到fibonacci(1) // /注意，它不是fib(n-2)，它执行时不需要fib(n-1)。它是独立的。这也适用于步骤1。
5. Add both values
6. 添加两个值
7. return the summed up value
8. 返回汇总值

The way it gets executed(Expanding the above four steps):

执行方式(扩展以上四个步骤):

1. Find the value of fibonacci(2)

   找到fibonacci(2)的值

   1. if fails, else executes
   2. 如果失败,否则执行
   3. fibonacci(1)
      1. if executes
      2. 如果执行
      3. value '1' is returned to step 1.2. and the control goes to step 1.3.
      4. 值“1”返回到步骤1.2。控制步骤是步骤1。3。
   4. fibonacci(1)如果执行值“1”返回到步骤1.2。控制步骤是步骤1。3。
   5. fibonacci(0)
      1. if executes
      2. 如果执行
      3. value '1' is returned to step 1.3. and the control goes to step 1.4.
      4. 值'1'返回到步骤1.3。控制步骤是1。4。
   6. fibonacci(0)如果执行值'1'返回到步骤1.3。控制步骤是1。4。
   7. Add both
      1. sum=1+1=2 //from steps 1.2.2. and 1.3.2.
      2. 金额= 1 + 1 = 2 / /步骤1.2.2。1.3.2。
   8. 从步骤1.2.2中添加两个sum=1+1=2 /。1.3.2。
   9. return sum // value '2' is returned to step 1. and the control goes to step 2
      
   10. 返回sum /值'2'返回到步骤1。控制转到第二步

2. Find the value of fibonacci(1)

   找到fibonacci(1)的值

   1. if executes
   2. 如果执行
   3. value '1' is returned
   4. 返回值“1”

3. Add both values

   添加两个值

   1. sum=2+1 //from steps 1.5. and 2.2.
   2. 和= 2 + 1 / /从步骤1.5。和2.2。
4. return the summed up value //sum=3
5. 返回汇总值//sum=3。

#6

Try to draw an illustration yourself, you will eventually see how it works. Just be clear that when a function call is made, it will fetch its return value first. Simple.

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

#7

Try debugging and use watches to know the state of the variable

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

#8

Understanding recursion requires also knowing how the call stack works i.e. how functions call each other.
If the function didn't have the condition to stop if n==0 or n==1, then the function would call itself recursively forever. It works because eventually, the function is going to petter out and return 1. at that point, the return fibonacci (n-1) + fibonacci (n-2) will also return with a value, and the call stack gets cleaned up really quickly.

理解递归还需要了解调用堆栈的工作方式，即函数之间的调用方式。如果函数没有条件在n= 0或n==1时停止，那么函数将永远递归地调用自己。它是有效的，因为最终，函数会输出并返回1。在这一点上，返回fibonacci (n-1) + fibonacci (n-2)也会返回一个值，调用堆栈很快就会被清理掉。

#9

I'll explain what your PC is doing when executing that piece of code with an example:

我将用一个例子来解释您的PC在执行这段代码时正在做什么:

Imagine you're standing in a very big room. In the room next to this room you have massive amounts of paper, pens and tables. Now we're going to calculate fibonacci(3):

想象你站在一个很大的房间里。在这个房间旁边的房间里，你有大量的纸、笔和桌子。现在我们来计算斐波那契数列(3)

We take a table and put it somewhere in the room. On the table we place a paper and we write "n=3" on it. We then ask ourselves "hmm, is 3 equal to 0 or 1?". The answer is no, so we will do "return fibonacci (n-1) + fibonacci (n-2);".

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

There's a problem however, we have no idea what "fibonacci (n-1)" and "fibonacci (n-2)" actually do. Hence, we take two more tables and place them to the left and right of our original table with a paper on both of them, saying "n=2" and "n=1".

但是有一个问题，我们不知道“fibonacci (n-1)”和“fibonacci (n-2)”实际上做了什么。因此，我们再取两个表，把它们分别放在原始表的左边和右边，在这两个表上都写着“n=2”和“n=1”。

We start with the left table, and wonder "is 2 equal to 0 or 1?". Of course, the answer is no, so we will once again place two tables next to this table, with "n=1" and "n=0" on them.

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

Still following? This is what the room looks like:

还在下面吗?这就是这个房间的样子:

n=1

n = 1

n=2 n=3 n=1

n = 2 n = 3 = 1

n=0

n = 0

We start with the table with "n=1", and hey, 1 is equal to 1, so we can actually return something useful! We write "1" on another paper and go back to the table with "n=2" on it. We place the paper on the table and go to the other table, because we still don't know what we're going to do with that other table.

我们从“n=1”的表格开始，嘿，1等于1，所以我们可以返回一些有用的东西!我们把“1”写在另一张纸上，然后回到写有“n=2”的表格。我们把纸放在桌子上，放到另一张桌子上，因为我们仍然不知道我们要怎么处理另一张桌子。

"n=0" of course returns 1 as well, so we write that on a paper, go back to the n=2 table and put the paper there. At this point, there are two papers on this table with the return values of the tables with "n=1" and "n=0" on them, so we can compute that the result of this method call is actually 2, so we write it on a paper and put it on the table with "n=3" on it.

"n=0"当然也会返回1，我们把它写在纸上，回到n=2表格，把纸放在那里。在这一点上,有两篇论文在这个表的返回值表“n = 1”和“n = 0”,所以我们可以计算,该方法调用的结果实际上是2,所以我们把它写在纸上,放在桌上,“n = 3”。

We then go to the table with "n=1" on it all the way to the right, and we can immediately write 1 on a paper and put it back on the table with "n=3" on it. After that, we finally have enough information to say that fibonacci(3) returns 3.

然后我们用“n=1”的方式，一直到右边，我们可以马上把1写在纸上，然后把它放回到桌子上，上面写着“n=3”。之后，我们终于有了足够的信息来说明fibonacci(3)返回3。

---

It's important to know that the code you are writing is nothing more than a recipe. All the compiler does is transform that recipe in another recipe your PC can understand. If the code is completely bogus, like this:

重要的是要知道，您所编写的代码只不过是一个菜谱。编译器所做的就是在你的电脑能理解的另一个配方中转换那个配方。如果代码完全是假的，比如:

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

will simply loop endlessly, or as in my example, you'll keep on placing more and more tables without actually getting anywhere useful. Your compiler doesn't care what fibonacci(n-1) or fibonacci(n-2) actually do.

将只是无休止地循环，或者像我的示例那样，您将继续放置越来越多的表，而实际上没有得到任何有用的东西。编译器不关心fibonacci(n-1)或fibonacci(n-2)实际上做什么。