Java -Rekursion

Java-Rekursion

Rekursion ist die Technik, einen Funktionsaufruf selbst durchzuführen. Diese Technik bietet eine Möglichkeit, komplizierte Probleme in einfache Probleme zu zerlegen, die leichter zu lösen sind.

Rekursion kann etwas schwierig zu verstehen sein. Der beste Weg, um herauszufinden, wie es funktioniert, ist, damit zu experimentieren.

Rekursionsbeispiel

Das Addieren von zwei Zahlen ist einfach, aber das Addieren einer Reihe von Zahlen ist komplizierter. Im folgenden Beispiel wird Rekursion verwendet, um eine Reihe von Zahlen zu addieren, indem sie in die einfache Aufgabe zerlegt wird, zwei Zahlen zu addieren:

public class Main {
  public static void main(String[] args) {
    int result = sum(10);
    System.out.println(result);
  }
  public static int sum(int k) {
    if (k > 0) {
      return k + sum(k - 1);
    } else {
      return 0;
    }
  }
}

Beispiel erklärt

Wenn die sum()Funktion aufgerufen wird, fügt sie Parameter kzur Summe aller Zahlen hinzu, die kleiner als sind, kund gibt das Ergebnis zurück. Wenn k 0 wird, gibt die Funktion einfach 0 zurück. Bei der Ausführung folgt das Programm diesen Schritten:

Da sich die Funktion nicht selbst aufruft, wenn k0 ist, stoppt das Programm dort und gibt das Ergebnis zurück.

Haltezustand

So wie Schleifen auf das Problem der Endlosschleife stoßen können, können rekursive Funktionen auf das Problem der Endlosrekursion stoßen. Unendliche Rekursion ist, wenn die Funktion nie aufhört, sich selbst aufzurufen. Jede rekursive Funktion sollte eine Haltebedingung haben, d. h. die Bedingung, bei der die Funktion aufhört, sich selbst aufzurufen. Im vorherigen Beispiel ist die Haltebedingung, wenn der Parameter k0 wird.

Es ist hilfreich, sich verschiedene Beispiele anzusehen, um das Konzept besser zu verstehen. In diesem Beispiel fügt die Funktion einen Zahlenbereich zwischen einem Anfang und einem Ende hinzu. Die Haltebedingung für diese rekursive Funktion ist, wenn end nicht größer als start ist :

public class Main {
  public static void main(String[] args) {
    int result = sum(5, 10);
    System.out.println(result);
  }
  public static int sum(int start, int end) {
    if (end > start) {
      return end + sum(start, end - 1);
    } else {
      return end;
    }
  }
}