Rekursion

„Hallo Amigo. Heute wird Bilaabo dir etwas über Rekursion erzählen.“

Wie Sie wissen, rufen in Java einige Methoden andere Methoden auf. Darüber hinaus werden beim Aufruf einer Methode bestimmte Argumente an diese übergeben, die lokalen Variablen der Methode nehmen jedoch während der Ausführung bestimmte Werte an.

„Uh-huh.“

„Und wie Sie wissen, sind die internen Variablen verschiedener Methoden unabhängig voneinander.“

„Uh-huh.“

„Stellen Sie sich also die Situation vor, in der sich eine Methode selbst aufruft. Dies nennt man Rekursion. Zum Beispiel:“

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!

„Ich kann sehen, dass sich die Methode im Code selbst aufruft, aber ich verstehe ehrlich gesagt nicht, was passiert.“

„Nun, ungefähr das Gleiche passiert, wenn eine andere Methode aufgerufen wird.“

„Nein, ich frage, was mit den Variablen passiert? Mit ihren Werten? Und wie beenden wir die Methode? Oder beenden wir alles auf einmal?“

„Meine Güte. Es ist alles viel einfacher. Stellen Sie sich vor, die Methode, die sich selbst aufruft, wurde um ein Vielfaches vervielfacht. Dann hätten wir die analoge Situation:“

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!

„Mit anderen Worten, jedes Mal, wenn eine Methode aufgerufen wird (auch wenn sie selbst aufgerufen wird), werden neue Variablen erstellt, die die Daten für diese Methode speichern. Es gibt keine gemeinsam genutzten Variablen.“

„Bei jedem Aufruf wird eine weitere Kopie der Methodenargumente mit neuen Werten im Speicher erstellt. Wenn wir zur alten Methode zurückkehren, werden deren Variablen dort verwendet. Mit anderen Worten: Bei der Rekursion rufen wir tatsächlich eine andere Methode auf, aber mit der Gleicher Code wie unserer! “

„Ich verstehe. Und wie funktioniert das Verlassen solcher Methoden? Vielleicht ein Beispiel?“

„OK. Ein Beispiel sagt mehr als tausend Worte. „Hier ist Ihr Beispiel:“

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

„OK. Ich glaube, ich verstehe. Warum brauchen wir eine Rekursion?“

„Es gibt viele, viele Aufgaben, die in separate Unteraufgaben unterteilt werden können, die mit der ursprünglichen Aufgabe identisch sind. Beispielsweise müssen Sie alle Elemente eines XML-Baums durchgehen. Jedes Element kann mehrere untergeordnete Elemente haben, und diese haben ihre eigenen.“ eigene untergeordnete Elemente.

„Oder Sie müssen die Liste der Dateien anzeigen, die sich in einem Verzeichnis und allen seinen Unterverzeichnissen befinden. Sie schreiben also eine Methode, die die Dateien des aktuellen Verzeichnisses anzeigt. Um dann die Dateien aller Unterverzeichnisse abzurufen, rufen Sie Ihre Methode mit a auf anderes Argument: ein Unterverzeichnis.

"Zum Beispiel:"

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());
 }
}

„Zeile 8 – Wir erhalten die Liste aller Dateien (und Verzeichnisse) im Dir-Verzeichnis.“

„Zeilen 10-11 – Wenn die Datei tatsächlich ein Verzeichnis ist, dann rufen wir printAllFiles erneut auf, dieses Mal jedoch mit einem anderen Argument: dem Unterverzeichnis.“

„Zeile 13 – Wir zeigen den Namen der aktuellen Datei an.“

„OK. Ich glaube, ich verstehe. Danke, Bilaabo.“