【Java】フィボナッチ数列を考える①

FizzBuzz問題と並んでプログラミング初心者向けにフィボナッチ数列というものがあります。実は自分で書いたことがなかったので今回はJavaで書いてみたいと思います。

配列で実装

フィボナッチ数列は1番目の値と2番目の値を足すと3番目の値になります。言い方を変えるとひとつ前とふたつ前の値を足した数が次の数ということです。

ということで言葉通りに実装したいと思います。方針としては可変の配列を作り、値を求めるためにひとつ前とふたつ前の値を取り出して足していきます。1番目の値は0、2番目の値は1として以下のように実装しました。

public class App {
    public static void main(String[] args) throws Exception {

        ArrayList<Integer> fib = new ArrayList<Integer>();

        for (int index = 0; index < 10; index++) {

            if (index == 0) {
                fib.add(0);
                System.out.println(0);
                continue;
            }

            if (index == 1) {
                fib.add(1);
                System.out.println(1);
                continue;
            }

            int currentNumber = fib.get(index - 1) + fib.get(index - 2);

            fib.add(currentNumber);
            
            System.out.println(currentNumber);
        }
    }
}

実行結果

int currentNumber = fib.get(index - 1) + fib.get(index - 2);

ここの部分がひとつ前とふたつ前の数字を足して現在値を求めているところになります。

数列の意味をそのままソースに落としているのでよく読めばわかりやすいですが、どうも助長なような…もう少し良い書き方があるような気がもします。

フィボナッチ数列といえば再帰処理

フィボナッチ数列と言えば再帰処理です。再帰処理とは関数内で自分自身を呼び出すことを言います。

色々なサイトで詳しく書かれているのでここでは説明を省きますが、

Fn = (Fn-1) + (Fn-2)の式で再帰的にフィボナッチ数を求めることができます。

この式を使うと以下のように書けます。

public class App {
    public static void main(String[] args) throws Exception {

        for (int n = 0; n < 10; n++) {

            System.out.println(fibonacci(n));
        }
    }

    private static int fibonacci(int n) {

        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

実行結果