Question

在斐波那契数列中，我看过传统实现方式，这种方式递归调用相同方法两次：

public void fibonacci(int i)
{
fibonacci(1) + fibonacci(2);
}

现在这种方法并不是我所见过的完全副本，也不是解决问题的正确方法，但是我见过类似以上的两种方法加在一起。因此，该方法不是递归调用，而是递归调用两次。在C#中编写这样的代码会发生什么？这两个方法会在单独的线程上运行吗？在幕后发生了什么？

Answer 1

这是那种时候，思考计算机的工作方式很有用。

让我们从函数开始。我将使用Python风格的伪代码编写它，因为我希望您暂时不考虑语言。

def fib(n):
    if n == 0: return 0
    if n == 1: return 1
    if n >  1: return fib(n-2) + fib(n-1)

现在让我们来介绍一下fib(2)。

fib(2)具有n>1，因此它采取第三个分支，

   return fib(2-2) + fib(2-1)

因此，它使用0调用，结果为0。

   return 0 + fib(2-1)

使用1调用fib()。

   return 0 + 1

现在我们看到了结果1。现在考虑fib(3)：

不小于1，因此

return fib(3-2)+fib(3-1)

而由于3-2等于1，我们将得到斐波那契数列第一项为fib(1)，即1。

return 1 + fib(3-1)

现在当我们调用 fib(3-1)，也就是 fib(2)时，我们没有直接的答案；n>1。因此，它变成了。

return 1 +
    return fib(2-2) + fib(2-1)

哪个变成

    return 0 + 1

我们回到之前的通话。

return 1 + 1

然后得到数值2。所以，你看，没有单独的线程，它只是在表达式中工作。我将其留作练习，以计算fib（4）的示例; 我打赌如果你做了，你会掌握它。

突发测试：为什么迭代版本要比传统版本具有大幅度的效率提升？

Answer 2

不，它们是一个接一个地被调用的。除非您明确要求（使用System.Threading的东西），否则不会创建其他线程。我不确定它们被调用的顺序，但我猜从左到右。C#规范中定义了它。

Answer 3

它们是按顺序进行评估的。即 fibonacci（1）在fibonacci（2）之前进行评估。如果您想可视化它，就要沿着第一个调用树（具有自己的“分裂递归”）向下，然后返回，再沿着第二个树向下走。

顺带一提，这通常被用作如何不使用递归的例子，因为这是一种显而易见但低效的方式来计算斐波那契数列。首选选择是迭代方法（计算出第一个数字，然后是下一个数字等，直到所需数字），或者，更好的是闭式方程式。

Answer 4

在C＃中，您可以轻松实现您建议的方法 - 它可能看起来像这样

public static int Fib(int i) {
   if (i == 0) return 0;
   if (i == 1) return 1;
   return Fib(i - 2) + Fib(i - 1);
}

然而，这里没有什么魔法。它只是一个递归调用跟随另一个。即所有代码在同一线程上按顺序运行。

由于每次迭代都有两个递归调用，性能也非常差，因此即使对于相当小的 i 值，这种实现也可能没有用处。如果您需要性能，最好通过自己处理状态来避免递归调用。