使用递归方法编写斐波那契数列是完全错误的!!
这是一个很久以前的著名示例,展示了好坏算法如何影响项目。
如果你用递归方式计算斐波那契数列,要计算到120
需要36年才能得出结果!!!
public static int Fibonacci(int x)
{ // bad fibonacci recursive code
if (x <= 1)
return 1;
return Fibonacci(x - 1) + Fibonacci(x - 2);
}
在.NET 4.0中,有一个新的类型名称BigInteger,您可以使用它来创建更好的函数。
使用System;
using System.Collections.Generic;
using System.Numerics; //需要对此程序集进行引用
namespace Fibonaci
{
public class CFibonacci
{
public static int Fibonacci(int x)
{
if (x <= 1)
return 1;
return Fibonacci(x - 1) + Fibonacci(x - 2);
}
public static IEnumerable<BigInteger> BigFib(Int64 toNumber)
{
BigInteger previous = 0;
BigInteger current = 1;
for (Int64 y = 1; y <= toNumber; y++)
{
var auxiliar = current;
current += previous;
previous = auxiliar;
yield return current;
}
}
}
}
你可以像这样使用它
using System;
using System.Linq;
namespace Fibonaci
{
class Program
{
static void Main()
{
foreach (var i in CFibonacci.BigFib(10))
{
Console.WriteLine("{0}", i);
}
var num = 12000;
var fib = CFibonacci.BigFib(num).Last();
Console.WriteLine("fib({0})={1}", num, fib);
Console.WriteLine("Press a key...");
Console.ReadKey();
}
}
}
在这种情况下,您可以在不到一秒钟的时间内计算出12000
。所以
使用递归方法并不总是一个好主意
上述代码来自Vahid Nasiri博客,他用波斯语写作