Einführung in die Programmierung Vorlesung 16

Transcrição

1
Einführung in die Programmierung
Bertrand Meyer
Letzte Aktualisierung: 15. Dezember 2003
Chair of Software Engineering
Intro – Lecture 16
2
Vorlesung 16:
Einführung in die Rekursion
3
1
4
Chiang
Mai
5
6
2
7
APSEC 2003
8
Asia-Pacific Software Engineering Conference
9
3
10
11
12
Vorlesung 16:
Einführung in die Rekursion
4
Die Geschichte des Universums*
13
*Gemäss Édouard Lucas, Récréations mathématiques, Paris, 1883
Dans le grand temple de Bénarès, sous le dôme qui marque le
centre du monde, repose un socle de cuivre équipé de trois
aiguilles verticales en diamant de 50 cm de haut.
A la création, Dieu enfila 64 plateaux en or pur sur une des
aiguilles, le plus grand en bas et les autres de plus en plus petits.
C'est la tour de Brahmâ.
Les moines doivent continûment déplacer les disques de manière
que ceux-ci se retrouvent dans la même configuration sur une
autre aiguille.
La règle de Brahmâ est simple: un seul disque à la fois et jamais
un grand plateau sur un plus petit.
Arrivé à ce résultat, le monde tombera en poussière et disparaîtra.
Die Geschichte des Universums*
14
*Gemäss Édouard Lucas, Récréations mathématiques, Paris, 1883
In the great temple of Benares, under the dome that marks the
center of the world, three diamond needles, a foot and a half high,
stand on a copper base.
God on creation strung 64 plates of pure gold on one of the
needles, the largest plate at the bottom and the others ever
smaller on top of each other. That is the tower of Brahmâ.
The monks must continuously move the plates until they will be
set in the same configuration on another needle.
The rule of Brahmâ is simple: only one plate at a time, and never
a larger plate on a smaller one.
When they reach that goal, the world will crumble into dust and
disappear.
Wie viele Schritte?
15
Beispiel: n Scheiben (n ≥ 0); drei Nadeln mit source, target und
other bezeichnet.
Die grösste Scheibe kann nur dann von source nach target bewegt
werden, wenn target leer ist; deshalb müssen alle anderen
Scheiben auf other liegen.
Deshalb ist die minimale Anzahl der Bewegungen für jede Lösung:
Move n−1 from
source to other
Move largest from
source to target
Hn = Hn−1 + 1 + Hn−1
= 2 * Hn−1 + 1
Move n−1 from
other to target
Da Hn = 1, impliziert dies:
Hn = 2n − 1
5
Daraus resultiert ein Algorithmus
16
move (n: INTEGER;
source, target, other: CHARACTER) is
-- Move n disks from needle source to target,
-- using other as storage.
do
if n > 0 then
move (n−1, source, other, target)
transfer (source, target)
move (n−1, other, target, source)
end
end
Der Begriff “Rekursion”
17
Eine Definition für ein Konzept ist rekursiv,
wenn sie eine Instanz des Konzeptes selbst
beinhaltet.
Bemerkungen:
• Die Definition kann mehr als eine “Instanz des
Konzeptes selbst” benutzen.
• Rekursion ist die Benutzung einer rekursiven
Definition.
Beispiele
18
Rekursive Routinen
Rekursive Grammatiken
Rekursiv definierte Programm-Konzepte
Rekursive Datenstrukturen
6
19
Rekursive Routine
20
Direkte Rekursion: Rumpf beinhaltet einen Aufruf
der Routine selbst.
Beispiel: Routine move der vorherigen Lösung des
Problems “Türme von Hanoi”.
Rekursion kann indirekt sein
21
Routine r beinhaltet einen Aufruf der Routine s
s beinhaltet einen Aufruf von r
Allgemein: r1 ruft r2 ruft ... ruft rn ruft r1.
7
Rekursive Grammatik
22
Instruction = Assignment | Conditional | Compound | ...
Conditional =
if Expression then Instruction
else Instruction end
Lexikographische Ordnung definieren
23
Problem: Definiere, dass das Wort w1 “vor” dem
Wort w2 ist, gemäss der lexikographischen Ordnung.
Konventionen:
Ein Wort ist eine Sequenz von Null oder mehreren
Buchstaben.
Ein Buchstabe ist eines von:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Für beliebige zwei Buchstaben ist bekannt, welcher der
beiden “kleiner” ist; die Ordnung ist die der vorherigen
Liste.
Beispiele
24
ABC vor DEF
AB vor DEF
Leeres Wort vor ABC
A vor AB
A vor ABC
8
Eine rekursive Definition
25
Das Wort w1 ist nur dann “vor” dem Wort w2, wenn
eine der folgenden Bedingungen zutrifft:
w1 ist leer und w2 ist nicht leer.
Weder w1 noch w2 sind leer, und der erste
Buchstabe von w1 ist kleiner als der erste
Buchstabe von w2 .
Weder w1 noch w2 sind leer, die ersten
Buchstaben sind die gleichen, und das Wort, das
durch Entfernen des ersten Buchstabens von w1
entsteht, ist (rekursiv) vor dem Wort, das durch
Entfernen des ersten Buchstabens von w2
entsteht.
Rekursive Datenstrukturen
26
G ist ein beliebiger Typ.
32
Ein binärer Baum über G ist entweder:
Leer
oder
Ein Knoten, bestehend aus drei
Elementen:
Wert von Typ G
Binärer Baum über G,
genannt linkes Kind
des Knotens
Binärer Baum über G,
genannt rechtes Kind
des Knotens
72
20
11
51
68
left
59
Right
Binärer Baum Klassen-Skelett
27
class BINARY_TREE [G] feature
item: G
left: BINARY_TREE [G]
right: BINARY_TREE [G]
... Insertion and deletion features ...
end
9
Binäre Suchbäume
28
Ein binärer Baum hat einen linken
Teilbaum und einen rechten
Teilbaum.
Ein binärer Baum über einer
sortierte Menge G ist ein binärer
Suchbaum, wenn für jeder Knoten
n gilt:
Für jeden Knoten x des linken
Teilbaums n, x.item ≤ n.item
32
72
20
11
51
68
Für jeden Knoten x des
rechten Teilbaums n,
x.item ≥ n.item
59
Ausdrucken von Elementen in
Reihenfolge
29
class BINARY_SEARCH_TREE [G ...] feature
item: G
left, right: BINARY_SEARCH_TREE [G]
right: BINARY_SEARCH_TREE [G]
sort is
do
-- Print element values in order
if left /= Void then left.sort end
print (item)
if right /= Void then right.sort end
end
end
Suchen in einem binären Suchbaum
30
item: G
end
has (x: G): BOOLEAN is
-- Does a node in this subtree have value x?
do
if x < item then
Result := ((left /= Void) and then left.has (x))
elseif x > item then
Result := (right /= Void) and then right.has (x)
else
Result := True
end
end
10
Einfügen in einen binären Suchbaum
31
Lösen sie dies als Übung!
Warum binäre Suchbäume?
32
Lineare Strukturen: Einfügen, Suchen und
Löschen sind O (n).
Binäre Suchbäume: Durchschnittliches
Verhalten für Einfügen, Suchen und Löschen ist
O (log (n)).
Aber: Worst-time Verhalten ist O (n)!
Beachte die Messung der Komplexität: best case,
average, worst case.
Generelle Zuverlässigkeitseigenschaften
33
Damit eine rekursive Definition Sinn macht:
Es muss einen nicht-rekursiven Zweig geben!
Eine nicht-negative Zahl — die Variante der
Rekursion — muss bei jedem Aufruf niedriger
werden.
11
Hanoi: Was ist die Variante?
34
move (n: INTEGER;
source, target, other: CHARACTER) is
-- Move n disks from needle source to target,
-- using other as storage.
do
if n > 0 then
move (n−1, source, other, target)
transfer (source, target)
move (n−1, other, target, source)
end
end
Ausdrucken: Was ist die Variante?
35
item: G
sort is
do
-- Print element values in order
if left /= Void then left.sort end
print (item)
if right /= Void then right.sort end
end
end
McCarthy’s 91 Funktion
36
M (n) =
n − 10
if n > 100
M (M (n + 11))
if n ≤ 100
12
Eine andere Funktion
37
bizarre (n) =
1
if n = 1
bizarre (n / 2)
if n is even
bizarre ((3 ∗ n + 1) / 2) if n > 1 and n is odd
Fibonacci Zahlen
38
fib (1) = 0
fib (2) = 1
fib (n) = fib (n−2) + fib (n−1)
for n > 2
Fakultätsfunktion
39
0! = 1
n! = n * (n − 1)!
for n > 0
Die Rekursive Definition ist nur für Demonstrationszwecke interessant; praktische Implementationen
werden Schleifen (oder Tabellen) anwenden.
13
Unser Original-Beispiel für eine Schleife
40
highest_name: STRING is
-- Alphabetically greatest station name of line f
do
from
f.start ; Result := ""
until
f.after
loop
Result := greater (Result, f.item.name)
f.forth
before
after
end
item
end
1
count
start
forth
Ein rekursives Equivalent
41
highest_name: STRING is
-- Alphabetically greatest station name
-- of line f
require
not f.is_empty
do
f.start
Result := f.highest_from_cursor
end
Hilfsfunktion für Rekursion
highest_from_cursor: STRING is
-- Alphabetically greatest name of stations of
-- line f starting at current cursor position
require
f /= Void; not f.off
do
Result := f.item.name
f.forth
if not f.after then
Result := greater (Result, highest_from_cursor)
end
item
end
1
42
after
count
forth
14
Schleifen-Version mit Argumenten
43
maximum (a: ARRAY [STRING]): STRING is
-- Alphabetically greatest item in a
require
a.count >= 1
local
i: INTEGER
do
from
i := a.lower + 1; Result := a.item (a.lower)
invariant
i > a.lower ; i <= a.upper + 1
-- Result is the maximum element of a [a.lower .. i−1]
until
i > a.upper
loop
if a.item (i) > Result then Result := a.item (i) end
i := i + 1
end
end
Rekursive Version
44
maxrec (a: ARRAY [STRING]): STRING is
-- Alphabetically greatest item in a
require
a.count >= 1
do
Result := max_sub_array (a, a.lower)
end
max_sub_array (a: ARRAY [STRING]; i: INTEGER): STRING is
-- Alphabetically greatest item in a starting from index i
require
i >= a.lower ; i <= a.upper
do
Result := a.item (i)
if i < a.upper then
Result := greater (Result, max_sub_array (a, i + 1))
end
end
Rekursions-Elimination
45
Rekursive Aufrufe verursachen (in einer DefaultImplementation ohne Optimierung) eine LaufzeitEinbusse: Verwaltung eines Stapels für die
aufbewahrten Werte notwendig.
Verschiedene Optimierungen sind möglich.
Manchmal kann eine Rekursion durch eine Schleife
ersetzt werden; dies wird als Rekursions-Elimination
bezeichnet.

“Tail recursion” (letzte Anweisung einer Routine ist ein
rekursiver Aufruf) kann gewöhnlich eliminiert werden.
15
Rekursions-Elimination
x := x’
goto start_of_r
46
r (x) is
do
... Some instructions ...
r (x’)
May need x!
-- e.g. r (x–1)
... More instructions ...
end
Nach Aufruf Zurückgreifen auf vorherige Werte der
Argumente und andere Kontextinformationen
notwendig.
Verwendung eines Stapels
Abfragen:
Ist der Stapel leer? is_empty
Oberstes Element, wenn eines:
item
47
“Top” position
Kommandos:
Lege ein Element an die Spitze:
put
Greife oberstes Element, wenn
überhaupt eines: remove
Rekursion als eine Problem lösende
Technik
48
Anwendbar — wenn man eine Möglichkeit
hat, eine Lösung für ein Problem zu
konstruieren — auf eine gewisse
Inputmenge von Lösungen für eine oder
mehrere kleinere Inputmengen.
16
Dank an...
49
Fromageries Bel (La Vache qui rit)
Yao Volksstamm
Swiss
Verschiedene andere Elefanten
Thailändische Regierung
50
Ende Vorlesung 16
17