java - 多次返回的递归混淆

Question

我仍然在思考递归，我想我已经掌握了一些基本的东西，比如阶乘。但是当 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) 步骤(这有意义吗)？如果是这样，这似乎很难想象。

Answer 1

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

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

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

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