C#で再帰を使ってフィボナッチ数列のn番目の値を取得する方法

C#では、再帰（リカーシブ）処理を利用することで、フィボナッチ数列のn番目の値を簡潔に求めることができます。まず、n番目の値を返すメソッドを作成しましょう。

public int displayFibonacci(int n)

このメソッドは次のように呼び出します。

displayFibonacci(val)

呼び出されると、displayFibonacci() メソッドが再帰的に実行され、n番目の値を計算します。

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

このメソッドのポイントは基本ケース（ベースケース）です。n == 0 のときは 0 を、n == 1 のときは 1 を返すことで再帰の終了条件を定めています。それ以外の場合は、直前の2つの項「displayFibonacci(n - 1)」と「displayFibonacci(n - 2)」を再帰的に呼び出して加算することで、フィボナッチ数列の性質（各項が直前の2項の和）を実現しています。

それでは、完全なコードを見てみましょう。

サンプルコード

using System;
public class Demo {
   public static void Main(string[] args) {
      Demo d = new Demo();
      int val = 7;
      int res = d.displayFibonacci(val);
      Console.WriteLine("{0}th number in fibonacci series = {1}", val, res);
   }
   public int displayFibonacci(int n) {
      if (n == 0) {
         return 0;
      }
      if (n == 1) {
         return 1;
      } else {
         return displayFibonacci(n - 1) + displayFibonacci(n - 2);
      }
   }
}

実行結果

7th number in fibonacci series = 13

この例では7番目の値を求めており、実行結果として 13 が出力されます。フィボナッチ数列は「0, 1, 1, 2, 3, 5, 8, 13 …」と続くため、インデックス7（0始まり）の値が13になるというわけです。

なお、単純な再帰実装は同じ値を何度も計算するため、nが大きくなると処理時間が急増します。実用的な場面では、計算結果をキャッシュするメモ化や、ループによる反復処理を組み合わせるとパフォーマンスを大幅に改善できます。