Rekursion ist ein grundlegendes Konzept in der Informatik und Mathematik, das es Funktionen ermöglicht, sich selbst aufzurufen und so die Lösung komplexer Probleme durch iterative Schritte zu ermöglichen. Eine häufig verwendete visuelle Darstellung zum Verständnis und zur Analyse der Ausführung rekursiver Funktionen ist ein Rekursionsbaum. In diesem Artikel werden wir die Theorie hinter Rekursionsbäumen, ihre Struktur und ihre Bedeutung für das Verständnis rekursiver Algorithmen untersuchen.

Was ist ein Rekursionsbaum?

Ein Rekursionsbaum ist eine grafische Darstellung, die den Ausführungsablauf einer rekursiven Funktion veranschaulicht. Es bietet eine visuelle Aufschlüsselung rekursiver Aufrufe und zeigt den Fortschritt des Algorithmus, während er verzweigt und schließlich einen Basisfall erreicht. Die Baumstruktur hilft bei der Analyse der zeitlichen Komplexität und beim Verständnis des rekursiven Prozesses.

Baumstruktur

Jeder Knoten in einem Rekursionsbaum repräsentiert einen bestimmten rekursiven Aufruf. Oben ist der erste Aufruf dargestellt, die nachfolgenden Aufrufe verzweigen sich darunter. Der Baum wächst nach unten und bildet eine hierarchische Struktur. Der Verzweigungsfaktor jedes Knotens hängt von der Anzahl der rekursiven Aufrufe innerhalb der Funktion ab. Darüber hinaus entspricht die Tiefe des Baums der Anzahl der rekursiven Aufrufe, bevor der Basisfall erreicht wird.

Basisfall

Der Basisfall dient als Beendigungsbedingung für eine rekursive Funktion. Es definiert den Punkt, an dem die Rekursion stoppt und die Funktion beginnt, Werte zurückzugeben. In einem Rekursionsbaum werden die Knoten, die den Basisfall darstellen, normalerweise als Blattknoten dargestellt, da sie nicht zu weiteren rekursiven Aufrufen führen.

Rekursive Aufrufe

Die untergeordneten Knoten in einem Rekursionsbaum stellen die rekursiven Aufrufe dar, die innerhalb der Funktion durchgeführt werden. Jeder untergeordnete Knoten entspricht einem separaten rekursiven Aufruf, was zur Erstellung neuer Unterprobleme führt. Die an diese rekursiven Aufrufe übergebenen Werte oder Parameter können unterschiedlich sein, was zu Variationen in den Eigenschaften der Teilprobleme führt.

Ausführungsablauf:

Das Durchlaufen eines Rekursionsbaums bietet Einblicke in den Ausführungsablauf einer rekursiven Funktion. Beginnend mit dem ersten Aufruf am Wurzelknoten folgen wir den Verzweigungen, um zu nachfolgenden Aufrufen zu gelangen, bis wir auf den Basisfall stoßen. Sobald die Basisfälle erreicht sind, beginnen die rekursiven Aufrufe zurückzukehren und ihre jeweiligen Knoten im Baum werden mit den zurückgegebenen Werten markiert. Die Durchquerung wird fortgesetzt, bis der gesamte Baum durchlaufen wurde.

Zeitkomplexitätsanalyse

Rekursionsbäume helfen bei der Analyse der zeitlichen Komplexität rekursiver Algorithmen. Indem wir die Struktur des Baums untersuchen, können wir die Anzahl der durchgeführten rekursiven Aufrufe und die auf jeder Ebene geleistete Arbeit bestimmen. Diese Analyse hilft dabei, die Gesamteffizienz des Algorithmus zu verstehen und mögliche Ineffizienzen oder Optimierungsmöglichkeiten zu identifizieren.

Einführung

• Stellen Sie sich ein Programm vor, das die Fakultät einer Zahl bestimmt. Diese Funktion verwendet eine Zahl N als Eingabe und gibt als Ergebnis die Fakultät von N zurück. Der Pseudocode dieser Funktion sieht folgendermaßen aus:

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• Die Rekursion wird durch die zuvor erwähnte Funktion veranschaulicht. Wir rufen eine Funktion auf, um die Fakultät einer Zahl zu bestimmen. Bei einem kleineren Wert derselben Zahl ruft sich diese Funktion dann selbst auf. Dies wird so lange fortgesetzt, bis wir den Grundfall erreichen, in dem es keine Funktionsaufrufe mehr gibt.
• Rekursion ist eine Technik zur Behandlung komplizierter Probleme, bei denen das Ergebnis von den Ergebnissen kleinerer Instanzen desselben Problems abhängt.
• Wenn wir über Funktionen nachdenken, wird eine Funktion als rekursiv bezeichnet, wenn sie sich selbst so lange aufruft, bis sie den Basisfall erreicht.
• Jede rekursive Funktion besteht aus zwei Hauptkomponenten: dem Basisfall und dem rekursiven Schritt. Wir gehen nicht mehr in die rekursive Phase über, sobald wir den Grundfall erreicht haben. Um eine endlose Rekursion zu verhindern, müssen Basisfälle richtig definiert werden und sind von entscheidender Bedeutung. Die Definition einer unendlichen Rekursion ist eine Rekursion, die niemals den Basisfall erreicht. Wenn ein Programm den Basisfall nie erreicht, kommt es weiterhin zu einem Stapelüberlauf.

Rekursionstypen

Generell gibt es zwei verschiedene Formen der Rekursion:

• Lineare Rekursion
• Baumrekursion
• Lineare Rekursion

Lineare Rekursion

• Eine Funktion, die sich bei jeder Ausführung nur einmal aufruft, wird linear rekursiv genannt. Ein schönes Beispiel für die lineare Rekursion ist die Fakultätsfunktion. Der Name „lineare Rekursion“ bezieht sich auf die Tatsache, dass die Ausführung einer linear rekursiven Funktion eine lineare Zeitspanne benötigt.
• Schauen Sie sich den folgenden Pseudocode an:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Wenn wir uns die Funktion doSomething(n) ansehen, akzeptiert sie einen Parameter namens n und führt einige Berechnungen durch, bevor sie dieselbe Prozedur noch einmal aufruft, jedoch mit niedrigeren Werten.
• Wenn die Methode doSomething() mit dem Argumentwert n aufgerufen wird, nehmen wir an, dass T(n) die Gesamtzeit darstellt, die zum Abschließen der Berechnung benötigt wird. Hierzu können wir auch eine Rekursionsrelation formulieren, T(n) = T(n-1) + K. K dient hier als Konstante. Die Konstante K ist enthalten, da die Funktion einige Zeit benötigt, um einer Variablen Speicher zuzuordnen bzw. die Zuweisung aufzuheben oder eine mathematische Operation auszuführen. Wir verwenden K, um die Zeit zu definieren, da sie so winzig und unbedeutend ist.
• Die Zeitkomplexität dieses rekursiven Programms kann einfach berechnet werden, da die Methode doSomething() im schlimmsten Fall n-mal aufgerufen wird. Formal gesehen ist die zeitliche Komplexität der Funktion O(N).

Baumrekursion

• Wenn Sie in Ihrem rekursiven Fall einen rekursiven Aufruf mehr als einmal durchführen, spricht man von einer Baumrekursion. Ein wirkungsvolles Beispiel für die Baumrekursion ist die Fibonacci-Folge. Baumrekursive Funktionen arbeiten in exponentieller Zeit; sie sind in ihrer zeitlichen Komplexität nicht linear.
• Schauen Sie sich den Pseudocode unten an:

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• Der einzige Unterschied zwischen diesem Code und dem vorherigen besteht darin, dass dieser noch einmal dieselbe Funktion mit einem niedrigeren Wert von n aufruft.
• Setzen wir T(n) = T(n-1) + T(n-2) + k als Wiederholungsbeziehung für diese Funktion. K dient erneut als Konstante.
• Wenn mehr als ein Aufruf derselben Funktion mit kleineren Werten ausgeführt wird, wird diese Art der Rekursion als Baumrekursion bezeichnet. Das Spannende ist nun: Wie zeitaufwändig ist diese Funktion?
• Machen Sie eine Schätzung basierend auf dem Rekursionsbaum unten für dieselbe Funktion.
  
• Möglicherweise kommt Ihnen der Gedanke, dass es schwierig ist, die Zeitkomplexität abzuschätzen, indem Sie eine rekursive Funktion direkt betrachten, insbesondere wenn es sich um eine Baumrekursion handelt. Die Rekursionsbaummethode ist eine von mehreren Techniken zur Berechnung der zeitlichen Komplexität solcher Funktionen. Lassen Sie es uns genauer untersuchen.

Was ist die Rekursionsbaummethode?

• Wiederholungsbeziehungen wie T(N) = T(N/2) + N oder die beiden, die wir weiter oben im Abschnitt „Arten von Rekursionen“ behandelt haben, werden mithilfe des Rekursionsbaum-Ansatzes gelöst. Bei diesen wiederkehrenden Beziehungen wird häufig eine „Teile-und-Herrsche“-Strategie zur Lösung von Problemen verwendet.
• Es braucht Zeit, die Antworten auf die kleineren Teilprobleme zu integrieren, die entstehen, wenn ein größeres Problem in kleinere Teilprobleme zerlegt wird.
• Die Wiederholungsrelation lautet beispielsweise T(N) = 2 * T(N/2) + O(N) für die Merge-Sortierung. Die Zeit, die benötigt wird, um die Antworten auf zwei Teilprobleme mit einer Gesamtgröße von T(N/2) zu kombinieren, beträgt O(N), was auch auf der Implementierungsebene gilt.
• Da die Wiederholungsbeziehung für die binäre Suche beispielsweise T(N) = T(N/2) + 1 ist, wissen wir, dass jede Iteration der binären Suche zu einem Suchraum führt, der halbiert wird. Sobald das Ergebnis bestimmt ist, verlassen wir die Funktion. Der Wiederholungsrelation wurde +1 hinzugefügt, da es sich um eine Operation mit konstanter Zeit handelt.
• Zu berücksichtigen ist die Wiederholungsbeziehung T(n) = 2T(n/2) + Kn. Kn bezeichnet die Zeit, die benötigt wird, um die Antworten auf n/2-dimensionale Teilprobleme zu kombinieren.
• Lassen Sie uns den Rekursionsbaum für die oben genannte Wiederholungsbeziehung darstellen.

Aus der Untersuchung des obigen Rekursionsbaums können wir einige Schlussfolgerungen ziehen, darunter:

1. Das Ausmaß des Problems auf jeder Ebene ist alles, was für die Bestimmung des Wertes eines Knotens ausschlaggebend ist. Die Problemgröße beträgt n auf Ebene 0, n/2 auf Ebene 1, n/2 auf Ebene 2 und so weiter.

2. Im Allgemeinen definieren wir die Höhe des Baums als gleich log (n), wobei n die Größe des Problems ist und die Höhe dieses Rekursionsbaums gleich der Anzahl der Ebenen im Baum ist. Dies ist wahr, weil, wie wir gerade festgestellt haben, die Divide-and-Conquer-Strategie von Wiederholungsbeziehungen zur Lösung von Problemen verwendet wird und der Übergang von der Problemgröße n zur Problemgröße 1 lediglich log (n) Schritte erfordert.

• Betrachten Sie zum Beispiel den Wert von N = 16. Wenn wir N bei jedem Schritt durch 2 dividieren dürfen, wie viele Schritte sind dann erforderlich, um N = 1 zu erhalten? Wenn man bedenkt, dass wir bei jedem Schritt durch zwei dividieren, ist die richtige Antwort 4, was dem Wert von log(16) zur Basis 2 entspricht.

log(16) Basis 2

log(2^4) Basis 2

4 * log(2) zur Basis 2, da log(a) zur Basis a = 1

Index von Java

also 4 * log(2) Basis 2 = 4

3. Auf jeder Ebene wird der zweite Term in der Wiederholung als Wurzel betrachtet.

Obwohl das Wort „Baum“ im Namen dieser Strategie vorkommt, müssen Sie kein Experte für Bäume sein, um es zu verstehen.

Wie verwende ich einen Rekursionsbaum, um Wiederholungsbeziehungen zu lösen?

Die Kosten des Teilproblems in der Rekursionsbaumtechnik sind die Zeit, die zur Lösung des Teilproblems benötigt wird. Wenn Ihnen also der Begriff „Kosten“ im Zusammenhang mit dem Rekursionsbaum auffällt, bezieht er sich einfach auf die Zeit, die zur Lösung eines bestimmten Teilproblems benötigt wird.

Lassen Sie uns alle diese Schritte anhand einiger Beispiele verstehen.

Beispiel

Betrachten Sie die Wiederholungsbeziehung,

T(n) = 2T(n/2) + K

Lösung

Die angegebene Wiederholungsbeziehung weist die folgenden Eigenschaften auf:

Ein Problem der Größe n wird in zwei Teilprobleme der Größe n/2 unterteilt. Die Kosten für die Kombination der Lösungen dieser Teilprobleme betragen K.

Jedes Problem der Größe n/2 wird in zwei Unterprobleme der Größe n/4 usw. unterteilt.

Auf der letzten Ebene wird die Teilproblemgröße auf 1 reduziert. Mit anderen Worten, wir erreichen endlich den Basisfall.

Java-Liste von

Befolgen wir die Schritte zur Lösung dieser Wiederholungsbeziehung:

Schritt 1: Zeichnen Sie den Rekursionsbaum

Schritt 2: Berechnen Sie die Höhe des Baumes

Da wir wissen, dass, wenn wir eine Zahl kontinuierlich durch 2 dividieren, irgendwann diese Zahl auf 1 reduziert wird. Nehmen wir wie bei der Problemgröße N an, dass N nach K Divisionen durch 2 gleich 1 wird, was impliziert, ( n / 2^k) = 1

Dabei ist n / 2^k die Problemgröße auf der letzten Ebene und immer gleich 1.

Jetzt können wir den Wert von k leicht aus dem obigen Ausdruck berechnen, indem wir log() auf beide Seiten anwenden. Nachfolgend finden Sie eine klarere Ableitung:

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) Basis 2

Die Höhe des Baums beträgt also log(n) zur Basis 2.

Schritt 3: Berechnen Sie die Kosten auf jeder Ebene

• Kosten auf Level-0 = K, zwei Teilprobleme werden zusammengeführt.
• Kosten auf Ebene 1 = K + K = 2*K, zwei Teilprobleme werden zweimal zusammengeführt.
• Kosten auf Ebene 2 = K + K + K + K = 4*K, zwei Teilprobleme werden viermal zusammengeführt. und so weiter....

Schritt 4: Berechnen Sie die Anzahl der Knoten auf jeder Ebene

Bestimmen wir zunächst die Anzahl der Knoten in der letzten Ebene. Aus dem Rekursionsbaum können wir dies ableiten

• Level-0 hat 1 (2^0) Knoten
• Level-1 hat 2 (2^1) Knoten
• Level-2 hat 4 (2^2) Knoten
• Level-3 hat 8 (2^3) Knoten

Die Ebene log(n) sollte also 2^(log(n)) Knoten haben, also n Knoten.

sts herunterladen

Schritt 5: Summieren Sie die Kosten aller Ebenen

• Die Gesamtkosten können wie folgt geschrieben werden:
• Gesamtkosten = Kosten aller Ebenen außer der letzten Ebene + Kosten der letzten Ebene
• Gesamtkosten = Kosten für Level-0 + Kosten für Level-1 + Kosten für Level-2 + .... + Kosten für Level-Log(n) + Kosten für das letzte Level

Die Kosten der letzten Ebene werden separat berechnet, da es sich um den Basisfall handelt und auf der letzten Ebene keine Zusammenführung erfolgt. Daher sind die Kosten für die Lösung eines einzelnen Problems auf dieser Ebene ein konstanter Wert. Nehmen wir es als O (1).

Setzen wir die Werte in die Formeln ein,

• T(n) = K + 2*K + 4*K + .... + log(n)` mal + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) mal)` + `O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) mal + O(n)

Wenn Sie sich den obigen Ausdruck genau ansehen, bildet er eine geometrische Folge (a, ar, ar^2, ar^3 ... unendliche Zeit). Die Summe von GP ergibt sich aus S(N) = a / (r – 1). Hier ist der erste Term und r ist das gemeinsame Verhältnis.