Buy Me a Coffee

為了讓非資工的同仁理解何謂遞迴

為了讓非資工的同仁理解何謂遞迴，特地撰寫此範例程式練功用。是一個簡單又可以理解其他議題的好範例。

  • 使用三個變數的好處是，簡潔節省執行時間。
  • 使用遞迴部分，讓人理解遞迴在執行時會多出其他系統資源成本。
  • 順便知道，原來C# int 會出現溢位(overflow)。可以用來探討基本基料型態的數值範圍。
  • 微軟官方文件之整數數數值型別 (C# 參考)
// For 迴圈版本
static void Main(string[] args)
{
    int loopCnt = 100;
    ulong bef2 = 0; // 前二個數
    ulong bef1 = 1; // 前一個數
    ulong currentNumber = 0; // 目前的數
    
    //迴圈版本
    Console.WriteLine($"{bef2}");
    Console.WriteLine($"{bef1}");
    for (int i = 3; i <= loopCnt; i++)
    {
        currentNumber = bef2 + bef1; //算出目前的數
        bef2 = bef1; // 將前一個數移至前二個數
        bef1 = currentNumber; // 將目前的數移至前一個數
        Console.WriteLine($"{currentNumber}");
    }

    //遞迴版本呼叫
    for (int idx = 0 ; idx <= 100; idx++)
        Console.WriteLine($"{idx}-{Fibonacci(idx)}");

}

/// <summary>
/// 費式級數到 12200160415121876738 overflow，其它程式語言應該不會
/// </summary>
/// <param name="num"></param>
/// <returns></returns>
private static int Fibonacci(int num)
{
    if (num == 0)
        return 0;
    
    if (num <= 2)
        return 1;
    
    return Fib(num - 1) + Fib(num - 2);

}