再帰

「こんにちは、アミーゴ。今日はビラーボが再帰についてお話します。」

ご存知のとおり、Java では一部のメソッドが他のメソッドを呼び出します。さらに、メソッドが呼び出されるとき、特定の引数がメソッドに渡されますが、メソッドのローカル変数は実行中に特定の値を取ります。

"うん。"

「そしてご存知のとおり、さまざまなメソッドの内部変数は互いに独立しています。」

"うん。"

「それでは、メソッドがそれ自体を呼び出す状況を想像してください。これは再帰と呼ばれます。たとえば、次のようになります。」

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

public static void countDown(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown(x - 1);
 }
}

10
9
8
7
6
5
4
3
2
1
Boom!

「コード内でメソッドが自分自身を呼び出しているのはわかりますが、何が起こっているのか正直わかりません。」

「そうですね、別のメソッドが呼び出されたときにもほぼ同じことが起こります。」

「いいえ、変数はどうなるのですか? その値はどうなるのでしょうか? そしてメソッドをどのように終了するのですか? それともすべてを一度に終了するのですか?」

「親切ですね。すべてははるかに単純です。自分自身を呼び出すメソッドが何度も乗算されていると想像してください。そうすると、同様の状況が得られます。」

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

public static void countDown(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown(x - 1);
 }
}

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

public static void countDown1(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown2(x - 1);
 }
}
public static void countDown2(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown3(x - 1);
 }
}
public static void countDown3(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown4(x - 1);
 }
}

public static void countDown4(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown5(x - 1);
 }
}

3
2
1
Boom!

3
2
1
Boom!

「言い換えれば、メソッドが呼び出されるたびに（単独でも）、このメソッドのデータを保存する新しい変数が作成されます。共有変数はありません。」

「呼び出しごとに、新しい値を持つメソッド引数の別のコピーがメモリ内に作成されます。古いメソッドに戻ると、その変数がそこで使用されます。つまり、再帰中に実際に別のメソッドを呼び出しますが、私たちと同じコードです！」

「なるほど。では、そのようなメソッドを終了するのはどのように機能するのでしょうか? 例を挙げるとよいでしょうか?」

「わかりました。例は百聞は一見に如かずです。「これが例です。」

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

public static void print(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  print(x - 1);
  System.out.println(x);
 }
}

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

public static void print1(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  print2(x - 1);
  System.out.println(x);
 }
}

public static void print2(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  print3(x - 1);
  System.out.println(x);
 }
}

…

3
2
1
Boom!
1
2
3

3
2
1
Boom!
1
2
3

「わかりました。理解できたと思います。なぜ再帰が必要なのでしょうか?」

「元のタスクと同一の別個のサブタスクに分割できるタスクが非常にたくさんあります。たとえば、XML ツリーのすべての要素をたどる必要があります。各要素には複数の子要素を持つことができ、それぞれに子要素があります。独自の子要素。」

"または、ディレクトリとそのすべてのサブディレクトリにあるファイルのリストを表示する必要があります。そのため、現在のディレクトリのファイルを表示するメソッドを作成します。次に、すべてのサブディレクトリのファイルを取得するには、別の引数: サブディレクトリです。」

"例えば："

public static void main(String[] args)
{
 printAllFiles(new File("c:/windows/"));
}

public static void printAllFiles(File dir)
{
 for (File file : dir.listFiles())
 {
  if (file.isDirectory())
   printAllFiles(file);
  else
   System.out.println(file.getAbsolutePath());
 }
}

「8 行目 – dir ディレクトリ内のすべてのファイル (およびディレクトリ) のリストを取得します。」

「行 10 ～ 11 – ファイルが実際にディレクトリである場合は、 printAllFiles を再度呼び出しますが、今回は別の引数であるサブディレクトリを使用します。」

「行 13 – 現在のファイルの名前を表示します。」

「わかりました。理解できたと思います。ありがとう、ビラーボ。」