末尾再起なフィボナッチ関数

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
  class Program
  {
    static int cnt;
    static void Main(string[] args)
    {
      foreach (var i in Enumerable.Range(0, 11))
      {
        cnt = 0;
        Console.WriteLine("Fib(" + i + ") : " + Fib(i) + ", 再帰呼び出し回数 : " + cnt);

        // == 実行結果 ==
        // Fib(0) : 0, 再帰呼び出し回数 : 0
        // Fib(1) : 1, 再帰呼び出し回数 : 0
        // Fib(2) : 1, 再帰呼び出し回数 : 1
        // Fib(3) : 2, 再帰呼び出し回数 : 2
        // Fib(4) : 3, 再帰呼び出し回数 : 3
        // Fib(5) : 5, 再帰呼び出し回数 : 4
        // Fib(6) : 8, 再帰呼び出し回数 : 5
        // Fib(7) : 13, 再帰呼び出し回数 : 6
        // Fib(8) : 21, 再帰呼び出し回数 : 7
        // Fib(9) : 34, 再帰呼び出し回数 : 8
        // Fib(10) : 55, 再帰呼び出し回数 : 9
      }
    }

    private static int Fib(int n)
    {
      return Fib(0, 1, n);
    }

    private static int Fib(int fib__, int fib_, int n)
    {
      cnt++;

      if (n == 0) return 0;
      if (n == 1) return 1;

      var fib = fib__ + fib_;

      if (n > 2)
      {
        return Fib(fib_, fib, n - 1);
      }
      else
      {
        return fib;
      }
    }
  }
}