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

Question

所以我是编程和思想世界的新手,我会拿起一本书来开始学习.我买了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语句为true而第二次通过索引是'2'使得第二个if语句为真.但是当它第三次运行并且索引转到3时它转到那个return语句,如果我的数学是正确的(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

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

难以阅读开发人员

第一次fib使用参数6调用函数时,它首先调用fib(4)(树的左侧部分),然后,当它结束时,调用fib(5)(树的右侧部分).

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

低效

正如您所看到的,一些fib(n)被称为具有相同n的多次.

最后,这个递归算法是O(2 ^ n),这对这个问题非常不利

循环中效率更低

请记住,插图仅用于一次迭代!你可以为每个n绘制一个这样的fib(n)图.

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