Rekursion (Informatik) - Recursion (computer science)

Baum, der mit der Programmiersprache Logo erstellt wurde und stark auf Rekursion basiert. Jeder Zweig kann als kleinere Version eines Baumes betrachtet werden.

In der Informatik ist Rekursion eine Methode zur Lösung eines Problems, bei der die Lösung von Lösungen für kleinere Instanzen desselben Problems abhängt. Solche Probleme können im Allgemeinen durch Iteration gelöst werden , aber dies muss die kleineren Instanzen zur Programmierzeit identifizieren und indizieren. Rekursion löst solche rekursiven Probleme durch die Verwendung von Funktionen , die sich selbst aus ihrem eigenen Code aufrufen. Der Ansatz lässt sich auf viele Arten von Problemen anwenden, und die Rekursion ist eine der zentralen Ideen der Informatik.

Die Macht der Rekursion liegt offenbar in der Möglichkeit, eine unendliche Menge von Objekten durch eine endliche Aussage zu definieren. Auf die gleiche Weise können unendlich viele Berechnungen durch ein endliches rekursives Programm beschrieben werden, auch wenn dieses Programm keine expliziten Wiederholungen enthält.

—  Niklaus Wirth , Algorithmen + Datenstrukturen = Programme , 1976

Die meisten Computer - Programmiersprachen unterstützen Rekursion durch eine Funktion ermöglicht selbst aus den eigenen Code aufzurufen. Einige funktionale Programmiersprachen (zum Beispiel Clojure ) definieren keine Schleifenkonstrukte, sondern verlassen sich ausschließlich auf Rekursion, um Code wiederholt aufzurufen. In der Berechenbarkeitstheorie wird bewiesen , dass diese rein rekursiven Sprachen Turing-vollständig sind ; das bedeutet, dass sie genauso mächtig sind (sie können verwendet werden, um dieselben Probleme zu lösen) wie imperative Sprachen, die auf Kontrollstrukturen wie whileund basieren for.

Das wiederholte Aufrufen einer Funktion aus sich heraus kann dazu führen, dass die Aufrufliste eine Größe hat, die der Summe der Eingabegrößen aller beteiligten Aufrufe entspricht. Daraus folgt, dass für Probleme, die leicht durch Iteration gelöst werden können, die Rekursion im Allgemeinen weniger effizient ist , und dass es für große Probleme grundlegend ist, Optimierungstechniken wie die Tail-Call- Optimierung zu verwenden.

Rekursive Funktionen und Algorithmen

Eine übliche Taktik der Computerprogrammierung besteht darin, ein Problem in Teilprobleme desselben Typs wie das Original aufzuteilen, diese Teilprobleme zu lösen und die Ergebnisse zu kombinieren. Dies wird oft als die Divide-and-Conquer-Methode bezeichnet ; in Kombination mit einer Nachschlagetabelle , die die Ergebnisse von zuvor gelösten Teilproblemen speichert (um sie nicht wiederholt zu lösen und zusätzliche Rechenzeit zu verursachen), kann es als dynamische Programmierung oder Memoisierung bezeichnet werden .

Basisfall

Eine rekursive Funktionsdefinition hat einen oder mehrere Basisfälle , dh Eingaben, für die die Funktion trivial (ohne Wiederholung) ein Ergebnis liefert , und einen oder mehrere rekursive Fälle , dh Eingaben, für die das Programm rekursiert (sich selbst aufruft) . Beispielsweise kann die Fakultätsfunktion rekursiv durch die Gleichungen 0! = 1 und für alle n > 0 gilt n ! = n ( n − 1)! . Keine der Gleichungen allein bildet eine vollständige Definition; der erste ist der Basisfall und der zweite der rekursive Fall. Da der Basisfall die Rekursionskette unterbricht, wird er manchmal auch als "terminierender Fall" bezeichnet.

Die Aufgabe der rekursiven Fälle kann darin gesehen werden, komplexe Eingaben in einfachere zu zerlegen. In einer richtig entworfenen rekursiven Funktion muss bei jedem rekursiven Aufruf das Eingabeproblem so vereinfacht werden, dass schließlich der Basisfall erreicht werden muss. ( Eine Ausnahme bilden Funktionen, die unter normalen Umständen nicht beendet werden sollen – zum Beispiel einige System- und Serverprozesse .) Wenn ein Basisfall nicht geschrieben oder falsch getestet wird, kann dies zu einer Endlosschleife führen .

Für einige Funktionen (wie eine, die die Reihe für e = 1/0! + 1/1! + 1/2! + 1/3! + ... berechnet ) gibt es keinen offensichtlichen Basisfall, der durch die Eingabedaten impliziert wird ; für diese kann man einen Parameter (wie die Anzahl der hinzuzufügenden Terme in unserem Reihenbeispiel) hinzufügen, um ein 'Abbruchkriterium' bereitzustellen, das den Basisfall festlegt. Ein solches Beispiel wird natürlicher von corecursion behandelt , wo aufeinanderfolgende Terme in der Ausgabe die Teilsummen sind; dies kann in eine Rekursion umgewandelt werden, indem der Indexierungsparameter verwendet wird, um zu sagen "berechne den n- ten Term ( n- te Teilsumme)".

Rekursive Datentypen

Viele Computerprogramme müssen beliebig große Datenmengen verarbeiten oder erzeugen . Rekursion ist eine Technik zur Darstellung von Daten, deren genaue Größe dem Programmierer unbekannt ist : Der Programmierer kann diese Daten mit einer selbstreferenziellen Definition spezifizieren . Es gibt zwei Arten von selbstreferenziellen Definitionen: induktive und koinduktive Definitionen.

Induktiv definierte Daten

Eine induktiv definierte rekursive Datendefinition ist eine Definition, die angibt, wie Instanzen der Daten konstruiert werden. Zum Beispiel verkettete Listen induktiv (hier mit definiert werden Haskell - Syntax):

data ListOfStrings = EmptyList | Cons String ListOfStrings

Der obige Code gibt an, dass eine Liste von Zeichenfolgen entweder leer ist oder eine Struktur, die eine Zeichenfolge und eine Liste von Zeichenfolgen enthält. Die Selbstreferenz in der Definition erlaubt den Aufbau von Listen beliebiger (endlicher) Anzahl von Strings.

Ein weiteres Beispiel für induktive Definition sind die natürlichen Zahlen (oder positiven ganzen Zahlen ):

A natural number is either 1 or n+1, where n is a natural number.

In ähnlicher Weise werden rekursive Definitionen häufig verwendet, um die Struktur von Ausdrücken und Anweisungen in Programmiersprachen zu modellieren . Sprachdesigner drücken Grammatiken oft in einer Syntax wie der Backus-Naur-Form aus ; Hier ist eine solche Grammatik für eine einfache Sprache arithmetischer Ausdrücke mit Multiplikation und Addition:

 <expr> ::= <number>
          | (<expr> * <expr>)
          | (<expr> + <expr>)

Dies besagt, dass ein Ausdruck entweder eine Zahl, ein Produkt zweier Ausdrücke oder eine Summe zweier Ausdrücke ist. Durch rekursive Bezugnahme auf Ausdrücke in der zweiten und dritten Zeile erlaubt die Grammatik beliebig komplizierte arithmetische Ausdrücke wie (5 * ((3 * 6) + 8)), mit mehr als einer Produkt- oder Summenoperation in einem einzigen Ausdruck.

Koinduktiv definierte Daten und Kokursion

Eine koinduktive Datendefinition ist eine, die die Operationen spezifiziert, die an einem Datenelement ausgeführt werden können; typischerweise werden selbstreferentielle koinduktive Definitionen für Datenstrukturen unendlicher Größe verwendet.

Eine coinductive Definition der unendlichen Ströme von Strings, informell gegeben, könnte wie folgt aussehen:

A stream of strings is an object s such that:
 head(s) is a string, and
 tail(s) is a stream of strings.

Dies ist einer induktiven Definition von Stringlisten sehr ähnlich; der Unterschied ist , dass diese Definition spezifiziert , wie die Inhalte der Datenstruktur, nämlich für den Zugriff über die Zugriffsfunktionen und -und was diese Inhalte sein können, während die induktiven Definition gibt , wie die Struktur zu schaffen , und was es kann aus erstellt werden. headtail

Corecursion ist mit Koinduktion verwandt und kann verwendet werden, um bestimmte Instanzen von (möglicherweise) unendlichen Objekten zu berechnen. Als Programmiertechnik wird es am häufigsten im Zusammenhang mit faulen Programmiersprachen verwendet und kann der Rekursion vorzuziehen sein, wenn die gewünschte Größe oder Genauigkeit der Ausgabe eines Programms unbekannt ist. In solchen Fällen erfordert das Programm sowohl eine Definition für ein unendlich großes (oder unendlich genaues) Ergebnis als auch einen Mechanismus, um einen endlichen Teil dieses Ergebnisses zu nehmen. Das Problem der Berechnung der ersten n Primzahlen lässt sich mit einem kernkursiven Programm lösen (zB hier ).

Arten der Rekursion

Einzelrekursion und Mehrfachrekursion

Eine Rekursion, die nur eine einzige Selbstreferenz enthält, wird als . bezeichnet einzelne Rekursion , während eine Rekursion, die mehrere Selbstreferenzen enthält, als . bekannt istmehrfache Rekursion . Standardbeispiele einer einzelnen Rekursion umfassen eine Listendurchquerung, wie beispielsweise bei einer linearen Suche, oder das Berechnen der Fakultätsfunktion, während Standardbeispiele einer Mehrfachrekursion eineBaumdurchquerungumfassen, wie beispielsweise bei einer Tiefensuche.

Eine einzelne Rekursion ist oft viel effizienter als eine mehrfache Rekursion und kann im Allgemeinen durch eine iterative Berechnung ersetzt werden, die in linearer Zeit abläuft und konstanten Platz benötigt. Im Gegensatz dazu kann eine Mehrfachrekursion exponentiell Zeit und Raum erfordern und ist grundsätzlicher rekursiv, da sie ohne einen expliziten Stapel nicht durch Iteration ersetzt werden kann.

Mehrfache Rekursion kann manchmal in eine einzelne Rekursion umgewandelt werden (und, falls gewünscht, von dort in eine Iteration). Während zum Beispiel die naive Berechnung der Fibonacci-Folge eine mehrfache Iteration ist, da jeder Wert zwei vorherige Werte erfordert, kann sie durch eine einzelne Rekursion berechnet werden, indem zwei aufeinanderfolgende Werte als Parameter übergeben werden. Dies ist natürlicher als corecursion formuliert, baut aus den Anfangswerten auf und verfolgt bei jedem Schritt zwei aufeinanderfolgende Werte – siehe corecursion: Beispiele . Ein komplexeres Beispiel ist die Verwendung eines Binärbaums mit Thread , der eine iterative Baumdurchquerung anstelle einer mehrfachen Rekursion ermöglicht.

Indirekte Rekursion

Die meisten grundlegenden Beispiele für Rekursion und die meisten der hier vorgestellten Beispiele demonstrieren direkte Rekursion , bei der sich eine Funktion selbst aufruft. Eine indirekte Rekursion tritt auf, wenn eine Funktion nicht von sich selbst, sondern von einer anderen aufgerufenen Funktion (entweder direkt oder indirekt) aufgerufen wird. Zum Beispiel, wenn f rufe f, dassdirekte Rekursion, aber wenn f ruft g die Anrufe f, dann istindirekte Rekursion von f. Ketten von drei oder mehr Funktionen sind möglich; Funktion 1 ruft beispielsweise Funktion 2 auf, Funktion 2 ruft Funktion 3 auf und Funktion 3 ruft erneut Funktion 1 auf.

Indirekte Rekursion wird auch als gegenseitige Rekursion bezeichnet , was ein symmetrischerer Begriff ist, obwohl dies nur ein Unterschied in der Betonung ist, kein anderer Begriff. Das heißt, wenn f ruft g und dann g Anrufe f, die wiederum rufen g wieder, aus der Sicht von f allein, f indirekt Rekursion, während aus der Sicht von g allein, es indirekt Rekursion, während aus der Sicht beider sind f und g wechselseitig aufeinander rekursiv. In ähnlicher Weise kann eine Menge von drei oder mehr Funktionen, die sich gegenseitig aufrufen, als eine Menge gegenseitig rekursiver Funktionen bezeichnet werden.

Anonyme Rekursion

Die Rekursion erfolgt normalerweise durch explizites Aufrufen einer Funktion mit Namen. Die Rekursion kann jedoch auch durch implizites Aufrufen einer Funktion basierend auf dem aktuellen Kontext erfolgen, was besonders für anonyme Funktionen nützlich ist und als anonyme Rekursion bezeichnet wird .

Strukturelle versus generative Rekursion

Einige Autoren klassifizieren Rekursion entweder als "strukturell" oder "generativ". Die Unterscheidung bezieht sich darauf, woher ein rekursives Verfahren die Daten erhält, mit denen es arbeitet, und wie es diese Daten verarbeitet:

[Funktionen, die strukturierte Daten verbrauchen] zerlegen normalerweise ihre Argumente in ihre unmittelbaren strukturellen Komponenten und verarbeiten diese Komponenten dann. Wenn eine der unmittelbaren Komponenten derselben Datenklasse angehört wie die Eingabe, ist die Funktion rekursiv. Aus diesem Grund bezeichnen wir diese Funktionen als (STRUKTURELL) REKURSIVE FUNKTIONEN.

—  Felleisen, Findler, Flatt und Krishnaurthi, Wie man Programme entwirft , 2001

Somit besteht das definierende Merkmal einer strukturell rekursiven Funktion darin, dass das Argument für jeden rekursiven Aufruf der Inhalt eines Felds der ursprünglichen Eingabe ist. Strukturelle Rekursion umfasst fast alle Baumdurchquerungen, einschließlich XML-Verarbeitung, Erstellung binärer Bäume und Suche usw. Unter Berücksichtigung der algebraischen Struktur der natürlichen Zahlen (d. h., eine natürliche Zahl ist entweder Null oder der Nachfolger einer natürlichen Zahl), können Funktionen wie als Fakultät kann auch als strukturelle Rekursion angesehen werden.

Generative Rekursion ist die Alternative:

Viele bekannte rekursive Algorithmen generieren aus den gegebenen Daten ein völlig neues Datenstück und wiederholen sich darauf. HtDP ( How to Design Programs ) bezeichnet diese Art als generative Rekursion. Beispiele für generative Rekursion sind: gcd , quicksort , binäre Suche , mergesort , Newtons Methode , Fraktale und adaptive Integration .

—  Matthias Felleisen, Advanced Functional Programming , 2002

Diese Unterscheidung ist wichtig, um die Beendigung einer Funktion zu beweisen .

  • Alle strukturell rekursiven Funktionen auf endlichen ( induktiv definierten ) Datenstrukturen können durch strukturelle Induktion leicht terminiert werden : Intuitiv erhält jeder rekursive Aufruf ein kleineres Stück Eingabedaten, bis ein Basisfall erreicht ist.
  • Im Gegensatz dazu führen generativ rekursive Funktionen nicht unbedingt kleinere Eingaben in ihre rekursiven Aufrufe ein, sodass der Nachweis ihrer Beendigung nicht unbedingt so einfach ist und das Vermeiden von Endlosschleifen größere Sorgfalt erfordert. Diese generativ rekursiven Funktionen können oft als korekursive Funktionen interpretiert werden – jeder Schritt erzeugt die neuen Daten, wie z.
  • In Bezug auf Schleifenvarianten liegt eine strukturelle Rekursion vor, wenn es eine offensichtliche Schleifenvariante gibt, nämlich Größe oder Komplexität, die endlich beginnt und mit jedem rekursiven Schritt abnimmt.
  • Im Gegensatz dazu liegt eine generative Rekursion vor, wenn es keine so offensichtliche Schleifenvariante gibt und die Beendigung von einer Funktion abhängt, wie z.

Umsetzungsfragen

Bei der tatsächlichen Implementierung können anstelle einer reinen rekursiven Funktion (einfache Prüfung für den Basisfall, ansonsten rekursiver Schritt) aus Gründen der Klarheit oder Effizienz eine Reihe von Modifikationen vorgenommen werden. Diese beinhalten:

  • Wrapper-Funktion (oben)
  • Kurzschließen des Basisgehäuses, auch bekannt als "Arm's-Length Recursion" (unten)
  • Hybridalgorithmus (unten) – Wechsel zu einem anderen Algorithmus, sobald die Daten klein genug sind

Aufgrund der Eleganz sind Wrapper-Funktionen allgemein anerkannt, während das Kurzschließen des Basisgehäuses vor allem in der Wissenschaft verpönt ist. Hybridalgorithmen werden oft aus Effizienzgründen verwendet, um den Overhead der Rekursion in kleinen Fällen zu reduzieren, und die Rekursion nach fremdüblichen Bedingungen ist ein Sonderfall davon.

Wrapper-Funktion

Eine Wrapper-Funktion ist eine Funktion, die direkt aufgerufen wird, aber nicht selbst rekursiert, sondern eine separate Hilfsfunktion aufruft, die tatsächlich die Rekursion durchführt.

Wrapper-Funktionen können verwendet werden, um Parameter zu validieren (damit die rekursive Funktion diese überspringen kann), eine Initialisierung durchzuführen (Speicher zuordnen, Variablen initialisieren), insbesondere für Hilfsvariablen wie "Rekursionsniveau" oder Teilberechnungen für die Memoisierung , und um Ausnahmen und Fehler zu behandeln . In Sprachen, die verschachtelte Funktionen unterstützen , kann die Hilfsfunktion innerhalb der Wrapper-Funktion verschachtelt werden und einen gemeinsamen Gültigkeitsbereich verwenden. Wenn keine verschachtelten Funktionen vorhanden sind, sind Hilfsfunktionen stattdessen eine separate Funktion, wenn möglich private (da sie nicht direkt aufgerufen werden), und Informationen werden mithilfe von pass-by-reference an die Wrapper-Funktion weitergegeben .

Kurzschließen des Basisgehäuses

Fakultät: gewöhnlich vs. Kurzschluss
Gewöhnliche Rekursion Kurzschlussrekursion
int fac1(int n) {
   if (n <= 0)
      return 1;
   else
      return fac1(n-1)*n;
}
static int fac2(int n) {
   // assert(n >= 2);
   if (n == 2)
      return 2;
   else
      return fac2(n-1)*n;
}
int fac2wrapper(int n) {
   if (n <= 1)
      return 1;
   else
      return fac2(n);
}

Das Kurzschließen des Basisfalls, auch bekannt als Arm's-Length-Rekursion , besteht darin, den Basisfall zu überprüfen, bevor ein rekursiver Aufruf durchgeführt wird – dh zu prüfen, ob der nächste Aufruf der Basisfall sein wird, anstatt anzurufen und dann nach dem Basisfall zu suchen . Das Kurzschließen erfolgt insbesondere aus Effizienzgründen, um den Overhead eines sofort zurückkehrenden Funktionsaufrufs zu vermeiden. Beachten Sie, dass, da der Basisfall bereits geprüft wurde (unmittelbar vor dem rekursiven Schritt), dieser nicht separat geprüft werden muss, sondern eine Wrapper-Funktion für den Fall verwendet werden muss, wenn die Gesamtrekursion mit dem Basisfall beginnt selbst. Zum Beispiel ist in der Fakultätsfunktion der Basisfall richtigerweise 0! = 1, während sofort 1 für 1 zurückgegeben wird! ist ein Kurzschluss und kann 0 verpassen; Dies kann durch eine Wrapper-Funktion abgeschwächt werden. Die Box zeigt C- Code, um die Fakultätsfälle 0 und 1 zu verkürzen.

Kurzschluss ist in erster Linie ein Problem, wenn viele Basisfälle angetroffen werden, wie z. B. Null-Zeiger in einem Baum, die in der Anzahl der Funktionsaufrufe linear sein können, daher erhebliche Einsparungen für O ( n ) -Algorithmen; dies wird unten für eine Tiefensuche veranschaulicht. Das Kurzschließen in einem Baum entspricht dem Betrachten eines Blatts (nichtleerer Knoten ohne Kinder) als Basisfall, anstatt einen leeren Knoten als Basisfall zu betrachten. Wenn es nur einen einzigen Basisfall gibt, wie zum Beispiel bei der Berechnung der Fakultät, bietet das Kurzschließen nur O (1) Einsparungen.

Konzeptionell kann das Kurzschließen entweder so betrachtet werden, dass es denselben Basisfall und rekursiven Schritt hat, den Basisfall nur vor der Rekursion überprüft, oder als einen anderen Basisfall (ein Schritt vom Standardbasisfall entfernt) betrachtet werden und a komplexerer rekursiver Schritt, nämlich "Prüfe gültig, dann rekursiv", wie bei der Betrachtung von Blattknoten anstelle von Null-Knoten als Basisfälle in einem Baum. Da das Kurzschließen im Vergleich zur klaren Trennung von Basisfall und rekursivem Schritt bei der Standardrekursion einen komplizierteren Ablauf hat, wird es insbesondere in der akademischen Welt oft als schlechter Stil angesehen.

Tiefensuche

Ein grundlegendes Beispiel für Kurzschlüsse wird in der Tiefensuche (DFS) eines Binärbaums gegeben; siehe Abschnitt Binärbäume für eine standardmäßige rekursive Diskussion.

Der standardmäßige rekursive Algorithmus für ein DFS ist:

  • Basisfall: Wenn der aktuelle Knoten Null ist, gebe false zurück
  • rekursiver Schritt: andernfalls Wert des aktuellen Knotens prüfen, bei Übereinstimmung true zurückgeben, andernfalls Rekurs auf Kinder

Beim Kurzschließen ist dies stattdessen:

  • Wert des aktuellen Knotens prüfen, bei Übereinstimmung true zurückgeben,
  • andernfalls bei Kindern, wenn nicht Null, dann rekursiv.

In Bezug auf die Standardschritte verschiebt dies die Basisfallprüfung vor den rekursiven Schritt. Alternativ können diese als eine andere Form von Basisfall bzw. rekursivem Schritt betrachtet werden. Beachten Sie, dass dies eine Wrapper-Funktion erfordert, um den Fall zu behandeln, wenn der Baum selbst leer ist (der Stammknoten ist Null).

Im Fall eines perfekten Binärbaums der Höhe h gibt es 2 h +1 −1 Knoten und 2 h +1 Null-Zeiger als Kinder (2 für jedes der 2 h- Blätter), sodass das Kurzschließen die Anzahl der Funktionen kürzt Anrufe im schlimmsten Fall halbieren.

In C kann der rekursive Standardalgorithmus wie folgt implementiert werden:

bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // base case
    else if (tree_node->data == i)
        return true;
    else
        return tree_contains(tree_node->left, i) ||
               tree_contains(tree_node->right, i);
}

Der Kurzschlussalgorithmus kann implementiert werden als:

// Wrapper function to handle empty tree
bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // empty tree
    else
        return tree_contains_do(tree_node, i);  // call auxiliary function
}

// Assumes tree_node != NULL
bool tree_contains_do(struct node *tree_node, int i) {
    if (tree_node->data == i)
        return true;  // found
    else  // recurse
        return (tree_node->left  && tree_contains_do(tree_node->left,  i)) ||
               (tree_node->right && tree_contains_do(tree_node->right, i));
}

Beachten Sie die Verwendung der Kurzschlussauswertung der Booleschen && (AND)-Operatoren, so dass der rekursive Aufruf nur erfolgt, wenn der Knoten gültig ist (nicht Null). Beachten Sie, dass der erste Term im AND ein Zeiger auf einen Knoten ist, der zweite Term jedoch ein boolescher Wert ist, sodass der Gesamtausdruck einen booleschen Wert ergibt. Dies ist eine gängige Redewendung beim rekursiven Kurzschließen. Dies erfolgt zusätzlich zur Kurzschlussauswertung des Booleschen || (OR)-Operator, um nur das rechte Kind zu überprüfen, wenn das linke Kind fehlschlägt. Tatsächlich kann der gesamte Kontrollfluss dieser Funktionen durch einen einzigen booleschen Ausdruck in einer return-Anweisung ersetzt werden, aber die Lesbarkeit leidet ohne Effizienzvorteile.

Hybrid-Algorithmus

Rekursive Algorithmen sind bei kleinen Datenmengen aufgrund des Mehraufwands wiederholter Funktionsaufrufe und -rückgaben oft ineffizient. Aus diesem Grund beginnen effiziente Implementierungen rekursiver Algorithmen oft mit dem rekursiven Algorithmus, wechseln dann aber zu einem anderen Algorithmus, wenn die Eingabe klein wird. Ein wichtiges Beispiel ist die Zusammenführungssortierung , die häufig durch Umschalten auf die nicht-rekursive Einfügungssortierung implementiert wird, wenn die Daten ausreichend klein sind, wie bei der gekachelten Zusammenführungssortierung . Hybride rekursive Algorithmen können oft weiter verfeinert werden, wie in Timsort , abgeleitet von einem hybriden Merge-Sort/Insertion-Sort.

Rekursion versus Iteration

Rekursion und Iteration sind gleichermaßen ausdrucksstark: Rekursion kann durch Iteration mit einem expliziten Call-Stack ersetzt werden , während Iteration durch Tail-Rekursion ersetzt werden kann . Welcher Ansatz bevorzugt wird, hängt vom betrachteten Problem und der verwendeten Sprache ab. Bei der imperativen Programmierung wird Iteration bevorzugt, insbesondere für die einfache Rekursion, da sie den Overhead von Funktionsaufrufen und Aufrufstapelverwaltung vermeidet, aber Rekursion wird im Allgemeinen für Mehrfachrekursionen verwendet. Im Gegensatz dazu wird in funktionalen Sprachen die Rekursion bevorzugt, wobei die Tail-Rekursion-Optimierung zu wenig Overhead führt. Die Implementierung eines Algorithmus unter Verwendung von Iteration ist möglicherweise nicht leicht zu erreichen.

Vergleichen Sie die Vorlagen zur Berechnung von x n definiert durch x n = f(n, x n-1 ) aus x base :

function recursive(n)
    if n == base
        return xbase
    else
        return f(n, recursive(n-1))
function iterative(n)
    x = xbase
    for i = base+1 to n
        x = f(i, x)
    return x

Bei der imperativen Sprache besteht der Overhead darin, die Funktion zu definieren, bei der funktionalen Sprache besteht der Overhead darin, die Akkumulatorvariable x zu definieren.

Zum Beispiel kann eine Fakultätsfunktion iterativ in C implementiert werden, indem einer Schleifenindexvariablen und einer Akkumulatorvariablen zugewiesen wird, anstatt Argumente zu übergeben und Werte durch Rekursion zurückzugeben:

unsigned int factorial(unsigned int n) {
  unsigned int product = 1; // empty product is 1
  while (n) {
    product *= n;
    --n;
  }
  return product;
}

Ausdruckskraft

Die meisten heute verwendeten Programmiersprachen erlauben die direkte Spezifikation rekursiver Funktionen und Prozeduren. Wenn eine solche Funktion aufgerufen wird, verfolgt die Laufzeitumgebung des Programms die verschiedenen Instanzen der Funktion (oft unter Verwendung einer Aufrufliste , obwohl andere Methoden verwendet werden können). Jede rekursive Funktion kann durch das Ersetzen rekursive Aufrufe mit in eine iterative Funktion umgewandelt werden iterative Steuerkonstrukte und Simulieren des Call - Stack mit einem Stapel explizit verwaltet durch das Programm.

Umgekehrt können alle iterativen Funktionen und Prozeduren, die von einem Computer ausgewertet werden können (siehe Turing-Vollständigkeit ), in Form von rekursiven Funktionen ausgedrückt werden; iterative Kontrollkonstrukte wie while - und for - Schleifen werden in funktionalen Sprachen routinemäßig in rekursiver Form umgeschrieben . In der Praxis hängt diese Umschreibung jedoch von der Beseitigung von Rückrufen ab , die nicht in allen Sprachen vorhanden ist. C , Java und Python sind bemerkenswerte Mainstream-Sprachen, in denen alle Funktionsaufrufe, einschließlich Tail-Aufrufe , eine Stapelzuweisung verursachen können, die bei Verwendung von Schleifenkonstrukten nicht auftreten würde; in diesen Sprachen kann ein in rekursiver Form umgeschriebenes, iteratives Arbeitsprogramm den Aufrufstapel überlaufen , obwohl die Beseitigung von Rückrufen ein Merkmal sein kann, das nicht durch die Spezifikation einer Sprache abgedeckt wird, und verschiedene Implementierungen derselben Sprache können sich in den Fähigkeiten zur Beseitigung von Rückrufen unterscheiden.

Performance-Probleme

In Sprachen (wie C und Java ), die iterative Schleifenkonstrukte bevorzugen, sind rekursive Programme in der Regel mit erheblichen Zeit- und Platzkosten verbunden, aufgrund des Overheads, der für die Verwaltung des Stapels erforderlich ist, und der relativen Langsamkeit von Funktionsaufrufen; In funktionalen Sprachen ist ein Funktionsaufruf (insbesondere ein Endaufruf ) normalerweise eine sehr schnelle Operation, und der Unterschied ist normalerweise weniger auffällig.

Als konkretes Beispiel hängt der Leistungsunterschied zwischen rekursiven und iterativen Implementierungen des obigen "faktoriellen" Beispiels stark vom verwendeten Compiler ab . In Sprachen, in denen Schleifenkonstrukte bevorzugt werden, kann die iterative Version um mehrere Größenordnungen schneller sein als die rekursive. In funktionalen Sprachen kann die Gesamtzeitdifferenz der beiden Implementierungen vernachlässigbar sein; Tatsächlich können die Kosten für die Multiplikation der größeren Zahlen zuerst anstelle der kleineren Zahlen (was die hier angegebene iterative Version zufällig tut) jede Zeit, die durch die Wahl der Iteration gespart wird, überfordern.

Stapelplatz

In einigen Programmiersprachen ist die maximale Größe des Aufrufstapels viel kleiner als der im Heap verfügbare Speicherplatz , und rekursive Algorithmen benötigen tendenziell mehr Stapelspeicherplatz als iterative Algorithmen. Folglich begrenzen diese Sprachen manchmal die Rekursionstiefe, um Stapelüberläufe zu vermeiden ; Python ist eine solche Sprache. Beachten Sie den unten stehenden Vorbehalt bezüglich des Sonderfalls der Tail-Rekursion .

Verletzlichkeit

Da rekursive Algorithmen Stack-Überläufen unterliegen können, sind sie möglicherweise anfällig für pathologische oder böswillige Eingaben. Einige Malware zielt speziell auf den Aufrufstapel eines Programms ab und nutzt die inhärent rekursive Natur des Stapels. Auch in Abwesenheit von Malware, ein Stapelüberlauf durch unbeschränkte Rekursion verursacht wird, kann auf das Programm tödlich sein, und die Ausnahmebehandlung Logik den entsprechenden nicht verhindern kann Prozess vor einem beendet .

Rekursive Probleme multiplizieren

Multiplikationsrekursive Probleme sind von Natur aus rekursiv, da sie den vorherigen Zustand verfolgen müssen. Ein Beispiel ist die Baumdurchquerung wie bei der Tiefensuche ; obwohl sowohl rekursive als auch iterative Verfahren verwendet werden, stehen sie im Gegensatz zur Listendurchquerung und linearen Suche in einer Liste, die ein einfach rekursives und somit natürlich iteratives Verfahren ist. Andere Beispiele sind Divide-and-Conquer-Algorithmen wie Quicksort und Funktionen wie die Ackermann-Funktion . All diese Algorithmen können mit Hilfe eines expliziten Stapels iterativ implementiert werden , aber der Programmieraufwand für die Verwaltung des Stapels und die Komplexität des resultierenden Programms überwiegen wohl alle Vorteile der iterativen Lösung.

Refactoring-Rekursion

Rekursive Algorithmen können durch nicht-rekursive Gegenstücke ersetzt werden. Eine Methode zum Ersetzen rekursiver Algorithmen besteht darin, sie unter Verwendung von Heap-Speicher anstelle von Stapelspeicher zu simulieren . Eine Alternative besteht darin, einen Ersetzungsalgorithmus zu entwickeln, der vollständig auf nicht-rekursiven Methoden basiert, was eine Herausforderung darstellen kann. Rekursive Algorithmen zum Abgleichen von Wildcards , wie der Wildmat- Algorithmus von Rich Salz , waren beispielsweise früher typisch. Nicht-rekursive Algorithmen für den gleichen Zweck, wie der Krauss Matching Wildcards Algorithmus , wurden entwickelt, um die Nachteile der Rekursion zu vermeiden, und wurden nur allmählich basierend auf Techniken wie dem Sammeln von Tests und der Profilerstellung verbessert.

Tail-rekursive Funktionen

Tail-rekursive Funktionen sind Funktionen , in denen alle rekursiven Aufrufe sind Endrekursion und daher bauen keine latenten Operationen auf. Die Funktion gcd (wie unten noch einmal gezeigt) ist beispielsweise tail-rekursiv. Im Gegensatz dazu ist die Fakultätsfunktion (ebenfalls unten) nicht tail-rekursiv; da sich sein rekursiver Aufruf nicht in der Endposition befindet, baut er verzögerte Multiplikationsoperationen auf, die ausgeführt werden müssen, nachdem der letzte rekursive Aufruf abgeschlossen ist. Bei einem Compiler oder Interpreter , der endrekursive Aufrufe als Sprünge und nicht als Funktionsaufrufe behandelt, wird eine endrekursive Funktion wie gcd mit konstantem Leerzeichen ausgeführt. Somit ist das Programm im Wesentlichen iterativ, was der Verwendung zwingender Sprachkontrollstrukturen wie der "for"- und "while"-Schleife entspricht.

Schwanzrekursion : Erweiternde Rekursion:
//INPUT: Integers x, y such that x >= y and y >= 0
int gcd(int x, int y)
{
  if (y == 0)
     return x;
  else
     return gcd(y, x % y);
}
//INPUT: n is an Integer such that n >= 0
int fact(int n)
{
   if (n == 0)
      return 1;
   else
      return n * fact(n - 1);
}

Die Bedeutung der Endrekursion ist , dass , wenn ein Schwanz-rekursive Aufruf (oder jede Endrekursion) machen, die Rückkehrposition des Anrufers muss nicht auf den gespeichert wird Call - Stack ; wenn der rekursive Aufruf zurückkehrt, wird direkt auf die zuvor gespeicherte Rückkehrposition verzweigt. Daher spart die Tail-Rekursion in Sprachen, die diese Eigenschaft von Tail-Calls erkennen, sowohl Platz als auch Zeit.

Ausführungsreihenfolge

Betrachten Sie diese beiden Funktionen:

Funktion 1

void recursiveFunction(int num) {
    printf("%d\n", num);
    if (num < 4)
        recursiveFunction(num + 1);
}

Rekursive1.svg

Funktion 2

void recursiveFunction(int num) {
    if (num < 4)
        recursiveFunction(num + 1);
    printf("%d\n", num);
}

Rekursive2.svg

Funktion 2 ist Funktion 1 mit vertauschten Zeilen.

Wenn sich eine Funktion nur einmal selbst aufruft, werden Anweisungen, die vor dem rekursiven Aufruf platziert wurden, einmal pro Rekursion vor allen Anweisungen ausgeführt, die nach dem rekursiven Aufruf platziert wurden. Letztere werden nach Erreichen der maximalen Rekursion wiederholt ausgeführt.

Beachten Sie auch, dass die Reihenfolge der print-Anweisungen umgekehrt ist, was darauf zurückzuführen ist, wie die Funktionen und Anweisungen in der Aufrufliste gespeichert sind .

Rekursive Verfahren

Fakultät

Ein klassisches Beispiel für ein rekursives Verfahren ist die Funktion zur Berechnung der Fakultät einer natürlichen Zahl :

Pseudocode (rekursiv):
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ]
end factorial

Die Funktion kann auch als Rekursionsrelation geschrieben werden :

Diese Auswertung der Rekursionsbeziehung demonstriert die Berechnung, die bei der Auswertung des obigen Pseudocodes durchgeführt würde:

Berechnung der Rekursionsbeziehung für n = 4:
b4           = 4 × b3
             = 4 × (3 × b2)
             = 4 × (3 × (2 × b1))
             = 4 × (3 × (2 × (1 × b0)))
             = 4 × (3 × (2 × (1 × 1)))
             = 4 × (3 × (2 × 1))
             = 4 × (3 × 2)
             = 4 × 6
             = 24

Diese Fakultätsfunktion kann auch ohne Rekursion beschrieben werden, indem die typischen Schleifenkonstrukte in imperativen Programmiersprachen verwendet werden:

Pseudocode (iterativ):
function factorial is:
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
1. create new variable called running_total with a value of 1
2. begin loop 1. if n is 0, exit loop 2. set running_total to (running_total × n) 3. decrement n 4. repeat loop
3. return running_total
end factorial

Der obige Imperativcode entspricht dieser mathematischen Definition unter Verwendung einer Akkumulatorvariablen t :

Die obige Definition lässt sich direkt in funktionale Programmiersprachen wie Scheme übersetzen ; Dies ist ein Beispiel für eine rekursiv implementierte Iteration.

Größter gemeinsamer Teiler

Der euklidische Algorithmus , der den größten gemeinsamen Teiler von zwei ganzen Zahlen berechnet , kann rekursiv geschrieben werden.

Funktionsdefinition :

Pseudocode (rekursiv):
function gcd is:
input: integer x, integer y such that x > 0 and y >= 0

1. if y is 0, return x 2. otherwise, return [ gcd( y, (remainder of x/y) ) ]
end gcd

Rekursionsrelation für den größten gemeinsamen Teiler, wobei der Rest von ausdrückt :

wenn
Berechnung der Rekursionsbeziehung für x = 27 und y = 9:
gcd(27, 9)   = gcd(9, 27 % 9)
             = gcd(9, 0)
             = 9
Berechnung der Rekursionsbeziehung für x = 111 und y = 259:
gcd(111, 259)   = gcd(259, 111 % 259)
                = gcd(259, 111)
                = gcd(111, 259 % 111)
                = gcd(111, 37)
                = gcd(37, 111 % 37)
                = gcd(37, 0)
                = 37

Das obige rekursive Programm ist tail-rekursiv ; es entspricht einem iterativen Algorithmus, und die oben gezeigte Berechnung zeigt die Bewertungsschritte, die von einer Sprache durchgeführt würden, die Tail Calls eliminiert. Unten ist eine Version des gleichen Algorithmus mit expliziter Iteration, geeignet für eine Sprache, die Tail Calls nicht eliminiert. Indem es seinen Zustand vollständig in den Variablen x und y beibehält und ein Schleifenkonstrukt verwendet, vermeidet das Programm rekursive Aufrufe und das Vergrößern des Aufrufstapels.

Pseudocode (iterativ):
function gcd is:
input: integer x, integer y such that x >= y and y >= 0
1. create new variable called remainder
2. begin loop 1. if y is zero, exit loop 2. set remainder to the remainder of x/y 3. set x to y 4. set y to remainder 5. repeat loop
3. return x
end gcd

Der iterative Algorithmus erfordert eine temporäre Variable, und selbst bei Kenntnis des euklidischen Algorithmus ist es schwieriger, den Prozess durch einfache Inspektion zu verstehen, obwohl die beiden Algorithmen in ihren Schritten sehr ähnlich sind.

Türme von Hanoi

Türme von Hanoi

Die Türme von Hanoi ist ein mathematisches Rätsel, dessen Lösung die Rekursion veranschaulicht. Es gibt drei Stifte, die Stapel von Scheiben mit unterschiedlichen Durchmessern aufnehmen können. Eine größere Platte darf niemals auf eine kleinere gestapelt werden. Beginnend mit n Platten auf einem Peg müssen sie nacheinander auf einen anderen Peg verschoben werden. Was ist die kleinste Anzahl von Schritten, um den Stapel zu bewegen?

Funktionsdefinition :

Wiederholungsbeziehung für Hanoi :

Berechnung der Rekursionsbeziehung für n = 4:
hanoi(4)     = 2×hanoi(3) + 1
             = 2×(2×hanoi(2) + 1) + 1
             = 2×(2×(2×hanoi(1) + 1) + 1) + 1
             = 2×(2×(2×1 + 1) + 1) + 1
             = 2×(2×(3) + 1) + 1
             = 2×(7) + 1
             = 15


Beispielimplementierungen:

Pseudocode (rekursiv):
function hanoi is:
input: integer n, such that n >= 1
1. if n is 1 then return 1
2. return [2 * [call hanoi(n-1)] + 1]
end hanoi

Obwohl nicht alle rekursiven Funktionen eine explizite Lösung haben, kann die Tower of Hanoi-Folge auf eine explizite Formel reduziert werden.

Eine explizite Formel für Towers of Hanoi:
h1 = 1   = 21 - 1
h2 = 3   = 22 - 1
h3 = 7   = 23 - 1
h4 = 15  = 24 - 1
h5 = 31  = 25 - 1
h6 = 63  = 26 - 1
h7 = 127 = 27 - 1
In general:
hn = 2n - 1, for all n >= 1

Binäre Suche

Der binäre Suchalgorithmus ist eine Methode zum Durchsuchen eines sortierten Arrays nach einem einzelnen Element, indem das Array bei jedem rekursiven Durchlauf halbiert wird. Der Trick besteht darin, einen Mittelpunkt in der Nähe der Mitte des Arrays auszuwählen, die Daten an diesem Punkt mit den gesuchten Daten zu vergleichen und dann auf eine von drei möglichen Bedingungen zu reagieren: Die Daten werden in der Mitte gefunden, die Daten in der Mitte sind größer als die gesuchten Daten, oder die Daten am Mittelpunkt sind kleiner als die gesuchten Daten.

In diesem Algorithmus wird Rekursion verwendet, da bei jedem Durchlauf ein neues Array erstellt wird, indem das alte halbiert wird. Die binäre Suchprozedur wird dann rekursiv aufgerufen, diesmal auf dem neuen (und kleineren) Array. Normalerweise wird die Größe des Arrays durch Manipulation eines Anfangs- und Endindex angepasst. Der Algorithmus weist eine logarithmische Wachstumsordnung auf, da er im Wesentlichen den Problembereich bei jedem Durchlauf in zwei Hälften teilt.

Beispielimplementierung der binären Suche in C:

 /*
  Call binary_search with proper initial conditions.

  INPUT:
    data is an array of integers SORTED in ASCENDING order,
    toFind is the integer to search for,
    count is the total number of elements in the array

  OUTPUT:
    result of binary_search

 */
 int search(int *data, int toFind, int count)
 {
    //  Start = 0 (beginning index)
    //  End = count - 1 (top index)
    return binary_search(data, toFind, 0, count-1);
 }

 /*
   Binary Search Algorithm.

   INPUT:
        data is a array of integers SORTED in ASCENDING order,
        toFind is the integer to search for,
        start is the minimum array index,
        end is the maximum array index
   OUTPUT:
        position of the integer toFind within array data,
        -1 if not found
 */
 int binary_search(int *data, int toFind, int start, int end)
 {
    //Get the midpoint.
    int mid = start + (end - start)/2;   //Integer division


    if (start > end)                     //Stop condition (base case)
       return -1;
    else if (data[mid] == toFind)        //Found, return index
       return mid;
    else if (data[mid] > toFind)         //Data is greater than toFind, search lower half
       return binary_search(data, toFind, start, mid-1);
    else                                 //Data is less than toFind, search upper half
       return binary_search(data, toFind, mid+1, end);
 }

Rekursive Datenstrukturen (strukturelle Rekursion)

Eine wichtige Anwendung der Rekursion in der Informatik ist die Definition dynamischer Datenstrukturen wie Listen und Bäume . Rekursive Datenstrukturen können als Reaktion auf Laufzeitanforderungen dynamisch auf eine theoretisch unendliche Größe anwachsen; Im Gegensatz dazu muss die Größe eines statischen Arrays zur Kompilierzeit festgelegt werden.

„Rekursive Algorithmen bieten sich besonders an, wenn das zugrunde liegende Problem oder die zu behandelnden Daten rekursiv definiert sind.“

Die Beispiele in diesem Abschnitt veranschaulichen die sogenannte "strukturelle Rekursion". Dieser Begriff bezieht sich auf die Tatsache, dass die rekursiven Prozeduren auf rekursiv definierte Daten wirken.

Solange ein Programmierer die Vorlage aus einer Datendefinition ableitet, verwenden Funktionen strukturelle Rekursion. Das heißt, die Rekursionen im Körper einer Funktion verbrauchen einen unmittelbaren Teil eines gegebenen zusammengesetzten Werts.

Verlinkte Listen

Unten ist eine C-Definition einer verknüpften Listenknotenstruktur. Beachten Sie insbesondere, wie der Knoten in Bezug auf sich selbst definiert ist. Das "nächste" Element von struct node ist ein Zeiger auf einen anderen struct node , wodurch effektiv ein Listentyp erzeugt wird.

struct node
{
  int data;           // some integer data
  struct node *next;  // pointer to another struct node
};

Weil die struct Knotendatenstruktur rekursiv definiert ist, Verfahren , die auf ihn arbeiten kann natürlich als rekursiver Prozeduren implementiert werden. Die unten definierte list_print- Prozedur durchläuft die Liste, bis die Liste leer ist (dh der Listenzeiger hat den Wert NULL). Für jeden Knoten gibt es das Datenelement (eine ganze Zahl) aus. In der C-Implementierung bleibt die Liste durch die list_print- Prozedur unverändert .

void list_print(struct node *list)
{
    if (list != NULL)               // base case
    {
       printf ("%d ", list->data);  // print integer data followed by a space
       list_print (list->next);     // recursive call on the next node
    }
}

Binäre Bäume

Unten ist eine einfache Definition für einen Binärbaumknoten. Wie der Knoten für verkettete Listen wird er rekursiv in sich selbst definiert. Es gibt zwei selbstreferenzielle Zeiger: links (zeigt auf den linken Teilbaum) und rechts (zeigt auf den rechten Teilbaum).

struct node
{
  int data;            // some integer data
  struct node *left;   // pointer to the left subtree
  struct node *right;  // point to the right subtree
};

Operationen auf dem Baum können unter Verwendung von Rekursion implementiert werden. Beachten Sie, dass Baumoperationen möglicherweise zwei rekursive Aufrufe erfordern, da es zwei selbstreferenzierende Zeiger (links und rechts) gibt:

// Test if tree_node contains i; return 1 if so, 0 if not.
int tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return 0;  // base case
    else if (tree_node->data == i)
        return 1;
    else
        return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i);
}

Höchstens zwei rekursive Aufrufe werden für jeden gegebenen Aufruf von tree_contains wie oben definiert durchgeführt.

// Inorder traversal:
void tree_print(struct node *tree_node) {
    if (tree_node != NULL) {              // base case
        tree_print(tree_node->left);      // go left
        printf("%d ", tree_node->data);   // print the integer followed by a space
        tree_print(tree_node->right);     // go right
    }
}

Das obige Beispiel veranschaulicht eine Durchquerung des Binärbaums in der richtigen Reihenfolge . Ein binärer Suchbaum ist ein Sonderfall des binären Baums, bei dem die Datenelemente jedes Knotens geordnet sind.

Dateisystem-Traversierung

Da die Anzahl der Dateien in einem Dateisystem variieren kann, ist Rekursion die einzige praktische Möglichkeit, seinen Inhalt zu durchqueren und somit aufzuzählen. Das Traversieren eines Dateisystems ist dem des Tree-Traversal sehr ähnlich , daher sind die Konzepte hinter dem Tree-Traversal auf das Traversieren eines Dateisystems anwendbar. Genauer gesagt wäre der folgende Code ein Beispiel für eine Vorbestellungsdurchquerung eines Dateisystems.

import java.io.File;

public class FileSystem {

	public static void main(String [] args) {
		traverse();
	}

	/**
	 * Obtains the filesystem roots
	 * Proceeds with the recursive filesystem traversal
	 */
	private static void traverse() {
		File[] fs = File.listRoots();
		for (int i = 0; i < fs.length; i++) {
			System.out.println(fs[i]);
			if (fs[i].isDirectory() && fs[i].canRead()) {
				rtraverse(fs[i]);
			}
		}
	}

	/**
	 * Recursively traverse a given directory
	 *
	 * @param fd indicates the starting point of traversal
	 */
	private static void rtraverse(File fd) {
		File[] fss = fd.listFiles();

		for (int i = 0; i < fss.length; i++) {
			System.out.println(fss[i]);
			if (fss[i].isDirectory() && fss[i].canRead()) {
				rtraverse(fss[i]);
			}
		}
	}

}

Dieser Code ist sowohl Rekursion als auch Iteration - die Dateien und Verzeichnisse werden iteriert und jedes Verzeichnis wird rekursiv geöffnet.

Die Methode "rtraverse" ist ein Beispiel für eine direkte Rekursion, während die Methode "traverse" eine Wrapper-Funktion ist.

Das "Basisfall"-Szenario ist, dass es immer eine feste Anzahl von Dateien und/oder Verzeichnissen in einem gegebenen Dateisystem gibt.

Zeiteffizienz rekursiver Algorithmen

Die Zeiteffizienz rekursiver Algorithmen kann in einer Rekursionsbeziehung der Big-O-Notation ausgedrückt werden . Sie können (normalerweise) dann zu einem einzigen Big-O-Term vereinfacht werden.

Verknüpfungsregel (Mastertheorem)

Ist die Zeitkomplexität der Funktion in der Form

Dann ist das Big O der Zeitkomplexität:

  • Wenn für eine Konstante , dann
  • Wenn , dann
  • Wenn für eine Konstante und wenn für eine Konstante c < 1 und alle ausreichend groß n sind , dann

wobei a die Anzahl der rekursiven Aufrufe auf jeder Rekursionsebene darstellt, b repräsentiert, um welchen Faktor kleiner die Eingabe für die nächste Rekursionsebene ist (dh die Anzahl der Teile, in die Sie das Problem aufteilen), und f  ( n ) repräsentiert die Arbeit die Funktion funktioniert unabhängig von jeglicher Rekursion (zB Partitionierung, Rekombination) auf jeder Rekursionsebene.

Siehe auch

Anmerkungen

Verweise