递归与多重回报的混淆

我仍然围绕递归进行思考，并且我认为我得到了像阶乘这样的基本类。但我想进一步澄清，当return语句是一个稍微复杂一些像下面的代码片段：递归与多重回报的混淆

/** 
* @param n >= 0 
* @return the nth Fibonacci number 
*/ 
public static int fibonacci(int n) { 
    if (n == 0 || n == 1) { 
     return 1; // base cases 
    } else { 
     return fibonacci(n-1) + fibonacci(n-2); // recursive step 
    } 
}

在return语句，确实斐波那契（N-1）完全重现通过，才去下来斐波那契（n-2）的步骤（这是否有道理）？如果是这样，这似乎很难设想。

来源

2017-08-15 MeeBee

如果很难想象，只需使用调试器浏览代码即可。这会告诉你*究竟发生了什么。 – tadman

假设上面是单线程的，是的。 –

'fibonacci（n-1）+ fibonacci（n-2）;'的顺序未指定，可以先执行 – CoryKramer

是的，在另一个开始执行之前，一个调用将一直递减并返回。

Java中的调用顺序是明确的：fibonacci(n-1)在fibonacci(n-2)之前。

编辑：由于这个问题最初包括[C++]标签，这里是C的故事++部分：两个调用之一仍然必须完成另一个开始运行之前，但哪一个，fibonacci(n-1)或fibonacci(n-2)，未指定。

由于该函数没有副作用，因此两个调用中的哪一个首先运行并不重要。对于理解递归唯一重要的是，在当前级别的调用返回之前，两个调用必须完成，并且它们的结果必须相加。

来源

2017-08-15 17:10:50 dasblinkenlight

现在你应该编辑你的答案，C++标签已被删除。 –

它的工作过程是这样：

斐波那契程序：

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

说明： 在斐波那契序列的每个项目是前两者之和。所以，按照递归算法。

所以，

fibonacci(5) = fibonacci(4) + fibonacci(3) 

fibonacci(3) = fibonacci(2) + fibonacci(1) 

fibonacci(4) = fibonacci(3) + fibonacci(2) 

fibonacci(2) = fibonacci(1) + fibonacci(0)

现在你已经知道fibonacci(1)==1 and fibonacci(0) == 0。所以，你可以随后计算其他值。

现在，

fibonacci(2) = 1+0 = 1 
fibonacci(3) = 1+1 = 2 
fibonacci(4) = 2+1 = 3 
fibonacci(5) = 3+2 = 5

来源

2017-08-15 17:38:45 user2862544

这不是比调用比自己不同的功能更加不同。它需要在调用函数对结果做任何事情之前完成。

finobacci(0); // ==> 1 (since n is zero, the base case is to return 1) 
fibonacci(1); // ==> 1 (since n is one, the base case is to return 1)

现在让我们尝试2这不是基本情况：

fibonacci(2);    // == (since it's not the base case) 
fibonacci(1) + fibonacci(0); // == (both calls to fibonacci we already haver done above) 
1 + 1      // ==> 2

在现实

所以会发生什么是呼叫到fibonacci2等待，而每两个递归调用的完成，只是就像System.out.println在继续下一行之前一直等到打印出参数一样。递归并不是那么特别。

琐事：这是斐波那契本人的原始系列。现代数学家开始以n作为基本案例结果的系列，使0, 1, 1, 2, ...系列而不是1, 1, 2, 3, ...。

来源

2017-08-15 18:06:46 Sylwester

@Hulk更正了评论。 – Sylwester

在多个递归程序调用本身与它的第一呼叫到达基本情况，直到在这种情况下斐波纳契（N-1）;之后，递归停止并返回其值，继续将该值调用到递归的第二部分斐波那契（n-2）。

如果您没有在程序中看到多次递归，则此 fibonacci recursion tree可能会有所帮助。

来源

2017-08-22 04:57:18 Gober

递归与多重回报的混淆

回答

相关问题