Grundlagen der Informatik

Rekursion für Fortgeschrittene

Nicolai Kuntze

Hochschule Mainz University of Applied Sciences

[Link]@[Link]

12. Dezember 2017

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 1 / 36

Überblick
1 Berechenbarkeit
2 LOOP
3 Primitiv Rekursiv
4 Fakultät
5 ggT
6 Türme von Hanoi
7 Problematische Rekursion
8 Fakultät
9 Nichtlineare Rekursion
10 Auflösen der Rekursion
11 Indirekte Rekursion
12 Literatur
Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 2 / 36
Berechenbarkeit

Mitte des 20. Jahrhunderts beantworteten Pioniere, wie Alan M.

Turing (1937), E. Moore (1956) und G. H. Mealy (1957), die Frage,
welche Probleme sind mit Hilfe von Algorithmen berechenbar?
Turing fand einen recht intuitiven Zugang zum Lösen einer Aufgabe,
die Turingmaschine (TM):
Man nehme ein oder mehre Blätter Papier, einen Schreibstift und ein
Radiergummi.
Jetzt kann man in endlich vielen Schritten zu jeder Stelle des
Geschriebenen gelangen, um es zu lesen, zu löschen oder auch zu
verändern, meist in Abhängigkeit zum bereits an anderer Stelle
Geschriebenen oder Gelesenem.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 3 / 36

Die Turingmaschine - Erinnerung

In Ermangelung von echten Rechnern“ abstrahierte Turing seine

”
Maschine als einen Schreib/Lesekopf, der über einem (Magnet)band
positioniert wird. Mit dem Gelesenen werden einfache primitive
Grundoperationen, wie das Hinzufügen oder Entfernen von
Symbolen/Wörtern eines Alphabets Σ durchgeführt.
Addition und Subtraktion lassen sich als Hinzufügen und Entfernen
deuten. Schleifen werden durch geeignete
Schreib/Lesekopfbewegungen realisiert.
Mit diesem Ansatz gelang es wichtige Aussagen zur Berechenbarkeit
von Funktionen zu erhalten.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 4 / 36

Turing-berechenbar

Eine TM verarbeitet Wörter“ w ∈ Σ∗ eines Alphabets.

”
Eine Funktion f : Σ∗ → Σ∗ heißt Turing-berechenbar, falls eine
Turingmaschine existiert, die f (x) in endlich vielen Schritten
berechnet und dann terminiert. D.h. alle Eingaben x ∈ Σ∗ werden
durch die TM in die Ausgabe y ∈ Σ∗ mit y = f (x) = fTM (x)
überführt.
Zur Vereinfachung wird die Turing-Berechenbarkeit auf natürliche
Zahlen N0 erweitert. Hierzu dienen die
Eingabefunktion α : N0 → {|}∗ α(n) = |n und die
Ausgabefunktion β : {|}∗ → N0 β(|n ) = n
Potenzierung: |3 = ||| (Bierdeckelnotation)

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 5 / 36

Die Bierdeckel Turingmachine

Diese Bierdeckelnotation“ arbeitet mit Strichlisten:

” 4
α(4) = | = ||||
β(|||) = 3
Auch k-stellige Eingaben lassen sich so realisieren durch Einführen des
Trennsymbols ’0’:
αk : Nk0 → {|, 0}∗ αk (n1 , n2 , . . . , nk ) = |n1 0|n2 0 . . . |nk
Beispiel: Die Operation add : N20 → N0 add(x, y ) = x + y wird mit
der Turingmaschine addTM realisiert durch Entfernen des
”
Trennsymbols“

add(2, 5) = addTM (α2 (2, 5)) = addTM (|2 0|5 )

(1)
= addTM (||0|||||) = β(|||||||) = 7

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 6 / 36

Die Sprache LOOP

LOOP ist eine einfache Programmiersprache, die nur Variablen

x0 , x1 , x2 , . . . als Bezeichner für Speicherplätze und die Konstanten
0, 1, 2, . . . als Bezeichner für natürliche Zahlen N0 kennt.
Es gibt das Zuweisungssymbol = und die Operationen + und – mit
xj = xi + c und xj = xi − c für Speicherplätze x und Konstanten c.
Durch das Symbol ; werden zwei Anweisungen A1 ;A2 getrennt. Eine
Schleife wird durch loop xj do A end gekennzeichnet, A wird xj mal
ausgeführt. Innerhalb der Schleife darf auf xj nur lesend zugegriffen
werden

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 7 / 36

LOOP Programme

Der Start eines LOOP Programms erfolgt durch die Anweisung

read(x1 ,x2 ,. . .), die Ausgabe erfolgt immer mit der Variablen x0
durch write(x0 ). read und write können z.B. durch die Funktionen
αk und β der vorhergehenden Turingmaschine realisiert werden.
LOOP Programme berechnen Funktionen f : Nk0 → N0 und haben die
feste Struktur:
read(x1 , x2 , . . .); A; write(x0 )
Die Anweisung A kann zusammengesetzt sein und weitere LOOP
Schleifen enthalten.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 8 / 36

LOOP berechenbar

Eine Funktion f : Nk0 → N0 heißt LOOP-berechenbar, wenn ein

zugehöriges LOOP Programm P existiert mit fP (x) = f (x).
Beispiel die Multiplikation mult(x, y ) = x ∗ y ist LOOP berechenbar
durch das Programm:
read(x1 ,x2 );
x0 = 0;
loop x2 do
x0 = x0 + x1 ;
end;
write(x0 )

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 9 / 36

LOOP terminiert immer

In LOOP wird die Anzahl x der Schleifendurchläufe vor dem Beginn

berechnet. Jede Schleife ist nach genau x Durchläufen beendet.
Alle LOOP Programme terminieren daher nach einer endlichen Anzahl
von Rechenschritten.
LOOP kennt kein if xp then A1 else A2 dieses lässt sich aber mit
LOOP Schleifen emulieren:
x1 = 1; x2 = 1;
loop xp do x2 = 0 end;
loop x2 do x1 = 0; A2 end;
loop x1 do A1 end;

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 10 / 36

Primitiv rekursive Funktionen

In der theoretischen Informatik wird die Klasse Pr der primitiv

rekursiven Funktionen definiert.
Pr enthält die drei Grundfunktionen
konstante Nullfunktion f k (n1 , . . . , nk ) = 0
Projektion auf ein Argument πjk (n1 , . . . , nk ) = nj
die Nachfolgefunktion ν(n) = n + 1
sowie alle primitiv rekursiven Funktionen, f , g , h ∈ Pr die sich
darstellen lassen durch die Verknüpfung
f (n1 , . . . , nk ) = g (h1 (n1 , . . . , nk ), . . . , hm (n1 , . . . , nk ))
und der Rekursion f (0, n2 , . . . , nk ) = g (n2 , . . . , nk )
f (n1 + 1, n2 , . . . , nk ) = h(f (n1 , . . . , nk ), n1 , . . . , nk )

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 11 / 36

Schema einer rekursiven Funktion

Eine Funktion f : N → N ist dann rekursiv definiert,wenn sich der

Funktionswert f (n + 1) aus den vorhergehenden Funktionswerten
f (n), f (n − 1), . . . berechnen lässt.
D.h. sind hinreichend viele Startwerte von f bekannt, so lässt sich im
Prinzip f für alle beliebigen Werte berechnen.
Eine Voraussetzung ist, dass der Bildbereich von f im Wertebereich
von f liegt. Bild- und Wertebereich müssen nicht unbedingt N sein.
Bildbereich:

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 12 / 36

Primitive Operationen

Die wesentlichen arithmetischen Operationen lassen sich durch

primitiv rekursive Funktionen darstellen.
Die konstante Funktion c(n + 1) = c(n) = π11 (c) = c
Die Addition add(p, q) = p + q mit
add(0, q) = π11 (q) = q
add(p + 1, q) = ν(add(p, q)) ≡ add(p, q) + 1
Die Multiplikation mult(p, q) = p ∗ q mit

mult(0, q) = f1 (q) = 0
mult(p + 1, q) = add(mult(p, q), q) (2)
≡ mult(p, q) + q

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 13 / 36

Beispiele rekursiver Funktionen

Pn
Die Summenfunktion s(n) = s(n − 1) + n = k=1 k
Die Fibonacci Folge fib(n + 2) = fib(n) + fib(n + 1)
Damit letztere Funktionen terminieren muss noch jeweils ein
Rekursionsanfang mit den Startwerten s(0) = 0 und fib(0) = 0,
fib(1) = 1 definiert werden.
Einfach rekursiv definierte Funktionen lassen sich immer auch als
iterative Funktionen in Form einer Schleife implementieren.
Die Menge der LOOP-berechenbaren Funktionen ist gleich der Menge
der primitiv rekursiv berechenbaren Funktionen.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 14 / 36

Fakultät als rekursive Funktion

Ein einfaches Beispiel für Rekursion ist die Fakultät. Diese ist
mathematisch sowohl iterativ als auch rekursiv definiert:
iterative
rekursiv
n! ≡ nk=1 k
Q
0! ≡ 1
n! ≡ n ∗ (n − 1)!n > 0
read(x1 ); x0 = 1; x2 = 1;
loop x1 do
x0 = x0 ∗ x2 ;
x2 = x2 + 1; fac(0) = π11 (1) = 1
end; write(x0 ) fac(n) = mult(fac(n − 1), n)

LOOP Programm Primitive Rekursion

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 15 / 36

Eine weitere Rekursion

Bei der Berechnung des größten gemeinsamen Teilers ergaben sich die
Beziehungen ggT (a, b) = ggT (b, a), sowie
ggT (a, b) = ggT (b, a − b) für a > b.
Wird diese Erkenntnis ernst genommen“, so ergibt sich eine
”
neuartige Möglichkeit den ggT rekursiv zu berechnen:

 ggT (b, a) a<b
ggT (a, b) = a (b ≡ a) ∨ (b ≡ 0)
ggT (b, a − b) a > b


Bei diesem rekursiven Ansatz wird aus der Funktion ggT die Funktion
ggT erneut aufgerufen, allerdings mit anderen, neuberechneten
Argumenten.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 16 / 36

Rekursiver ggT mit modulo

Die schnellere Modulo Variante lautet:


 ggT (b, a) a<b
ggT (a, b) = ggT (b, amodb) 0 < b < a
a a≡b∨b ≡0


D.h. die ggT Funktion ruft sich so lange selber auf, bis der Fall b==a
oder b==0 eintritt, zu implementieren ist so gut wie nichts mehr

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 17 / 36

Rekursive C Implementierung

unsigned int ggT ( unsigned int a ,

unsigned int b ) {
if ( a == b | | b == 0 ) {
return a ;
} else if ( a < b ) {
return ggT ( b , a ) ;
} else {
return ggT ( b , a%b ) ;
}
}

Der Quelltext für die C Implementierung ist kurz und enthält keinerlei
Schleifen mehr...

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 18 / 36

Türme von Hanoi

Das Spiel besteht aus drei Stäben A, B und C, auf die mehrere
gelochte Scheiben gelegt werden, alle verschieden groß. Zu Beginn
liegen alle Scheiben auf Stab A, der Größe nach geordnet, mit der
größten Scheibe unten und der kleinsten oben. Ziel des Spiels ist es,
den kompletten Scheiben-Stapel von A nach C zu versetzen.
Bei jedem Zug darf die oberste Scheibe eines beliebigen Stabes auf
einen der beiden anderen Stäbe gelegt werden, vorausgesetzt, dort
liegt nicht schon eine kleinere Scheibe. Folglich sind zu jedem
Zeitpunkt des Spieles die Scheiben auf jedem Feld der Größe nach
geordnet.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 19 / 36

Rekursive Lösung

Die Problembeschreibung spricht von drei Scheibenstapeln. Es bietet

sich daher an einen Stapelspeicher (Stack) zur Lösung zu verwenden.
Mit seiner Hilfe lassen sich die Scheiben sehr einfach per push und
pop Befehl in einer genau definierten Reihenfolge in einer rekursiven
Lösung verwalten.
Die Lösungsidee ist wie folgt: Um das Hanoiproblem für n Scheiben
und drei Stapel A, B, C zu lösen reicht es aus, das Problem für
(n − 1) Scheiben zu lösen und die letzte verbleibende Scheibe per
”
Hand“ mit einem move Befehl von A nach C zu transportieren.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 20 / 36

Hanoi rekursiv

Die Umsetzung der Lösungsidee liefert die folgende rekursive Lösung:

h a n o i ( n , A , B , C) {
if ( n>0) {
h a n o i ( n −1 , A , C , B ) ;
push (C , pop (A ) ) ;
h a n o i ( n −1 , B , A , C ) ;
}
}

n ist eine Integervariable und A, B, C sind vom Typ Stapel. Der move
Befehl wurde durch die Folge push(C, pop(A)) realisiert. Das ist Alles!

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 21 / 36

 Mittels Rekursion lassen sich Spezifikationen recht elegant und
einfach implementieren.
Leider sind jedoch die so erhaltenen Lösungen meist nicht sehr
effizient, was den Speicherverbrauch und die Laufzeit betrifft.
Da sich jede primitive Rekursion durch eine iterative Lösung mittels
Schleifen darstellen lässt, gilt es einen strukturierten Weg zu finden,
um eine rekursive Lösung in eine Iterative zu überführen.
Ein erster Schritt hierzu die Endrekursion, die eine effizientere
Implementierung gestattet.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 22 / 36

Endrekursion

Eine Rekursion heißt endrekursiv, wenn der Aufruf der Rekursion die
letzte Aktion zur Berechnung der rekursiven Funktion f ist.
Endrekursive Funktionen zeigen ein besseres Verhalten hinsichtlich
des Speicherbedarfs für lokale Variablen und den Stack, als normal
rekursive Funktionen, die nach der Rekursion noch weitere
Berechnungen vornehmen.
Am Beispiel der rekursiven Fakultätsberechnung soll das Prinzip
verdeutlicht werden.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 23 / 36

Rekursive Fakultät

int f a c t o r i a l ( int n ) {
if ( n<=1) return 1 ;
return n∗ f a c t o r i a l ( n −1);
}

Diese Implementierung der Fakultät ist nicht endrekursiv, da nach der

Rekursion noch eine Multiplikation mit dem Argument n erfolgt.
Sie ergibt sich z.B. für n = 4 die Aufruffolge 4!:
f (4) = 4 ∗ f (3) f (4) = 4 ∗ 6 = 24
f (3) = 3 ∗ f (2) f (3) = 3 ∗ 2 = 6
f (2) = 2 ∗ f (1) f (2) = 2 ∗ 1 = 2
f (1) = 1

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 24 / 36

Endrekursion mittels Hilfsfunktion

int g f a c t o r i a l ( int n , int f a c ) {

if ( n<=1) return f a c ;
return g f a c t o r i a l ( n −1, f a c ∗n ) ;
}
int f a c t o r i a l ( int n ) {
return g f a c t o r i a l ( n , 1 ) ;
}

Durch Einführen der Hilfsfunktion g factorial wird die nachträgliche

Multiplikation vermeiden.
Die Rekursion ist nun endrekursiv.
f (4) = g (4, 1) = g (3, 1 ∗ 4)
g (3, 4) = g (2, 4 ∗ 3)
g (2, 12) = g (1, 12 ∗ 2) = 24

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 25 / 36

Nichtlineare Rekursion

Bei der Endrekursion entfallen viele der Zwischenergebnisse, die auf

dem Stack vorgehalten werden und die Funktion kann am Ende der
Rekursion direkt terminieren.
An dem einfachen Beispiel der Fakultät kommt dieser Vorteil noch
nicht so deutlich zum Tragen, da hier die Rekursion linear verläuft,
anders wird dies bei nichtlinearen Rekursionen.
Eine nichtlineare Rekursion liegt vor, wenn im Rumpf der Definition
von f mehr als ein rekursiver Aufruf ist.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 26 / 36

Nichtlineare Rekursion

Ein besonders schlechtes Lauftzeitverhalten hat die nichtlineare

Rekursion, wie sie z.B. bei den Fibonacci Zahlen: 1, 1, 2, 3, 5, 8, 13,
21, 34, . . . vorkommt.
f1 := f2 := 1
fn := fn−1 + fn−2
Die Aufruffolge zeigt, dass viele Fibonacci Zahlen mehrfach berechnet
werden und circa 2n Auswertungen notwendig sind:
fn

fn−1 fn−2

fn−2 fn−3 fn−3 fn−4

fn−3

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 27 / 36

Auflösen der Rekursion

Es ist offensichtlich, dass diese rekursive Lösung nicht effizient ist und
viele der Zahlen fk unnötig oft berechnet werden.
Zum Berechnen von fk werden lediglich die direkten Vorgängerzahlen
fk−1 und fk−2 benötigt. Wenn der Algorithmus diese bei der
Berechnung nur einmal berechnet und ab dann wiederverwendet, so
wird sich die Rekursion wesentlich verkürzen.
Hierzu wird eine Hilfsfunktion g eingeführt, welche die Fibonacci-Zahl
fk aus den beiden vorhergehenden Funktionswerten mit linearer
Endrekursion berechnet.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 28 / 36

Linearisierung der Rekursion

int g f i b o n a c c i ( int n , int f k 1 , int f k 2 ) {

if ( n<=1) return f k 1+f k 2 ;
return g f i b o n a c c i ( n −1, f k 2+f k 1 , f k 1 ) ;
}

int f i b o n a c c i ( int n ) {
return g f i b o n a c c i ( n − 1 , 1 , 0 ) ;
}

Aus der nichtlinearen Rekursion ist mittels der Hilfsfunktion g eine

Endrekursion geworden.
Diese Lösung hat eine lineare Laufzeit ∼ n im Vergleich zur
ursprünglichen rekursiven Lösung ∼ 2n

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 29 / 36

Endrekursion > Iterative Lösung

Ist erst einmal eine endrekursive Lösung gefunden worden, so ist es

meistens leicht, daraus eine iterative Lösung zu entwickeln, die
hinsichtlich der Laufzeit immer die bessere Variante darstellt.
Die generische Struktur einer linearen Rekursion ist:

g (n) fallsT (n)
f (n) =
h(n, f (n − 1)) sonst

Hierbei ist T(n) die terminierende Bedingung und im Spezialfall

h(n, y ) = y = f (n) ergibt sich die Endrekursion, die sich durch ein
LOOP Programm, d.h. eine einfache n-fache for-Schleife berechnen
lässt.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 30 / 36

Iterative Lösung

unsigned f i b o n a c c i ( unsigned n ) {
unsigned f , f k 1 =1, f k 2 =0;
while (−−n ) {
f = fk1 + fk2 ;
fk2 = fk1 , fk1 = f ;
}
return f k 1 ;
}

Diese iterative Lösung hat die Hilfsfunktion g durch eine Schleife

ersetzt und besitzt sowohl eine optimale Laufzeit als auch den
minimalen Speicherverbrauch.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 31 / 36

Wechselseitige Rekursion

unsigned e v e n ( unsigned n ) {
if ( n==0) return 1 ;
return odd ( n −1);
}

unsigned odd ( unsigned n ) {

if ( n==0) return 0 ;
return e v e n ( n −1);
}

Indirekte Rekursion liegt vor, wenn eine Funktion f eine Funktion h

aufruft, die direkt oder indirekt wiederum eine Rekursion der Funktion
f aufruft, wie hier am Beispiel der Funktionen even und odd, die
berechnen, ob eine Zahl n gerade oder ungerade ist.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 32 / 36

Weitere Rekursionen

Das letzte Beispiel ist ziemlich künstlich, ob eine Zahl n gerade oder
ungerade ist, lässt sich mit der Modulo Operation n modulo 2 == 1
viel einfacher und schneller herausbekommen.
Das Bisektionsverfahren zur Nullstellensuche oder dem Zahlenraten
lässt sich rekursiv durchführen.
Rekursion wird nicht nur für rein mathematische Aufgaben verwendet,
sondern auch bei Strategiespielen, die sich im weitesten Sinne auf
Rekursion zurückführen lassen:
Wolf, Schaf und Kohl mit Floss
Das acht Damen Problem

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 33 / 36

Graphische Rekursionen
Mittels Rekursion lassen sich graphische Algorithmen entwickeln wie
z.B. die fraktale Koch Kurve (1904).
Eine Strecke wird in drei gleichlange Teile zerlegt. Das mittlere
Teilstück wird verdoppelt und die beiden werden mit einem 60◦
Winkel eingefügt. Anschließend wird diese Vorschrift rekursiv auf alle
Teilstücke angewandt.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 34 / 36

Hilbert Kurve

Die Kurve entsteht durch vier Zeichenfunktionen, die sich

wechselseitig rekursiv aufrufen.
Mit zunehmender Rekursionstiefe wird die Kurve immer filigraner und
berührt im Limes jeden Punkt der Fläche und füllt diese vollständig
aus.

n=1 n=2 n=3 n=4 n=5

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 35 / 36

Mandelbrot-Menge
Die Mandelbrot-Menge ist die Menge aller komplexen Zahlen c, für
welche die durch
z0 = 0 zn+1 = zn2 + c
rekursiv definierte Folge beschränkt ist.

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 36 / 36

Literatur

HEROLD, Helmut; LURZ, Bruno; WOHLRAB, Jürgen. SCHLINGGLOFF, Holger.

35. Algorithmus der Woche – Zyklensuche.
Grundlagen der Informatik. [Link]
Pearson Studium, 2012. Alg_Inf_Jahr_pdf/[Link]
WULFF, Nikolaus. KRUMKE,Sven Oliver; NOLTEMEIER, Hartmut.
Einführung in die Informatik I. Graphen und Bäume. Graphentheoretische Konzepte und Algorithmen.
[Link] Springer Vieweg
docs/Informatik-I/Informatik_I_09_Graphen.pdf

Nicolai Kuntze (HS Mainz) GDI 12. Dezember 2017 36 / 36