Rekursion in Java

1. Einleitung

In diesem Artikel konzentrieren wir uns auf ein Kernkonzept in jeder Programmiersprache - die Rekursion.

Wir erklären die Eigenschaften einer rekursiven Funktion und zeigen, wie die Rekursion zur Lösung verschiedener Probleme in Java verwendet wird.

2. Rekursion verstehen

2.1. Die Definition

In Java unterstützt der Funktionsaufrufmechanismus die Möglichkeit, einen Methodenaufruf selbst durchzuführen . Diese Funktionalität wird als Rekursion bezeichnet .

Angenommen, wir möchten die ganzen Zahlen von 0 bis zu einem Wert n summieren :

public int sum(int n) { if (n >= 1) { return sum(n - 1) + n; } return n; }

Es gibt zwei Hauptanforderungen an eine rekursive Funktion:

  • Eine Stoppbedingung - Die Funktion gibt einen Wert zurück, wenn eine bestimmte Bedingung erfüllt ist, ohne einen weiteren rekursiven Aufruf
  • Der rekursive Aufruf - Die Funktion ruft sich mit einer Eingabe auf, die der Stoppbedingung einen Schritt näher kommt

Jeder rekursive Aufruf fügt dem Stapelspeicher der JVM einen neuen Frame hinzu. Also, wenn wir nicht zahlen Sie darauf, wie tief unser rekursiven Aufruf tauchen kann, kann ein aus der Erinnerung Ausnahme auftreten.

Dieses potenzielle Problem kann durch die Nutzung der Optimierung der Schwanzrekursion vermieden werden.

2.2. Schwanzrekursion versus Kopfrekursion

Wir bezeichnen eine rekursive Funktion als Schwanzrekursion, wenn der rekursive Aufruf das letzte ist, was die Funktion ausführt. Andernfalls wird es als Kopfrekursion bezeichnet .

Unsere obige Implementierung der Funktion sum () ist ein Beispiel für eine Kopfrekursion und kann in eine Schwanzrekursion geändert werden:

public int tailSum(int currentSum, int n) { if (n <= 1) { return currentSum + n; } return tailSum(currentSum + n, n - 1); }

Bei der Schwanzrekursion ist der rekursive Aufruf das Letzte, was die Methode tut, sodass innerhalb der aktuellen Funktion nichts mehr ausgeführt werden muss.

Logischerweise besteht keine Notwendigkeit, den Stapelrahmen der aktuellen Funktion zu speichern.

Obwohl der Compiler diesen Punkt nutzen kann , um den Speicher zu optimieren, sollte beachtet werden, dass der Java-Compiler derzeit nicht für die Schwanzrekursion optimiert .

2.3. Rekursion versus Iteration

Rekursion kann dazu beitragen, die Implementierung einiger komplizierter Probleme zu vereinfachen, indem der Code klarer und lesbarer gemacht wird.

Wie wir bereits gesehen haben, erfordert der rekursive Ansatz häufig mehr Speicher, da der erforderliche Stapelspeicher mit jedem rekursiven Aufruf zunimmt.

Wenn wir ein Problem mit Rekursion lösen können, können wir es alternativ auch durch Iteration lösen.

Zum Beispiel könnte unsere Summenmethode mithilfe der Iteration implementiert werden:

public int iterativeSum(int n) { int sum = 0; if(n < 0) { return -1; } for(int i=0; i<=n; i++) { sum += i; } return sum; }

Im Vergleich zur Rekursion könnte der iterative Ansatz möglicherweise zu einer besseren Leistung führen. Abgesehen davon ist die Iteration komplizierter und schwieriger zu verstehen als die Rekursion, zum Beispiel: Durchlaufen eines Binärbaums.

Die richtige Wahl zwischen Kopfrekursion, Schwanzrekursion und einem iterativen Ansatz hängt vom jeweiligen Problem und der jeweiligen Situation ab.

3. Beispiele

Versuchen wir nun, einige Probleme rekursiv zu lösen.

3.1. N-te Zehnerpotenz finden

Angenommen, wir müssen die n- te Potenz von 10 berechnen . Hier ist unsere Eingabe n. Wenn wir rekursiv denken, können wir zuerst die (n-1) -te Potenz von 10 berechnen und das Ergebnis mit 10 multiplizieren.

Um dann die (n-1) -te Potenz von 10 zu berechnen, wird die (n-2) -te Potenz von 10 sein und das Ergebnis mit 10 multiplizieren und so weiter. Wir werden so weitermachen, bis wir zu einem Punkt kommen, an dem wir die (nn) -te Potenz von 10 berechnen müssen, die 1 ist.

Wenn wir dies in Java implementieren wollten, würden wir schreiben:

public int powerOf10(int n) { if (n == 0) { return 1; } return powerOf10(n-1) * 10; }

3.2. Finden des N-ten Elements der Fibonacci-Sequenz

Beginnend mit 0 und 1 ist die Fibonacci-Sequenz eine Folge von Zahlen, wobei jede Zahl als die Summe der beiden Zahlen definiert wird, die darauf folgen : 0 1 1 2 3 5 8 13 21 34 55

Bei einer Zahl n besteht unser Problem darin, das n- te Element der Fibonacci-Sequenz zu finden . Um eine rekursive Lösung zu implementieren, müssen wir die Stoppbedingung und den rekursiven Aufruf herausfinden .

Zum Glück ist es wirklich einfach.

Nennen wir f (n) den n- ten Wert der Sequenz. Dann haben wir f (n) = f (n-1) + f (n-2) (der rekursive Aufruf ) .

In der Zwischenzeit ist f (0) = 0 und f (1) = 1 ( Stoppbedingung) .

Dann ist es für uns wirklich offensichtlich, eine rekursive Methode zur Lösung des Problems zu definieren:

public int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); }

3.3. Konvertieren von Dezimal in Binär

Betrachten wir nun das Problem der Konvertierung einer Dezimalzahl in eine Binärzahl. Die Anforderung besteht darin, eine Methode zu implementieren, die einen positiven ganzzahligen Wert n empfängt und eine binäre String- Darstellung zurückgibt .

Ein Ansatz zum Konvertieren einer Dezimalzahl in eine Binärzahl besteht darin, den Wert durch 2 zu teilen, den Rest aufzuzeichnen und den Quotienten weiterhin durch 2 zu teilen.

Wir teilen so weiter, bis wir einen Quotienten von 0 erhalten . Wenn wir dann alle Reste in der Reihenfolge der Reserve ausschreiben, erhalten wir die binäre Zeichenfolge.

Daher besteht unser Problem darin, eine Methode zu schreiben, die diese Reste in Reservereihenfolge zurückgibt:

public String toBinary(int n) { if (n <= 1 ) { return String.valueOf(n); } return toBinary(n / 2) + String.valueOf(n % 2); }

3.4. Höhe eines Binärbaums

Die Höhe eines Binärbaums ist definiert als die Anzahl der Kanten von der Wurzel bis zum tiefsten Blatt. Unser Problem besteht nun darin, diesen Wert für einen bestimmten Binärbaum zu berechnen.

Ein einfacher Ansatz wäre, das tiefste Blatt zu finden und dann die Kanten zwischen der Wurzel und diesem Blatt zu zählen.

Wenn wir jedoch versuchen, eine rekursive Lösung zu finden, können wir die Definition für die Höhe eines Binärbaums als maximale Höhe des linken Zweigs der Wurzel und des rechten Zweigs der Wurzel plus 1 wiederholen .

Wenn die Wurzel keinen linken und rechten Zweig hat, ist ihre Höhe Null .

Hier ist unsere Implementierung:

public int calculateTreeHeight(BinaryNode root){ if (root!= null) { if (root.getLeft() != null || root.getRight() != null) { return 1 + max(calculateTreeHeight(root.left), calculateTreeHeight(root.right)); } } return 0; }

Daher sehen wir, dass einige Probleme mit Rekursion auf wirklich einfache Weise gelöst werden können.

4. Fazit

In diesem Tutorial haben wir das Konzept der Rekursion in Java vorgestellt und anhand einiger einfacher Beispiele demonstriert.

Die Implementierung dieses Artikels finden Sie auf Github.