Java | アルゴリズムと再帰関数 (recursive function)

前半：Javaで理解する「アルゴリズム」と「再帰関数」の基礎

Javaは静的型付けで、関数（メソッド）の動きが明確に見えるため、再帰の学習にとても向いている言語だ。
ここでは、プログラミング初心者でも「再帰の本質」をつかめるように、アルゴリズムの基礎から丁寧に解説していく。

アルゴリズムとは何か

アルゴリズムを日常の言葉に置き換える

アルゴリズムとは「問題を解くための手順書」のことだ。
たとえば「コーヒーを淹れるアルゴリズム」を書くなら、次のようになる。

豆を挽く
フィルターをセットする
お湯を注ぐ
抽出が終わるまで待つ

これをプログラムの世界に持ってきたものがアルゴリズムだ。
つまり、Javaでコードを書くというのは「コンピュータが実行できる形で手順書を書く」ことに他ならない。

なぜアルゴリズムが重要なのか

文法を覚えるだけでは「動くコード」は書けても、「速くて安全なコード」は書けない。
アルゴリズムを理解すると、次のような力が身につく。

処理を効率よくする
無駄な計算を減らす
入力が増えても落ちない安全なコードを書く

特にJavaは業務システムでよく使われるため、パフォーマンスと安全性は非常に重要だ。
アルゴリズムを学ぶことは、エンジニアとしての基礎体力をつけることに直結する。

再帰関数とは何か

一言でいうと「自分自身を呼び出すメソッド」

Javaでの再帰関数（recursive method）は、「メソッドの中で自分自身を呼び出すメソッド」のことだ。

void foo(int n) {
    foo(n - 1);  // 自分自身を呼んでいる
}

void foo(int n) {
    foo(n - 1);  // 自分自身を呼んでいる
}

このままだと無限に呼び続けてしまう。
だから再帰には必ず「終わりを決める条件」が必要になる。

再帰の2本柱：ベースケースと再帰ステップ

再帰関数は次の2つが揃って初めて成立する。

ベースケース（終わりの条件）
再帰ステップ（問題を小さくして自分を呼ぶ部分）

この2つが揃っていない再帰は、必ず暴走する。

Javaで学ぶ最もやさしい再帰：カウントダウン

カウントダウンを再帰で書く

まずは、Javaで「n から 1 までカウントダウンする」再帰関数を作ってみる。

public static void countdown(int n) {
    if (n <= 0) {                     // ① ベースケース
        System.out.println("終了");
        return;
    }

    System.out.println(n);            // ② 今の仕事
    countdown(n - 1);                 // ③ 再帰ステップ
}

public static void main(String[] args) {
    countdown(3);
}

public static void countdown(int n) {
    if (n <= 0) {                     // ① ベースケース
        System.out.println("終了");
        return;
    }

    System.out.println(n);            // ② 今の仕事
    countdown(n - 1);                 // ③ 再帰ステップ
}

public static void main(String[] args) {
    countdown(3);
}

実行結果はこうなる。

3
2
1
終了

ベースケースを深掘りする

if (n <= 0) return;
ここが再帰の命綱だ。

これがないと、countdown(n - 1) が永遠に呼ばれ続け、最終的に Java は次のエラーを出す。

java.lang.StackOverflowError

これは「コールスタックが限界を超えた」という意味だ。
セキュリティの観点でも、無限再帰はDoS（サービス妨害）につながる危険なパターンだ。

再帰ステップを深掘りする

countdown(n - 1)
ここで「問題を一段小さくして未来の自分に任せる」という動きをしている。

countdown(3) → countdown(2) → countdown(1) → countdown(0)

このように、再帰は「深く潜っていき、ベースケースで止まり、そこから戻る」という流れで動く。

Javaのコールスタックと再帰の関係

コールスタックとは何か

Javaはメソッドを呼ぶたびに「どこから呼ばれたか」「変数の値は何か」をスタックに積み上げる。
これを「コールスタック」と呼ぶ。

countdown(3) を呼ぶと、次のように積み上がる。

countdown(3)
countdown(2)
countdown(1)
countdown(0)

countdown(0) が return すると、一番上が消え、次に countdown(1) に戻る。
これが「呼び出し元に戻る」という動きの正体だ。

スタックオーバーフローと安全性

再帰が深くなりすぎると、Javaは StackOverflowError を投げる。
これは単なるエラーではなく、「入力次第で簡単に落ちる危険なコード」という意味でもある。

再帰を書くときは、次の2点を常に意識する必要がある。

必ず終わる
深くなりすぎない

この2つは、アルゴリズムとセキュリティの両面で重要だ。

アルゴリズムと再帰の関係

再帰は「アルゴリズムの表現方法」のひとつ

アルゴリズムは「問題を解く手順」。
その手順をコードにする方法として、

ループ（for, while）
再帰（recursive method）

の2つがある。

たとえば「1 から n までの合計を求める」アルゴリズムを考える。

ループで書く場合

public static int sumLoop(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

public static int sumLoop(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

再帰で書く場合

public static int sumRecursive(int n) {
    if (n == 0) {                 // ベースケース
        return 0;
    }
    return n + sumRecursive(n - 1);   // 再帰ステップ
}

public static int sumRecursive(int n) {
    if (n == 0) {                 // ベースケース
        return 0;
    }
    return n + sumRecursive(n - 1);   // 再帰ステップ
}

どちらも同じアルゴリズムを実現している。
ただ、表現方法が違うだけだ。

前半のまとめと後半への予告

前半では、次の基礎をしっかり固めた。

アルゴリズムは「問題を解く手順書」であり、文法とは別に鍛えるべき思考である
再帰関数は「自分自身を呼ぶメソッド」であり、ベースケースと再帰ステップが必須
Javaではコールスタックの仕組みで再帰が動き、深くなりすぎると StackOverflowError が起きる
カウントダウンや合計などの例で、再帰の流れと「問題を小さくして任せる」感覚をつかんだ

後半では、さらに実践的な内容に踏み込む。

階乗・フィボナッチなどの典型的な再帰アルゴリズム
配列・文字列・木構造を再帰で処理する方法
再帰とループの選び方（パフォーマンス・安全性の観点）
再帰を書くときの「思考の型」と落とし穴