我仍然在思考递归,我想我已经掌握了一些基本的东西,比如阶乘。但是当 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 语句中,fibonacci(n-1) 是否完全重复,然后再进入 fibonacci(n-2) 步骤(这有意义吗)?如果是这样,这似乎很难想象。
最佳答案
是的,在另一个调用开始执行之前,一个调用将一直向下递归并返回。
Java 中的调用顺序是明确定义的:fibonacci(n-1)
在 fibonacci(n-2)
之前。
编辑:由于问题最初包含 [C++] 标记,这里是 C++ 部分的故事:两个调用之一仍然必须在另一个调用开始运行之前完成,但是一个,fibonacci(n-1)
或 fibonacci(n-2)
,未指定。
由于该函数没有副作用,因此两个调用中的哪一个先运行并不重要。唯一对理解递归很重要的是,在当前级别的调用返回之前,两个调用都必须完成,并且它们的结果必须加在一起。
关于java - 多次返回的递归混淆,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45697804/