Javaで再帰（リカージョン）を使う方法｜基礎から実例まで徹底解説

プログラミングにおける「再帰（recursion）」とは、関数が自分自身を直接または間接的に呼び出す処理のことです。再帰は、コンピュータサイエンスにおけるさまざまな問題の解決に活用されています。

Javaプログラミング言語は、自分自身を呼び出す「再帰メソッド」の作成をサポートしています。

このチュートリアルでは、具体例を交えながら、再帰がどのように動作するのか、そしてJavaで再帰関数を作成する方法について詳しく解説します。この記事を読み終える頃には、Javaで再帰メソッドを自信を持って書けるようになっているでしょう。

Javaのメソッドとは

メソッド（関数とも呼ばれます）とは、特定のタスクを実行するコードのブロックです。たとえば、配列内の値の合計を計算したり、配列の内容をコンソールに出力したりするためにメソッドを使用できます。

Javaにおけるメソッドの基本構文は以下の通りです：

modifier static returnType methodName(Parameters) {
	// メソッド本体
}

たとえば、「It's Wednesday! We're half-way through the week!（水曜日です！1週間の折り返し地点です！）」という文をコンソールに出力するメソッドを作成したいとしましょう。次のようなコードで実現できます：

class Main {
public static void printItsWednesday() {
	System.out.println("It's Wednesday! We're half-way through the week!");
}

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

printItsWednesday() を呼び出すと、以下が出力されます：

It's Wednesday! We're half-way through the week!

Javaのメソッドについてさらに詳しく学びたい方は、Javaメソッドの完全ガイドもあわせてご覧ください。

上記の例では、mainプログラムの中で printItsWednesday() メソッドを呼び出しています。しかし、もしメソッド自身の内部でそのメソッドを呼び出したら、それは「再帰メソッド」となります。

Javaにおける再帰

再帰メソッドとは、最初にmainメソッド内で呼び出され、その後メソッド自身の内部でも呼び出されるメソッドのことです。再帰メソッドの構文は以下の通りです：

static void executeMethod() {
	// ここにコードを書く
	executeMethod(); // これが再帰呼び出し
	// ここにコードを書く
}

public static void main(String[] args) {
	executeMethod(); // これは通常のメソッド呼び出し
}

プログラムを実行すると、mainプログラム内で executeMethod() メソッドが呼び出されます。これにより executeMethod() 内のコードが実行されますが、その中には executeMethod() の呼び出し自体も含まれています。つまり、プログラムはループ状態に入るのです。

プログラムは、処理を停止させる条件が満たされるまで executeMethod() を実行し続けます。再帰を止める条件が指定されていない場合、プログラムは永遠に実行され続けます。これを「無限再帰（infinite recursion）」と呼びます。

なぜ再帰を使うべきなのでしょうか？第一に、特定のケースでは再帰によってプログラムの時間計算量を削減できます。第二に、再帰を活用することで、一部のアルゴリズムをより読みやすく、保守しやすい形で実装できます。

再帰を使ってよく書かれるプログラムの例をいくつか挙げます：

• フィボナッチ数列の計算
• 文字列の反転
• 数値の階乗の計算
• 二分木の高さの計算

ただし、再帰は標準的なメソッドでタスクを実行するよりも遅くなる場合がある点に注意が必要です。これは、再帰メソッドが実行されるたびに、変数用の新しい格納領域が作成されるためです。

Java再帰の実例

それでは、Javaで再帰がどのように機能するのかを理解するために、2つの具体的な例を見ていきましょう。

再帰を使った文字列の反転

ある中学校の教師のために、生徒の年間の成績が記録された文字列を反転させるプログラムを作るとしましょう。この文字列は、生徒が最初に取得した成績で始まり、最新の成績で終わっています。私たちは、生徒の最も新しい成績が文字列の先頭に来るように、文字列を反転させたいと考えています。

文字列を反転させるには、次のコードを使用できます：

public class ReverseGrades {
	public static String reverse(String grades) {
		if (grades.isEmpty())
			return grades;
		return reverse(grades.substring(1)) + grades.charAt(0);
	}

	public static void main(String[] args) {
		String grades = "CBCBAABACAABA";
		String reverse_grades = reverse(grades);

		System.out.println("This student's grades for the year are: " + reverse_grades);
	}
}

このコードの出力結果は以下の通りです：

This student's grades for the year are: ABAACABAABCBC

ご覧のとおり、プログラムによって文字列の内容が正しく反転されました。このプログラムでは、reverse() という再帰関数を作成しています。

reverse() 関数が実行されると、まず成績の文字列が空かどうかをチェックします。空であれば、成績の文字列をそのままmainプログラムに返します。これにより、関数末尾の reverse() 呼び出しが実行される機会がなくなり、再帰が停止します。

成績の文字列が空でない場合は、プログラムが再度 reverse() メソッドを実行し、その結果を文の最初の文字と連結します。この例では charAt() メソッドを使って文の最初の文字を取得し、reverse() メソッドの戻り値の左側に追加しています。

文字列が反転された後、「This student's grades for the year are:」というメッセージと、反転された生徒の成績文字列がプログラムに返されます。

再帰を使った階乗の計算

再帰が役立つもう一つの代表的な例が、数値の階乗の計算です。

数学において、階乗とは、ある数値以下のすべての正の整数を掛け合わせた積のことです。たとえば、5の階乗は 5×4×3×2×1 となり、その結果は120です。階乗の計算は同じ演算を繰り返し行うため、再帰が問題解決に役立つ身近な好例と言えます。

次のJavaプログラムでは、7の階乗を計算できます：

class Main {
	static int calculateFactorial(int number) {
		if (number != 0)
			return number * calculateFactorial(number-1);
		else
			return 1;
	}
	
	public static void main(String[] args) {
		int num = 7;
		int answer = calculateFactorial(num);
		System.out.println("The factorial of 7 is: " + answer);
	}
}

このコードの出力結果は以下の通りです：

The factorial of 7 is: 5040

この例では、numberパラメータに格納された数値に、次の calculateFactorial() メソッドの結果を掛け合わせる calculateFactorial() メソッドを作成しています。この処理は、numberパラメータが0になるまで繰り返し実行されます。

numberパラメータが0になると、コード内のif文が1を返し、calculateFactorial() メソッドの結果がmainプログラムへと戻されていきます。

つまり、calculateFactorial() メソッドは 7×6×5×4×3×2×1 を計算し、その答えをmainプログラムに返します。答えが計算されると、「The factorial of 7 is:」というメッセージと、プログラムが算出した答えがコンソールに出力されます。

まとめ

再帰とは、メソッドが自分自身を呼び出すことを表すプログラミングの概念です。再帰メソッドは、同じタスクを何度も繰り返し実行し、前回の処理結果を現在の処理で利用する必要がある場合に特に便利です。

このチュートリアルでは、Javaにおける再帰の基礎と再帰メソッドの作成方法を解説しました。さらに、文字列の反転と階乗の計算という2つの実例を通じて、実際の再帰の動作も確認しました。

これであなたも、プロフェッショナルのようにJavaで再帰メソッドを活用する準備が整いました！