C#斐波那契数列的各种算法【递归、循环、数组】比较
斐波那契数列，就是整数： 第三项 等于前两项之和.A(n)=A(n-2)+A(n-1).
例如：1,1,2,3,5,8,13,21,34,55,....
现在使用四种方式：
一、递归
二、For循环【使用临时变量】
三、For循环【无临时变量】
四、使用数组作为临时仓库
测试四种算法的性能。以及计算出从第几项开始，超过Int32的最大值
新建控制台应用程序FibonacciSequenceDemo
测试源程序如下：
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace FibonacciSequenceDemo
{
class Program
{
static void Main(string[] args)
{
Console.SetWindowSize(120, 30);
Task taskRecursion = Task.Run(() => { AlgorithmTimespan(GetFibonacciRecursion, nameof(GetFibonacciRecursion)); });
Task taskFor = Task.Run(() => { AlgorithmTimespan(GetFibonacciFor, nameof(GetFibonacciFor)); });
Task taskForNoTemp = Task.Run(() => { AlgorithmTimespan(GetFibonacciForNoTemp, nameof(GetFibonacciForNoTemp)); });
Task taskArray = Task.Run(() => { AlgorithmTimespan(GetFibonacciArray, nameof(GetFibonacciArray)); });
Task.WaitAll(taskRecursion, taskFor, taskForNoTemp, taskArray);
Console.WriteLine("-------------测试多次调用斐波那契数列方法的用时【获取第一个大于Int32的最大值】------------------");
taskRecursion = Task.Run(() => { AlgorithmTimespanMultiple(GetFibonacciRecursion, nameof(GetFibonacciRecursion)); });
taskFor = Task.Run(() => { AlgorithmTimespanMultiple(GetFibonacciFor, nameof(GetFibonacciFor)); });
taskForNoTemp = Task.Run(() => { AlgorithmTimespanMultiple(GetFibonacciForNoTemp, nameof(GetFibonacciForNoTemp)); });
taskArray = Task.Run(() => { AlgorithmTimespanMultiple(GetFibonacciArray, nameof(GetFibonacciArray)); });
Task.WaitAll(taskRecursion, taskFor, taskForNoTemp, taskArray);
Console.ReadLine();
}
/// <summary>
/// 算法用时:单次
/// </summary>
/// <param name="FibonacciMethod"></param>
/// <param name="methodName"></param>
static void AlgorithmTimespan(Func<int, long> FibonacciMethod, string methodName)
{
Stopwatch stopwatch = Stopwatch.StartNew();
int nItem = 40;
long number = FibonacciMethod(nItem);
Console.WriteLine($"【{methodName.PadRight(26)}】，第【{nItem + 1}】项=【{number}】,用时【{stopwatch.Elapsed.TotalMilliseconds}】ms");
}
/// <summary>
/// 计算多次使用斐波那契函数的时间
/// </summary>
/// <param name="FibonacciMethod"></param>
/// <param name="methodName"></param>
static void AlgorithmTimespanMultiple(Func<int, long> FibonacciMethod, string methodName)
{
Stopwatch stopwatch = Stopwatch.StartNew();
long number;
int nItem = GetIndexLargerMaxInt32(FibonacciMethod, out number);
Console.WriteLine($"【{methodName.PadRight(26)}】，第【{nItem + 1}】项=【{number}】超过Int32的最大值,用时【{stopwatch.Elapsed.TotalMilliseconds}】ms");
}
/// <summary>
/// 找出斐波那契数列的第几项超过Int32的最大值
/// </summary>
/// <param name="FibonacciMethod"></param>
/// <returns></returns>
static int GetIndexLargerMaxInt32(Func<int, long> FibonacciMethod, out long number)
{
int nItem = 0;
number = 0;
while (true)
{
number = FibonacciMethod(nItem);
if (number >= Int32.MaxValue)
{
break;
}
nItem++;
}
return nItem;
}
/// <summary>
/// 获取斐波那契数列的第N项，索引从0开始 使用递归
/// </summary>
/// <param name="nItem">索引：从0开始</param>
/// <returns></returns>
static long GetFibonacciRecursion(int nItem)
{
if (nItem <= 1)
{
return 1;
}
return GetFibonacciRecursion(nItem - 1) + GetFibonacciRecursion(nItem - 2);
}
/// <summary>
/// 获取斐波那契数列的第N项，索引从0开始 使用For循环
/// </summary>
/// <param name="nItem">索引：从0开始</param>
/// <returns></returns>
static long GetFibonacciFor(int nItem)
{
long first = 1;
long second = 1;
for (int i = 1; i < nItem; i++)
{
long temp = first;
first = first + second;
second = temp;
}
return first;
}
/// <summary>
/// 获取斐波那契数列的第N项，索引从0开始 使用For循环，不使用临时变量
/// </summary>
/// <param name="nItem"></param>
/// <returns></returns>
static long GetFibonacciForNoTemp(int nItem)
{
long first = 1;
long second = 1;
for (int i = 1; i < nItem; i++)
{
first = first + second;
second = first - second;
}
return first;
}
/// <summary>
/// 获取斐波那契数列的第N项，索引从0开始 使用数组仓库
/// </summary>
/// <param name="nItem">索引：从0开始</param>
/// <returns></returns>
static long GetFibonacciArray(int nItem)
{
long[] array = new long[nItem + 1];
for (int i = 0; i < array.Length; i++)
{
if (i <= 1)
{
array[i] = 1;
}
else
{
array[i] = array[i - 1] + array[i - 2];
}
}
return array[nItem];
}
}
}
运行效果如图：
我们发现：性能比较结果，依次为：
【for(无临时变量)】
【for(有临时变量)】
【数组仓库】
【递归】
这也是我们编程中经常提醒：尽量减少使用递归