递归阶乘的速度快得令人怀疑

本文关键字：怀疑 速度快 阶乘 递归 | 更新日期: 2023-09-27 18:08:45

由于问题的高复杂性，阶乘的递归计算应该很慢。为什么我的基本实现不是慢得令人痛苦?我很好奇，因为这应该是一个糟糕方法的教科书范例。

是因为c#程序中的一些内部优化或缓存结果吗?

using System;
using System.Diagnostics;
using System.Numerics;
namespace FactorialRecursion
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch stopwatch = new Stopwatch();
            for (int i = 0; i < 4000; i++)
            { 
                stopwatch.Reset();
                stopwatch.Start();
                Factorial(i);
                stopwatch.Stop();
                Console.WriteLine($"{i}! = ({stopwatch.Elapsed})");
            }
            Console.ReadKey();
        }
        static BigInteger Factorial(BigInteger number)
        {
            if (number <= 1)
                return 1;
            return number * Factorial(number - 1);
        }
    }
}

结果如下:

3990! = (00:00:00.0144319)
3991! = (00:00:00.0149198)
3992! = (00:00:00.0159502)
3993! = (00:00:00.0116784)
3994! = (00:00:00.0104608)
3995! = (00:00:00.0122931)
3996! = (00:00:00.0128695)
3997! = (00:00:00.0131792)
3998! = (00:00:00.0142510)
3999! = (00:00:00.0145544)

递归阶乘的速度快得令人怀疑

递归方法在阶乘计算中被认为是不好的，因为堆栈内存消耗，而不是因为速度。

如果你取一个足够大的数，你很快就会用完内存来计算阶乘，而不是说你会很慢(如果你用来存储阶乘ed值的内存足够大来存储它)。

使用递归和迭代的阶乘函数的时间复杂度是相同的，尽管递归使用额外的内存空间将函数调用存储在堆栈中。但是，就时间复杂度而言，在这种情况下是一样的，因为递归间接地充当循环。当递归试图一次又一次地计算相同的值时，递归的时间复杂度比迭代的时间复杂度更差，这在迭代中是可以避免的。(例如:-使用不带记忆的递归的Fibonacci num gen具有O(2^n)最坏情况时间复杂度，而它的迭代对应具有O(n)最坏情况时间复杂度。

有可能JIT正在使用尾部递归优化，这有助于加快速度，有关更多信息，请参阅此。在没有访问您的环境的情况下，很难确定。

给出的方法被认为是不利的，因为它使用了大量的堆栈内存来处理更大的阶乘。它与速度关系不大，更多的是与它消耗了多少内存有关。但是，如果您知道尾部递归将在那里发生(由JIT决定，而不是由您决定，所以不要指望它)，那么这真的无关紧要。

相关文章：