Mathematik-Grundbegriffe für Programmierer

Rekursion und der rekursive Algorithmus

LinkedIn Learning kostenlos und unverbindlich testen!

Jetzt testen Alle Abonnements anzeigen
Bei einem rekursiven Algorithmus wird ein Algorithmus quasi durch sich selbst beschrieben. Die Rekursion muss jedoch an einer definierten Stelle beendet werden, sonst ist der Algorithmus nicht endlich. Bei rekursiven Algorithmen werden Funktionen oder Methoden bzw. deren Zustand vor der konkreten Abarbeitung auf einem Stapel (Stack) abgelegt. Die Ausführung erfolgt, indem der Stapel von oben nach unten abgearbeitet wird. Der letzte rekursive Schritt wird also als Erstes ausgeführt.
04:17

Transkript

In diesem Video beschäftigen wir uns mit der sogenannten Rekursion oder dem rekursiven Algorithmus. Die Idee dabei ist, dass ein Algorithmus durch sich selbst wieder beschrieben wird. Wir haben das, was man sehr oft vereinfacht einen Selbstaufruf bezeichnet. Wichtig ist, dass eine Rekursion an einer definierten Stelle beendet werden muss, denn sonst haben wir keinen Algorithmus. Ein Algorithmus muss endlich sein. Ich habe hier ein kleines rekursives Programm zur Verfügung in Java geschrieben, dass die Fakultät berechnet. Das heißt, Sie sehen, dass hier eine Methode definiert ist und an der Stelle erfolgt der Methodenaufruf von sich selbst, das heißt, die Methode ruft sich selbst wieder auf. Das ist dieser rekursive Effekt. Sie sehen auch, dass diese Methode einen Übergabewert hat und der Übergabewert hier beim Selbstaufruf wird immer um 1 reduziert. Das ist schlicht und einfach die Logik bei der Fakultät an der Stelle. Damit erreiche ich aber auch, dass ich eine Abbruchbedingung habe, das heißt, dieser Algorithmus in dem Fall ist endlich. Die Abbruchbedingung entsteht dadurch, dass wir eine Variable x hier haben, die mit dem Wert 4 in der Main-Methode eingeführt und initialisiert wird und dann der Methode als Parameter beim Aufruf übergeben wird. Im Inneren überprüfen wir mit "if x 0", ob dieser Wert größer Null ist und wir übergeben den um 1 reduzierten Wert dann beim Selbstaufruf der Methode wieder. Aber das ist nur eine spezielle Variante eben von dieser Fakultätsberechnung hier. Wichtig bei rekursiven Algorithmen ist, dass die Methodenfunktion beziehungsweise deren Zustand vor der konkreten Abarbeitung auf dem Stack abgelegt werden, also eine Art Stapel und das heißt, die Ausführung erfolgt, indem der Stapel von oben nach unten abgearbeitet wird. Der letzte rekursive Schritt wird also als erstes ausgeführt. Das können wir uns hier mit einem Debugger sehr schön ansehen. Ich habe einen Breakpoint bereits gesetzt, den sehen Sie in Zeile 5 und ich lass das Programm mal laufen. Ich bin also jetzt im ersten Aufruf der Funktion und ich steppe. ich bin im zweiten Aufruf der Funktion und Sie sehen, ich komme immer wieder an die Stelle, wo die Funktion sich selbst aufruft. Der Wert von x ist jetzt 1 und die Bedingung ist, dass x größer 0 sein muss. Das heißt, wir sind kurz davor, diese Selbstaufrufe zu verlassen. Das heißt, ich habe jetzt auf dem Stack mehrere Methodenaufrufe, die, sobald ich hier aus diesem Selbstaufruf, aus der Rekursion heraus bin, dann abgearbeitet werden. Jetzt liegt alles auf dem Stack und dieser wird jetzt von oben nach unten abgearbeitet. Sie sehen hier, wie sich der Wert von x verändert und jetzt erfolgt die Ausgabe, das haben wir hier unten. Sie haben also in diesem Video das Konzept des rekursiven Algorithmus kennen gelernt. Rekursion hat zwei wichtige Kennzeichen: Einmal, ein Algorithmus beschreibt sich quasi selbst, wir haben einen Selbstaufruf und die Rekursion legt erst einmal die Funktionsaufrufe beziehungsweise die Methoden und deren Zustand auf einem Stack ab, der dann von oben nach unten abgearbeitet wird und der letzte rekursive Schritt wird als erstes, der erste rekursive Schritt als letztes ausgeführt.

Mathematik-Grundbegriffe für Programmierer

Lernen Sie die Themenbereiche und Verfahren aus der Mathematik kennen, die bei der täglichen Programmierarbeit zum Einsatz kommen.

2 Std. 54 min (40 Videos)
Derzeit sind keine Feedbacks vorhanden...
Exklusiv für Abo-Kunden
Erscheinungsdatum:03.10.2016
Aktualisiert am:19.12.2016

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!