2

在斐波那契数列中，我见过递归调用相同方法两次的常规实现：

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

现在这种方法不是我所看到的完全复制或解决问题的正确方法，但我已经看到两种方法像上面一样加在一起。所以该方法不是递归调用的，而是递归调用两次。在 C# 中编写这样的代码时究竟会发生什么？这两种方法是否在单独的线程上运行？引擎盖下发生了什么？

4

4 回答 4

8

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

于 2008-12-26T00:57:20.093 回答
5

这是考虑计算机的工作方式很有用的时候之一。

让我们从函数开始。我将用 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 调用fib()，也就是 0

   return 0 + fib(2-1)

用 1调用fib()

   return 0 + 1

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

n>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) 的示例；不过，我敢打赌，如果你这样做，你会成功的。

小测验：为什么迭代版本的效率如此之高？

于 2008-12-26T01:47:33.533 回答
0

它们按顺序进行估值。iefibonacci(1)在 is 之前被评估fibonacci(2)。如果您想将其可视化，则需要先从第一个调用树（使用它自己的“拆分递归”）向下走，然后再向下走第二个三棵树。

顺便说一句，这通常用作如何不使用递归的示例，因为这是评估斐波那契数列的一种明显但低效的方式。首选选项是迭代方法（计算第一个数字，然后是下一个数字，等等，直到所需的数字），或者更好的是封闭形式的方程。

于 2008-12-26T01:00:33.223 回答
0

在 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这个实现的非常小的值也可能没有用。如果您需要性能，最好自己处理状态来避免递归调用。

于 2008-12-26T19:38:40.093 回答