Lektion 1.2

Rekursion und Rekurrenzgleichungen

40 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • die Laufzeit eines rekursiven Algorithmus als Rekurrenzgleichung aufschreiben,

  • eine Rekurrenz durch Abwickeln und mit einem Rekursionsbaum lösen,

  • eine vermutete Lösung mit der Substitutionsmethode durch vollständige Induktion beweisen,

  • begründen, warum die naive Fibonacci-Rekursion exponentiell viele Aufrufe macht,

  • die Schranken OO, Ω\Omega und Θ\Theta auseinanderhalten.

Vorausgesetzt: Laufzeit messen: Operationen zählen und O-Notation

In der letzten Lektion hast du Laufzeiten bestimmt, indem du Schleifendurchläufe gezählt und mit Summen addiert hast. Viele wichtige Algorithmen haben aber keine Schleife, an der man die Arbeit ablesen kann. Sie lösen ein Problem, indem sie sich selbst für ein kleineres Teilproblem aufrufen. Mergesort, Quicksort und die binäre Suche arbeiten so.

Nimm die binäre Suche in einem sortierten Feld mit einer Million Einträgen. Sie schaut den mittleren Eintrag an und sucht dann nur noch in der linken oder in der rechten Hälfte weiter, mit demselben Verfahren. Wie viele Einträge sieht sie sich schlimmstenfalls an? Im Programmtext steht diese Zahl nirgends. Sie steckt in der Frage, wie oft sich die Funktion selbst aufruft.

Die Antwort dieser Lektion: Man schreibt die Laufzeit als Funktion T(n)T(n) der Eingabegröße nn und drückt T(n)T(n) durch Werte von TT an kleineren Stellen aus. So entsteht eine Rekurrenzgleichung, und für solche Gleichungen gibt es Lösungsverfahren.

Vermute zuerst

Die binäre Suche halbiert bei jedem Schritt den Bereich, in dem sie noch sucht. Wie viele Einträge eines sortierten Feldes mit 1 000 0001\,000\,000 Einträgen sieht sie schlimmstenfalls an?

Definition

Rekursiver Algorithmus

Ein Algorithmus heißt rekursiv, wenn er sich selbst für eine kleinere Eingabe aufruft. Er besteht aus zwei Teilen:

  • Basisfall (Rekursionsanfang): kleine Eingaben, die direkt gelöst werden, ohne Selbstaufruf.
  • Rekursionsfall: Die Eingabe wird auf eine oder mehrere kleinere Eingaben zurückgeführt, für die sich der Algorithmus selbst aufruft.

Damit die Rekursion endet, muss jeder Selbstaufruf näher an den Basisfall heranführen, zum Beispiel weil nn kleiner wird. Das einfachste Beispiel ist die Fakultät n!=1⋅2⋯nn! = 1 \cdot 2 \cdots n mit 0!=10! = 1, denn es gilt n!=n⋅(n−1)!n! = n \cdot (n-1)!:

ZeileEinrückungAnweisung
10fak(n):\texttt{fak(n):}
21wenn n <= 1: gib 1 zuru¨ck\texttt{wenn n <= 1: gib 1 zurück}
31gib n * fak(n - 1) zuru¨ck\texttt{gib n * fak(n - 1) zurück}

Der Aufruf fak(4)\texttt{fak(4)} ruft fak(3)\texttt{fak(3)} auf, dieser fak(2)\texttt{fak(2)} und dieser fak(1)\texttt{fak(1)}, den Basisfall. Dann werden die Ergebnisse rückwärts multipliziert: 11, 2⋅1=22 \cdot 1 = 2, 3⋅2=63 \cdot 2 = 6, 4⋅6=244 \cdot 6 = 24.

Kein rekursiver Algorithmus in diesem Sinn ist eine Funktion g(n)\texttt{g(n)}, die ohne Basisfall g(n - 1)\texttt{g(n - 1)} aufruft. Sie endet nie, weil nn immer weiter fällt, auch unter 00.

Beispiel

Von der Funktion zur Rekurrenz: Fakultät

Sei T(n)T(n) die Zahl der Grundoperationen, die fak(n)\texttt{fak(n)} für n≥1n \ge 1 ausführt. Im Basisfall sind es konstant viele, sagen wir c0c_0 (ein Vergleich, eine Rückgabe). Im Rekursionsfall sind es ebenfalls konstant viele, sagen wir cc (Vergleich, Subtraktion, Multiplikation, Rückgabe), und dazu kommen die Kosten des Aufrufs fak(n - 1)\texttt{fak(n - 1)}. Die sind nach Definition T(n−1)T(n-1):

T(1)=c0,T(n)=T(n−1)+cfu¨r n≥2T(1) = c_0, \qquad T(n) = T(n-1) + c \quad \text{für } n \ge 2

Das ist eine Rekurrenzgleichung, kurz Rekurrenz: Sie legt T(n)T(n) durch Werte an kleineren Stellen fest, und der Anfangswert T(1)T(1) macht die Folge eindeutig. Gesucht ist eine geschlossene Form, also ein Term in nn, in dem TT nicht mehr vorkommt. Hier kostet jedes Absteigen von nn nach n−1n - 1 genau cc, und es gibt n−1n - 1 solche Schritte bis T(1)T(1). Also ist T(n)=c0+(n−1) cT(n) = c_0 + (n-1)\,c: Die Fakultät braucht lineare Zeit.

Definition

Untere und genaue Schranken: Ω\Omega und Θ\Theta

f∈O(g)f \in O(g) sagt nur, dass ff höchstens so schnell wächst wie gg. Auch c0+(n−1) cc_0 + (n-1)\,c liegt in O(n2)O(n^2). Das ist wahr, aber zu grob. Für genaue Aussagen gibt es zwei weitere Zeichen. Seien ff und gg wie bisher Funktionen von den natürlichen Zahlen in die nichtnegativen reellen Zahlen.

  • f∈Ω(g)f \in \Omega(g) (gesprochen „Omega von gg“), wenn es c>0c > 0 und n0n_0 gibt mit f(n)≥c⋅g(n)f(n) \ge c \cdot g(n) für alle n≥n0n \ge n_0. Das ist eine untere Schranke.
  • f∈Θ(g)f \in \Theta(g) (gesprochen „Theta von gg“), wenn f∈O(g)f \in O(g) und f∈Ω(g)f \in \Omega(g) gilt. Dann wachsen ff und gg bis auf konstante Faktoren gleich schnell.

Beispiel: n(n−1)2∈Θ(n2)\frac{n(n-1)}{2} \in \Theta(n^2), denn für n≥2n \ge 2 ist n24≤n(n−1)2≤n22\frac{n^2}{4} \le \frac{n(n-1)}{2} \le \frac{n^2}{2}. Die Fakultät braucht Θ(n)\Theta(n) Schritte, wenn cc und c0c_0 positiv sind. Gegenbeispiel: n∈O(n2)n \in O(n^2), aber n∉Ω(n2)n \notin \Omega(n^2), denn n≥c n2n \ge c\,n^2 hieße n≤1cn \le \frac 1c, und das gilt nicht für alle großen nn.

f∈Θ(g)  :⟺  ∃ c1,c2>0, n0: ∀n≥n0: c1 g(n)≤f(n)≤c2 g(n)f \in \Theta(g) \;:\Longleftrightarrow\; \exists\, c_1, c_2 > 0,\ n_0:\ \forall n \ge n_0:\ c_1\, g(n) \le f(n) \le c_2\, g(n)
Beispiel

Binäre Suche: Rekurrenz aufstellen und abwickeln

Das Feld A\texttt{A} ist aufsteigend sortiert. Gesucht ist der Wert x\texttt{x} zwischen den Stellen l\texttt{l} und r\texttt{r}. floor\texttt{floor} rundet ab; in Formeln schreiben wir dafür ⌊⋅⌋\lfloor \cdot \rfloor und für das Aufrunden ⌈⋅⌉\lceil \cdot \rceil.

ZeileEinrückungAnweisung
10suche(A, x, l, r):\texttt{suche(A, x, l, r):}
21wenn l > r: gib -1 zuru¨ck\texttt{wenn l > r: gib -1 zurück}
31m = floor((l + r) / 2)\texttt{m = floor((l + r) / 2)}
41wenn A[m] = x: gib m zuru¨ck\texttt{wenn A[m] = x: gib m zurück}
51wenn A[m] < x: gib suche(A, x, m + 1, r) zuru¨ck\texttt{wenn A[m] < x: gib suche(A, x, m + 1, r) zurück}
61gib suche(A, x, l, m - 1) zuru¨ck\texttt{gib suche(A, x, l, m - 1) zurück}

Der Bereich hat n=r−l+1n = r - l + 1 Einträge. Ohne den mittleren bleiben n−1n - 1, links ⌊(n−1)/2⌋\lfloor (n-1)/2 \rfloor und rechts ⌈(n−1)/2⌉=⌊n/2⌋\lceil (n-1)/2 \rceil = \lfloor n/2 \rfloor. Im schlechtesten Fall geht es im größeren Teil weiter. Sei T(n)T(n) die Zahl der angesehenen Einträge (Zeile 4) im schlechtesten Fall:

T(0)=0,T(n)=T(⌊n/2⌋)+1fu¨r n≥1T(0) = 0, \qquad T(n) = T\bigl(\lfloor n/2 \rfloor\bigr) + 1 \quad \text{für } n \ge 1

Abwickeln heißt: die Gleichung immer wieder in sich selbst einsetzen, bis ein Muster sichtbar wird. Für n=2kn = 2^k ist ⌊n/2⌋=n/2\lfloor n/2 \rfloor = n/2, und es folgt

T(n)=T(n/2)+1=T(n/4)+2=T(n/8)+3=⋯=T(n/2j)+j.T(n) = T(n/2) + 1 = T(n/4) + 2 = T(n/8) + 3 = \dots = T(n/2^j) + j.

Bei j=kj = k ist n/2k=1n/2^k = 1, und T(1)=T(0)+1=1T(1) = T(0) + 1 = 1. Also ist T(n)=k+1=log⁡n+1T(n) = k + 1 = \log n + 1. Für jedes n≥1n \ge 1 gilt genau T(n)=⌊log⁡n⌋+1T(n) = \lfloor \log n \rfloor + 1; den Beweis führst du in den Übungen. Für n=106n = 10^6 sind das ⌊19,93⌋+1=20\lfloor 19{,}93 \rfloor + 1 = 20 Einträge, und die binäre Suche liegt in Θ(log⁡n)\Theta(\log n).

Abwickeln liefert eine Vermutung. Ein Beweis ist es erst, wenn man das Muster, hier das „…\dots“, mit Induktion absichert.

Kurz geprüft

Löse durch Abwickeln: T(1)=2T(1) = 2 und T(n)=T(n−1)+3T(n) = T(n-1) + 3 für n≥2n \ge 2. Wie groß ist T(10)T(10)?

Definition

Rekursionsbaum

Mergesort (ausführlich im Kapitel über Sortieralgorithmen) sortiert ein Feld, indem es das Feld in zwei Hälften teilt, jede Hälfte rekursiv sortiert und die beiden sortierten Hälften in linearer Zeit zu einer sortierten Folge mischt. Rechnen wir das Mischen von nn Werten mit Kosten nn und ein Feld der Länge 11 mit Kosten 11, so erhalten wir für Zweierpotenzen nn die Rekurrenz T(1)=1T(1) = 1 und T(n)=2 T(n/2)+nT(n) = 2\,T(n/2) + n.

Hier gibt es zwei Selbstaufrufe, das Abwickeln wird unübersichtlich. Ein Rekursionsbaum ordnet die Arbeit: Jeder Aufruf ist ein Knoten, seine Kinder sind die Aufrufe, die er selbst startet. An jeden Knoten schreibt man die Kosten, die der Aufruf selbst verursacht, ohne die seiner Kinder. Die Summe über alle Knoten ist T(n)T(n). Man summiert ebenenweise: Ebene 00 ist der erste Aufruf, Ebene 11 sind seine Kinder, und so weiter.

Für n=8n = 8:

Ebene iiKnotenGröße je KnotenKosten je KnotenKosten der Ebene
0011888888
1122444488
2244222288
338811T(1)=1T(1) = 188

Zusammen T(8)=32T(8) = 32. Allgemein hat Ebene ii genau 2i2^i Knoten der Größe n/2in/2^i und kostet 2i⋅n2i=n2^i \cdot \frac{n}{2^i} = n. Die Ebenen 00 bis log⁡n−1\log n - 1 kosten je nn, die letzte Ebene log⁡n\log n besteht aus nn Blättern mit Kosten 11. Vermutung: T(n)=nlog⁡n+nT(n) = n \log n + n.

Kurz geprüft

Wie groß ist T(16)T(16) für T(1)=1T(1) = 1 und T(n)=2 T(n/2)+nT(n) = 2\,T(n/2) + n? Zähle die Ebenen des Rekursionsbaums.

Schritt für Schritt

Substitutionsmethode: die Vermutung beweisen

Der Baum liefert eine Vermutung, aber das Aufsummieren war Anschauung. Die Substitutionsmethode macht daraus einen Beweis: Man vermutet eine Lösung und beweist sie mit vollständiger Induktion, indem man die Vermutung für die kleineren Werte in die Rekurrenz einsetzt (substituiert). Behauptung: Für alle k≥0k \ge 0 und n=2kn = 2^k gilt T(n)=nlog⁡n+nT(n) = n \log n + n.

  1. Induktionsanfang k=0k = 0, also n=1n = 1: T(1)=1T(1) = 1 und 1⋅log⁡1+1=0+1=11 \cdot \log 1 + 1 = 0 + 1 = 1.

Schritt 1 von 4
Häufige Fehler

Induktion mit OO statt mit einer festen Konstante

Behauptung: Für T(n)=2 T(n/2)+nT(n) = 2\,T(n/2) + n gilt T(n)∈O(n)T(n) \in O(n). „Beweis“: Angenommen, T(n/2)≤c⋅n2T(n/2) \le c \cdot \frac n2. Dann ist T(n)≤2c⋅n2+n=cn+nT(n) \le 2c \cdot \frac n2 + n = cn + n, und cn+ncn + n liegt in O(n)O(n). Fertig?

Richtig ist

Nein. Der Induktionsschritt muss dieselbe Aussage T(n)≤c nT(n) \le c\,n mit derselben Konstante cc zeigen. Sonst wächst die Konstante bei jedem Halbieren um 11, und nach log⁡n\log n Halbierungen ist sie keine Konstante mehr. Die Ungleichung cn+n≤cncn + n \le cn gilt aber für kein n≥1n \ge 1. Die Behauptung ist auch falsch, die Lösung ist nlog⁡n+nn \log n + n. Schreibe in Induktionsbeweisen deshalb nie O(… )O(\dots), sondern eine Ungleichung mit einer benannten Konstante.

Mergesort Aufruf für Aufruf

Mergesort

2 bis 12 ganze Zahlen von 1 bis 99, getrennt durch Komma oder Leerzeichen. Enter übernimmt sie.

Vergleiche
0
Vertauschungen
0
Schreibzugriffe
0
  • V verglichen
  • T getauscht oder geschrieben
  • P Pivot
  • • markiert
  • Arbeitsbereich
  • am Platz
Schritt 1 von 72
Tempo
← → Schritt, Leertaste Abspielen
Die Idee

Teilen, dann Mischen

Mergesort teilt das Feld in zwei Hälften, sortiert jede Hälfte für sich und mischt die beiden sortierten Hälften dann zu einer. Die Hälften werden genauso behandelt: Die Funktion ruft sich selbst für kleinere Bereiche auf (Rekursion), bis nur noch einzelne Werte übrig sind. Ein einzelner Wert ist immer sortiert.

Pseudocoden = 8, Stellen 0 bis 7
  1. mergesort(lo, hi):
  2. wenn lo ≥ hi: zurück
  3. mitte ← ⌊(lo + hi) / 2⌋
  4. mergesort(lo, mitte)
  5. mergesort(mitte + 1, hi)
  6. kopiere A[lo..hi] nach B[lo..hi]
  7. i ← lo; j ← mitte + 1
  8. für k von lo bis hi:
  9. wenn i > mitte: A[k] ← B[j]; j ← j + 1
  10. sonst wenn j > hi: A[k] ← B[i]; i ← i + 1
  11. sonst wenn B[j] < B[i]: A[k] ← B[j]; j ← j + 1
  12. sonst: A[k] ← B[i]; i ← i + 1

Laufzeit bei n Zahlen: bester Fall Θ(nlog⁡n)\Theta(n \log n), im Mittel Θ(nlog⁡n)\Theta(n \log n), schlechtester Fall Θ(nlog⁡n)\Theta(n \log n).

Gehe Schritt für Schritt durch die Aufrufe von Mergesort. Die Zähler unter den Balken zeigen Vergleiche und Schreibzugriffe, darunter steht der Pseudocode mit der aktuellen Zeile.

Probier es aus

Beispiel

Naive Fibonacci-Rekursion

Die Fibonacci-Zahlen sind F0=0F_0 = 0, F1=1F_1 = 1 und Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} für n≥2n \ge 2, also 0,1,1,2,3,5,8,13,…0, 1, 1, 2, 3, 5, 8, 13, \dots Die Definition lässt sich wörtlich als Programm schreiben:

ZeileEinrückungAnweisung
10fib(n):\texttt{fib(n):}
21wenn n <= 1: gib n zuru¨ck\texttt{wenn n <= 1: gib n zurück}
31gib fib(n - 1) + fib(n - 2) zuru¨ck\texttt{gib fib(n - 1) + fib(n - 2) zurück}

Sei A(n)A(n) die Zahl der Aufrufe von fib\texttt{fib}, die fib(n)\texttt{fib(n)} insgesamt auslöst, sich selbst mitgezählt. Der Aufruf selbst zählt 11, dazu kommen alle Aufrufe der beiden Teilaufrufe:

A(0)=A(1)=1,A(n)=A(n−1)+A(n−2)+1fu¨r n≥2A(0) = A(1) = 1, \qquad A(n) = A(n-1) + A(n-2) + 1 \quad \text{für } n \ge 2

Die ersten Werte sind 1,1,3,5,9,15,251, 1, 3, 5, 9, 15, 25. So ruft fib(4)\texttt{fib(4)} zweimal fib(2)\texttt{fib(2)} und dreimal fib(1)\texttt{fib(1)} auf: Dieselben Teilprobleme werden immer wieder neu berechnet. Für n=30n = 30 sind es schon 2 692 5372\,692\,537 Aufrufe, für n=40n = 40 über 331331 Millionen.

Satz

Die naive Fibonacci-Rekursion braucht exponentiell viele Aufrufe

Für alle n≥0n \ge 0 gilt 2⌊n/2⌋≤A(n)≤2n2^{\lfloor n/2 \rfloor} \le A(n) \le 2^n. Weil jeder Aufruf mindestens eine Grundoperation kostet (den Vergleich in Zeile 2), liegt die Laufzeit von fib(n)\texttt{fib(n)} in Ω(2n/2)\Omega(2^{n/2}).

2⌊n/2⌋  ≤  A(n)  ≤  2n2^{\lfloor n/2 \rfloor} \;\le\; A(n) \;\le\; 2^n
Kurz geprüft

Warum ist fib\texttt{fib} so langsam, obwohl fak\texttt{fak} mit einer sehr ähnlichen Rekursion linear ist?

Zusammenfassung

  • Ein rekursiver Algorithmus hat einen Basisfall und einen Rekursionsfall, der auf kleinere Eingaben zurückführt.

  • Seine Laufzeit erfüllt eine Rekurrenz: T(n)T(n) = Summe der Kosten der Teilaufrufe plus die Arbeit des Aufrufs selbst, dazu ein Anfangswert.

  • Ω\Omega ist eine untere Schranke, Θ\Theta eine obere und untere zugleich; f∈Θ(g)f \in \Theta(g) heißt: gleiches Wachstum bis auf Konstanten.

  • Abwickeln: die Rekurrenz in sich einsetzen, bis ein Muster entsteht. Binäre Suche: T(n)=T(⌊n/2⌋)+1T(n) = T(\lfloor n/2 \rfloor) + 1 ergibt ⌊log⁡n⌋+1∈Θ(log⁡n)\lfloor \log n \rfloor + 1 \in \Theta(\log n).

  • Rekursionsbaum: Kosten ebenenweise summieren. T(n)=2T(n/2)+nT(n) = 2T(n/2) + n hat log⁡n\log n Ebenen mit je nn und nn Blätter: nlog⁡n+nn \log n + n.

  • Substitutionsmethode: Vermutung mit Induktion beweisen, immer mit derselben benannten Konstante, nie mit O(… )O(\dots) im Induktionsschritt.

  • Die naive Fibonacci-Rekursion macht mindestens 2⌊n/2⌋2^{\lfloor n/2 \rfloor} Aufrufe, weil sie dieselben Teilprobleme immer wieder löst.

Übungen

Aufgabe 1Numerisch

Wie viele Aufrufe von fak\texttt{fak} finden bei der Berechnung von fak(6)\texttt{fak(6)} statt, den ersten Aufruf mitgezählt?

Aufgabe 2Numerisch

Für die binäre Suche gilt T(0)=0T(0) = 0 und T(n)=T(⌊n/2⌋)+1T(n) = T(\lfloor n/2 \rfloor) + 1 für n≥1n \ge 1. Berechne T(1024)T(1024).

Aufgabe 3Multiple Choice

Ein Algorithmus sieht alle nn Einträge eines Feldes einmal an und ruft sich dann für das Feld ohne den letzten Eintrag auf. Also gilt T(1)=1T(1) = 1 und T(n)=T(n−1)+nT(n) = T(n-1) + n. In welcher Klasse liegt TT?

Aufgabe 4Numerisch

Wie viele Aufrufe von fib\texttt{fib} löst fib(6)\texttt{fib(6)} in der naiven Rekursion insgesamt aus, den ersten Aufruf mitgezählt?

Aufgabe 5Freitext

Für Zweierpotenzen nn sei T(1)=1T(1) = 1 und T(n)=2 T(n/2)+1T(n) = 2\,T(n/2) + 1. (So zählt man die Aufrufe von Mergesort: ein Aufruf und die Aufrufe der beiden Hälften.) Bestimme die Lösung mit einem Rekursionsbaum und beweise sie mit der Substitutionsmethode.

Aufgabe 6Freitext

Beweise: Für T(0)=0T(0) = 0 und T(n)=T(⌊n/2⌋)+1T(n) = T(\lfloor n/2 \rfloor) + 1 (n≥1)(n \ge 1) gilt T(n)=⌊log⁡n⌋+1T(n) = \lfloor \log n \rfloor + 1 für alle n≥1n \ge 1.

Aufgabe 7Freitext

Beweise für die Aufrufzahl der naiven Fibonacci-Rekursion (A(0)=A(1)=1A(0) = A(1) = 1, A(n)=A(n−1)+A(n−2)+1A(n) = A(n-1) + A(n-2) + 1) die Formel A(n)=2Fn+1−1A(n) = 2F_{n+1} - 1 für alle n≥0n \ge 0.