Rekursion in Java

Um zu verstehen, was Rekursion ist, müssen Sie verstehen, was Rekursion ist. Tatsächlich ist es nicht schwer, solche Funktionen zu verstehen; Sie müssen sie nur einmal gut verstehen. Und üben Sie, wenn es ums Programmieren geht. Rekursion in Java - 1

Rekursion kommt nicht nur in der Programmierung vor, sondern auch im wirklichen Leben. Nehmen Sie einen Spiegel in die Hand und stellen Sie sich vor einen anderen Spiegel. Die Reflexion der Reflexion wird in der Reflexion widergespiegelt und so weiter. Sie werden eine unendliche Anzahl von Reflexionen sehen, die in die Unendlichkeit gehen. Mehr zur „echten“ Rekursion finden Sie im Artikel „ Dedicated to Groundhog Day... “ Kehren wir von der realen Welt in den Alltag eines Programmierers zurück. Einfache Definition: Rekursive Funktionen in Java sind Funktionen, die sich selbst aufrufen. Lassen Sie mich Ihnen ein sehr einfaches und sehr schädliches Beispiel geben:

public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}

Warum ist es schädlich? Ich empfehle Ihnen, es selbst zu überprüfen! Wenn Sie sich für dieses Abenteuer entscheiden (und das werden Sie höchstwahrscheinlich tun, Sie Programmierer!), schreiben Sie in die Kommentare, welchen Fehler die JVM auslösen wird =) Dieses Beispiel und viele andere zeigen, dass die Verwendung der Rekursion in Java sorgfältig angegangen werden muss . Sie müssen verstehen, wo, wann und warum ein solcher Ansatz zur Lösung eines Problems gerechtfertigt ist, und sicherstellen, dass Ihre Funktion die Ausführung des Programms nicht zum „Murmeltiertag“ macht. Es gibt zwei weitere wichtige Definitionen zum Verständnis der Rekursion:

Rekursionsbasis – die Bedingung zum Verlassen des Blocks rekursiver Aufrufe – die grundlegende Lösung des Problems unter Bedingungen, unter denen kein Bedarf besteht, eine Rekursion aufzurufen.
Der Rekursionsschritt besteht darin, dass sich eine Funktion beim Ändern von Parametern selbst aufruft.

Ein klassisches Beispiel für die Verwendung einer rekursiven Funktion ist die Berechnung der Fakultät einer Zahl. Falls Sie es vergessen haben, möchte ich Sie daran erinnern: Die Fakultät einer positiven ganzen Zahl N(bezeichnet als N!) ist das Produkt von Zahlen aus 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. Übrigens ist die Fakultät von Null per Definition gleich 1. Die Fakultät kann also für jede positive ganze Zahl und Null gefunden werden (in der Sprache der Mathematik - für die Menge der nichtnegativen ganzen Zahlen oder für die Menge der natürlichen Zahlen und null). Ich denke, Sie verstehen, dass Sie Fakultäten mithilfe von Schleifen programmieren können. Tatsächlich gibt es hier eine nicht rekursive Methode zur Lösung dieses Problems:

private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Fügen wir eine Prüfung hinzu, ob die Zahl positiv und eine Ganzzahl ist, sowie eine separate Prüfung auf Null.

private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Jetzt gebe ich den Methodencode zur rekursiven Lösung dieses Problems an:

private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}

Schauen wir uns die Ausgabeergebnisse für die Aufrufe an:

System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));

Wir erhalten die erwarteten Werte:

Fügen wir eine schöne Ausgabe hinzu und berechnen die Fakultät für eine größere Zahl:

private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");

Wir erhalten: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! In diesem Fall ist die Verwendung einer rekursiven Funktion gerechtfertigt und sicher. Wir haben die Bedingung für das Verlassen des rekursiven Blocks klar definiert und sind zuversichtlich, dass sie erreichbar ist: Wir geben eine nicht negative ganze Zahl ein. Wenn die Zahl gleich Null oder Eins ist, geben wir das Ergebnis zurück, wenn die Zahl größer ist , multiplizieren wir das Ergebnis mit einer Funktion der Zahl n-1. Am Beispiel der Fakultät Drei:

factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)

		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1

Zur Vorsicht bei der Verwendung: Was ist die Schwachstelle dieser Funktion? Wenn Sie einer Methode eine negative Zahl als Parameter geben, dann erfolgt die Prüfung

if (n == 1 || n == 0) {
    return result;
}

macht keinen Sinn und wir werden in einen endlosen Kreislauf geraten, in dem wir uns selbst anrufen. Es lohnt sich, eine Prüfung auf Nicht-Negativität hinzuzufügen:

if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}

Und alles wird gut.

Was ist der Vorteil einer Methode gegenüber einer anderen? Es scheint keinen großen Unterschied zu geben, aber tatsächlich wirken sich viele rekursive Aufrufe negativ auf die Leistung und den Speicherverbrauch aus: Der Aufrufstapel ist eine nahezu unkontrollierbare Ressource und unter verschiedenen Bedingungen für den Aufruf derselben rekursiven Funktion Es kann sein, dass wir mit dieser Ressource Probleme bekommen oder auch nicht. Fast alle Probleme, die durch Iterationen (Zyklen wie for-each) gelöst werden, können auch rekursiv gelöst werden. Der Vorteil der Rekursion ist die Lesbarkeit und das einfache Schreiben; über die Nachteile haben wir oben gesprochen: Die Möglichkeit, sich „selbst ins Bein zu schießen“, ist keine Illusion. Noch vorsichtiger müssen Sie sein, wenn Sie die sogenannte „komplexe Rekursion“ verwenden: Eine Funktion A()ruft eine Funktion auf B(), die eine Funktion aufruft A(). Um solche Probleme zu lösen, ist ein umfassendes Verständnis der Funktionsweise der Rekursion erforderlich. Ein Beispiel für eine solche Aufgabe: Berechnen des Wertes von x^n/(n!). Die Fakultät ist, wie wir oben besprochen haben, auf der Menge der nicht negativen ganzen Zahlen definiert. Abschließend gebe ich den Lösungscode an. Die komplexe Rekursion besteht aus zwei Methoden:

private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Um eine Rekursion einzugeben, wird eine Methode verwendet calculate, die eine Methode aufruft power, die wiederum eine Methode aufruft calculate. Wir haben die Rekursionsbasis in der Potenzmethode definiert:

if (n == 1) return x;

Dort ist auch der Rekursionsschritt definiert:

return x * calculate(x, n - 1);

Es bleibt noch eine Prüfung der Gültigkeit der Eingabedaten hinzuzufügen:

Jede Zahl außer Null ist gleich der Potenz von Null 1. Wenn n = 0, dann n! = 1. Muss es zurückschicken 1.
Null zu jeder Potenz ist gleich Null.
Wir berücksichtigen keine Typunsicherheit 0^0und akzeptieren solche Eingabedaten als ungültig.

Mit allen Prüfungen sehen die Methoden folgendermaßen aus:

private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

    if (n == 0) {
        return 1;
    }

    if (x == 0) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Nun, wenn Sie eine Funktion aufrufen, müssen Sie daran denken, den Fehler abzufangen:

try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}

Kommentare

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION