我无法理解这个Fibonacci程序流程

所以我是编程和思想世界的新手，我会拿起一本书来开始学习。 我买了C＃3rd Edition的玩家指南和它给你的一个小作业，让我很难过。 我一步一步地调试它以帮助我理解，但程序的流程对我来说毫无意义。 这里是。

static void Main(string[] args) { for (int index = 1; index <= 10; index++) { Console.WriteLine(Fibonacci(index)); } Console.ReadKey(); } /// 
 /// Returns a number from the Fibonacci sequence, starting at 1. /// Note that this implementation is not very optimized, and can /// take a very long time if you're looking up large numbers. /// 
 ///  ///  static ulong Fibonacci(int number) { if (number == 1) { return 1; } if (number == 2) { return 1; } return Fibonacci(number - 1) + Fibonacci(number - 2); } 

它通过for循环运行的前两次打印出’1’和’1’，因为第一次通过索引是’1’使得第一个if语句为true而第二次通过索引是’2’使得第二个if语句为真。 但是当它第三次运行并且索引变为3时它会转到返回语句，如果我的数学是正确的（3-1）+（3-2）等于3，这是正确的。 所以我希望它从方法返回3中断并将其写入控制台窗口，但它没有。 相反，这次再次运行该方法说这个数字的值是2.（好吧??）至少它应该停在第二个if语句并再次重新打印’1’。 不，它忽略了该行再次击中return语句。 这到底是怎么回事？ 请解释一下这个逻辑。

Answer 1

这种递归地狱有很好的例证。

请注意，该插图适用于循环的一次迭代

此外，它是为此代码绘制的：

 return Fibonacci(number - 2) + Fibonacci(number - 1); 

如果你有反向添加，正确的程序流程将与下图所示的相反。

图片来自： http ： //composingprograms.com/pages/28-efficiency.html

我称它为地狱有两个原因：

难以阅读开发人员

第一次使用参数6调用fib函数时，它首先调用fib（4）（树的左侧部分），然后，当它结束时，调用fib（5）（树的右侧部分）。

然而，递归对于某些情况可能非常有用，但是这个学校一个绝对不适合这种递归。 代码的目的不是只由编译器读取，它也应由开发人员阅读。

低效

正如您所看到的，一些fib（n）被称为具有相同n的多次。

最后，这个递归算法是O（2 ^ n） ，这对这个问题非常不利

循环中效率更低

请记住，插图仅适用于一次迭代！ 你可以为每个n绘制一个这样的fib（n）图。

使用此方法，您将丢失先前计算的每个值，而不是重新使用它们来计算下一个值。 这个循环具有复杂度O（n * 2 ^ n）

Answer 2

好吧，这是一个不那么简单的递归示例，并且最糟糕的是，它正在循环中执行……我几乎不会用什么来教人们递归是什么。

因此，递归的重点是函数会一遍又一遍地执行，直到它满足停止条件（如果它永远不会满足或者甚至不存在，它将创建一个无限递归，大多数时候不是好事）。

递归的典型例子是计算阶乘（如果你不记得它是如何工作的，5！= 5 * 4 * 3 * 2 * 1）。

因此，阶乘递归方法的实现将是这样的：

 Int64 Factorial(int input) { if(input < 0) { throw new ArgumentOutOfRangeException("Input must be 0 or higher."); } if(input < 2) { return 1; } return input * Factorial(input - 1); } 

（0！= 1，-3！无效......）

现在，假设您使用数字3调用此方法：
Factorial(3)将返回3 * Factorial(3-1) 。
同样， Factorial(2)将返回2 * Factorial(2-1) 。
Factorial(1)将简单地返回1 。
综合因素Factorial(3)将返回3 * 2 * 1即3! 。

现在，在你的情况下， Fibonacci递归方法停止条件是数字是1或2，但它自己调用两次： Fibonacci(number - 1) + Fibonacci(number - 2); 。 最糟糕的是，它是从for循环内部执行的，通过索引（从1到10）计算Fibonacci序列上的数字。

让我们来看看Fibonacci(3)作用：

Fibonacci(3)将返回Fibonacci(3-1) + Fibonacci(3-2) 。
Fibonacci(2)将返回1 。
Fibonacci(1)将返回1 。

所以， Fibonacci(3)将返回1 + 1。

我们来看下一个数字：

Fibonacci(4)将返回Fibonacci(4-1) + Fibonacci(4-2) 。
我们已经计算出Fibonacci(3)返回2，我们知道Fibonacci(2)将返回1，所以Fibonacci(4)将返回3
（如果你想进入每个电话，则为1 + 1 + 1）。

同样， Fibonacci(5)将返回Fibonacci(5-1) + Fibonacci(5-2) - 所以它是3 + 2等等（ Fibonacci(6)将返回5 + 3， Fibonacci(7)将返回8 + 5 ）。