慢递推法[复制]

我在面试中被问到这个问题。下面的算法输出非常好,但是对于较大的输入参数来说,它非常慢。如何在不改变计算逻辑的情况下提高其性能?

    public static int SomeAlgo(int n)
    {
        if ((n == 0) || (n == 1))
        {
            return n;
        }
        else
        {
            return SomeAlgo(n - 1) + SomeAlgo(n - 2);
        }
   }

从参数值40开始变得非常缓慢。 我使用以下代码检查执行所需的时间:

static void Main(string[] args)
{
    var watch = System.Diagnostics.Stopwatch.StartNew();

    Console.WriteLine("Algo Output: " + SomeAlgo(40));

    watch.Stop();
    var elapsedMs = watch.ElapsedMilliseconds;
    Console.WriteLine("Time taken in ms: " + elapsedMs);
    Console.ReadLine();
}