c# - 看不懂这个斐波那契程序流程

Question

所以我是编程世界的新手，我想拿起一本书开始学习。我买了 A Players Guide to C# 3rd Edition，它给你的一个小家庭作业让我很困惑。我正在逐步调试它以帮助我理解，但程序的流程对我来说毫无意义。在这里。

      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 次运行并且索引变为 3 时，它会转到该 return 语句，如果我的数学是正确的，则 (3-1) + (3-2) 等于 3，这是有道理的。所以我希望它从方法 return 3 中断并将其写入控制台窗口，但它没有。相反，这次它再次运行该方法，说数字的值为 2。(好吗？？)至少它应该在第二个 if 语句处停止并再次重新打印“1”。不，它会忽略那行再次点击 return 语句。这到底是怎么回事？请解释一下这个逻辑。

Answer 1

有一个很好的例子说明了这种递归 hell 。

请注意，插图是针对循环的一次迭代

而且，它是为这段代码绘制的:

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

因为你有反向加法，正确的程序流程将与下图所示的流程相反。

图片拍摄于此:http://composingprograms.com/pages/28-efficiency.html

我称之为 hell 有两个原因:

开发者难以阅读

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

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

效率低下

如您所见，某些 fib(n) 被调用了多次，并且 n 相同。

最后，这个递归算法is O(2^n) , 这对于这个问题来说是相当糟糕的

在循环中效率更低

请记住，插图仅适用于一次迭代!你可以像这样为每个 n 画一个 fib(n) 的图。

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