【Java】再帰処理を使って文章を反転させるプログラムの作成方法

はじめに

この記事では、再帰(recursion) を使用して文章(文字列)を反転させるJavaプログラムの作成方法について解説します。

再帰関数とは、特定の条件が満たされるまで、自分自身を繰り返し呼び出す関数のことです。一見複雑そうに思えますが、考え方さえ理解すれば非常にシンプルで強力なテクニックです。

再帰とは何か

再帰とは、同じ構造を自己相似的に繰り返していく処理のことです。プログラミング言語において、ある関数の内部からその同じ関数を呼び出せる仕組みを「再帰呼び出し」と呼びます。

多くのプログラミング言語では、再帰はスタック(stack)によって実現されています。一般的に、ある関数(呼び出し元)が別の関数や自分自身(呼び出し先)を呼び出すと、実行制御は呼び出し元から呼び出し先へと移ります。この際、引数などのデータも呼び出し元から呼び出し先へ引き渡されます。

入出力イメージ

入力:

Enter the sentence : Have a nice evening

出力:

The reversed input is: gnineve ecin a evaH

入力した文章が、1文字ずつ末尾から並べ替えられて出力されているのがわかります。

アルゴリズム

処理の流れは以下の通りです。

Step 1 - 開始
Step 2 - 文字列型変数 my_input(入力用)と my_result(結果格納用)を宣言する
Step 3 - ユーザーから値を読み込む、または値を定義する
Step 4 - 文字列を受け取り、末尾の文字から返す再帰関数 reverseString を定義する
Step 5 - my_input が空文字列になるまで、関数を再帰的に呼び出し続ける
Step 6 - 再帰関数を呼び出し、my_input を渡して戻り値を保存する
Step 7 - 結果を表示する
Step 8 - 終了

例1:ユーザーからの入力を使用する場合

ここでは、Scannerクラスを使ってユーザーに入力を促し、その値を反転させて表示します。

import java.util.Scanner;
public class Reverse {
   public static void main(String[] args) {
      String my_input, my_result;
      System.out.println("Required packages have been imported");
      Scanner my_scanner = new Scanner(System.in);
      System.out.println("A reader object has been defined ");
      System.out.print("Enter the sentence : ");
      my_input = my_scanner.nextLine();
      my_result = reverseString(my_input);
      System.out.println("The reversed input is: " + my_result);
   }
   public static String reverseString(String my_input) {
      if (my_input.isEmpty())
        return my_input;
      return reverseString(my_input.substring(1)) + my_input.charAt(0);
   }
}

実行結果

Required packages have been imported
A reader object has been defined
Enter the sentence : Have a nice evening
The reversed input is: gnineve ecin a evaH

例2:文字列を事前に定義しておく場合

こちらの例では、反転したい文字列をあらかじめコード内で定義し、その結果をコンソールに表示します。

public class Reverse {
   public static void main(String[] args) {
      String my_input, my_result;
      my_input = "Have a nice evening";
      System.out.println("The string is defined as :" +my_input);
      my_result = reverseString(my_input);
      System.out.println("The reversed input is: " + my_result);
   }
   public static String reverseString(String my_input) {
      if (my_input.isEmpty())
         return my_input;
      return reverseString(my_input.substring(1)) + my_input.charAt(0);
   }
}

実行結果

The string is defined as :Have a nice evening
The reversed input is: gnineve ecin a evaH

再帰の仕組みのポイント

このプログラムの核心は、次の1行です。

return reverseString(my_input.substring(1)) + my_input.charAt(0);

• substring(1):先頭の1文字を除いた残りの文字列を取り出し、それを引数として自分自身を再度呼び出します。
• charAt(0):取り除いた先頭の1文字を、再帰の戻り値の後ろに連結します。
• isEmpty() が true になった時点(ベースケース)で再帰が終了し、呼び出しが遡りながら文字列が組み上がっていきます。

注意点:パフォーマンスについて

上記のコードは理解しやすい反面、substring() や文字列連結のたびに新しいStringオブジェクトが生成されるため、計算量は O(n²)、長い文字列ではメモリ効率が悪化します。実務で大きなデータを扱う場合は、StringBuilder の reverse() メソッドや、ループによる後ろからの走査など、より効率的な手法を検討するとよいでしょう。

まとめ

今回は、Javaにおける再帰呼び出しの基本を踏まえ、文章を反転させるプログラムを2つのパターン(ユーザー入力版・定義済み文字列版)で紹介しました。「空になったら終了、それ以外は先頭を外して自分を呼ぶ」というシンプルな発想が、エレガントな再帰処理につながります。ぜひ実際にコードを動かして、再帰の挙動を体感してみてください。