我无法理解这个斐波那契程序流程

所以我对编程世界很陌生，我想我应该拿起一本书来开始学习。我买了《C# 玩家指南》第 3 版，它给你的小作业之一让我很困惑。我正在一步步调试它以帮助我理解，但程序的流程对我来说毫无意义。这里是。

      static void Main(string[] args)
        {
            for (int index = 1; index <= 10; index++)
            {
                Console.WriteLine(Fibonacci(index));
            }

            Console.ReadKey();
        }

        /// <summary>
        /// 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.
        /// </summary>
        /// <param name="number"></param>
        /// <returns></returns>
        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 语句为真，第二次通过索引是“2”，使得第二个 if 语句为真。但是当它第三次运行并且索引变为 3 时，它会转到 return 语句，如果我的数学正确的话 (3-1) + (3-2) 等于 3，这是有道理的。所以我希望它能从方法 return 3 中中断并将其写入控制台窗口，但事实并非如此。相反，这次它再次运行该方法，说数字的值为 2。（好吧？？） 好吧，至少它应该在第二个 if 语句处停止并再次重新打印“1”。不，它会忽略该行再次命中 return 语句。这到底是怎么回事？请解释一下这个逻辑。

有一个很好的例子来说明这种递归地狱。

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

而且，它是为此代码绘制的：

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

由于您进行了相反的加法，因此正确的程序流程将与下图所示相反。

图片是在这里拍摄的：http://compositingprograms.com/pages/28-efficiency.html http://composingprograms.com/pages/28-efficiency.html

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

对于开发者来说很难阅读

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

然而，递归对于某些情况可能非常有用，但是这所学校绝对不适合这种递归。代码的目的不仅仅是供编译器阅读，还供开发人员阅读。

效率低下

正如您所看到的，某些 fib(n) 使用相同的 n 被调用多次。

最后，这个递归算法是 O(2^n) https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence，这对于这个问题来说非常糟糕

循环效率更低

请记住，该插图仅适用于一次迭代！您可以为每个 n 绘制这样的 fib(n) 图表。

使用此方法，您将丢失之前计算的每个值，而不是重新使用它们来计算下一个值。该循环的复杂度为 O(n * 2^n)