递归调用两次相同的方法

在Fibonacci序列中,我已经看到了传统的实现,它们递归地调用相同的方法两次:

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

现在这个方法并不是我所看到的或者解决问题的正确方法的精确副本,但我已经看到如上所述将这两种方法加在一起.因此,该方法不是递归调用的,而是递归调用两次.在C#中编写这样的代码到底发生了什么？这两种方法是在单独的线程上运行的吗？引擎盖下发生了什么？

不,他们被称为一个接一个.除非您明确要求它(使用System.Threading的东西),否则不会创建其他线程.我不确定他们的命令是什么,但我猜是从左到右.C#规范肯定有它.

这是考虑计算机执行方式的有用时间之一.

让我们从这个功能开始吧.我将用Python风格的伪代码编写它,因为我希望你不要再考虑LANGUAGE了一秒钟.

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)

因此它调用fib()为0,即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.所以,你看,没有单独的线程,它只是在表达式中运行.我将把它作为练习来制定一个例子(4); 我打赌,如果你这样做,你会把它钉在上面.

流行测验:为什么迭代版本如此显着提高效率？