Javaでの再帰を使用したフィボナッチ数列の実装方法

1. 単純な再帰関数の実装: 以下は、単純な再帰関数を使用してフィボナッチ数列を計算する例です。

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
    public static void main(String[] args) {
        int n = 10;
        System.out.println("フィボナッチ数列の最初の " + n + " 項:");
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }
}

このコードでは、fibonacci 関数が再帰的に呼び出され、n番目のフィボナッチ数を計算します。最初の "n" 項を表示するために main 関数が使用されています。

2. メモ化再帰を使用した効率的な実装: 上記の単純な再帰関数は重複した計算を行うため、大きな数値の場合には効率が悪くなります。メモ化再帰を使用すると、計算済みの値を記憶して再利用することができます。

import java.util.HashMap;
import java.util.Map;
public class Fibonacci {
    private static Map<Integer, Integer> memo = new HashMap<>();
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }
    public static void main(String[] args) {
        int n = 10;
        System.out.println("フィボナッチ数列の最初の " + n + " 項:");
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }
}

このコードでは、memo という名前の HashMap を使用して計算済みの値を記録します。再帰呼び出しの前にメモをチェックし、計算済みの値があれば再利用します。

これらの例では、Javaで再帰を使用してフィボナッチ数列を計算する方法を示しました。単純な再帰関数とメモ化再帰の2つのアプローチがあります。メモ化再帰を使用すると、計算の効率を向上させることができます。