> Home
> Algorithmen
> Datenstrukturen
> Probleme
> Maschinenmodelle
> Themen
> Mindmaps
> Aufgaben
> Programmierung
> Facharbeit
> Abitur
> Projekte
> Informatik-AG
> News
> Impressum
> email
|
|
Rekursion und Iteration
Rekursion gehört zu den zentralen Lösungsstrategien der Informatik und Mathematik. Rekursion bezeichnet die Definition von "etwas" durch sich selbst. In Programmiersprechen spielt die Rekursion eine Rolle in er Gestalt von
- Rekursiven Algorithmen (z.B. Funktionen Fakultät, Fibonacci-Zahlen)
- Rekursive Datentypen (z.B. Bäume).
Als Iteration bezeichnet man die schrittweise Berechung einer Funktion aufgrund elementarer Operationen wie z.B. Addition, Subtraktion, Multiplikation usw. Da die Iteration zu den "gängigen" Programmiermethoden gehört, wird sie in deiser MINDMAP nur anhand eines Beispiel erläutert. Rekursion hingegen wird vom Laien jedoch nur selten eingesetzt.
1. Allgemeines Schema der Problemlösung durch Rekursion
(i) Elementarfall: Falls das Problem einfach genug ist, löse es direkt.
(ii) Rekursionsfall: Andernfalls behandle ein Teilproblem direkt und löse dann das auf diese Weise in seinem Umfang reduzierte Problem auf dieselbe Weise wie das gestellte Problem. |
Das allgemeine Schema läßt sich auch in Form einer PASCAL-Prozedur realisieren.
- Der Elementarfall entspricht dre sogenannten Abbruchbedingung.
- Der Rekursionsfall entspricht dem rekursiven Aufruf der Prozedur.
function arbeite_rekursiv;
begin
then <Rückgabe des Elementarfalls>
else begin
<Anweisung>;
<rekursiver Aufruf mit dem reduzierten Problem>;
end;
2. Beispiel: Die Funktion "Fakultät"
Definition:
Die Fakultät einer natürlichen Zahl n>=1 sei wie folgt definiert:
fak(1)=1
fak(2)=1*2=2
fak(3)=1*2*3=6
usw...
fak(n)=1*2*3*...*(n-2)*(n-1)*n
Iterative Lösung:
Eine sogenannte iterative Funktion der Fakultät in PASCAL wird in der Regel wie folgt aussehen:
Iteration bedeutet dabei die schrittweise Berechnung der Fakultätsfunktion aufgrund der elementaren Operationen "Multiplikation" (vgl. MINDMAP "Top-Down-Verfahren").
Function fakit (n:integer):integer;
var i,h:integer;
begin
h:=1;
for i:=1 to n do
h:=h*i;
fakit:=h;
end;
Rekursive Lösung:
Es besteht jedoch auch die Möglichkeit, die Fakultät-Funktionen rekursiven zu rekursiven zu definieren.
Dazu braucht man nur das allgemeine Schema der rekursiven Problemlösung auf die Definition der Fakultät (siehe oben) anwenden.
Elementarfall:
Bei der Untersuchung der mathematischen Definition der Fakultät auf den sogenannten Elementarfall findet man die Definition fak(1)=1. Da dieser Fall genügend einfach ist, kann er als Elemterfall gelten.
(i) Elemtar: fak(1)=1
Hier erkennt man, dass man die Fakultät von n berechnen kann, indem man zunächst einmal die Fakultät von n-1 mit fak(n-1)=1*2*3*...*(n-1) berechnet und das Ergebnis dieser Berechnung mit n multiplizieren. Wie berechnet man jedoch die Fakultät von (n-1)?
Nun, ganz einfach! Man berechnet zunächst die Fakultät von n-2 mit fak(n-2) = 1*2*3*...*(n-2) und multipliziert das Ergebnis mit (n-1). So kann man immer weitermnachen, bis man auf den Elementarfall trifft. Für den Elementarfall ist bereits klar, wie er berechnet wird. (i)
Wir formulieren deshalb den Rekursionsfall:
(ii) Rekursionsfall: Für n>1 fak(n) = fak(n-1)*n
Zusammenfassend erhalten wir also:
(i) Elementarfall: fak(1)=1
(ii) Rekursionsfall: fak(n)=fak(n-1)*n |
Dieses läßt sich direkt als PASCAL-Funktion formulieren:
function fak(n:integer):integer;
begin
if n=1 then fak:=1
else fak:=fak(n-1)*n;
end;
Diese Funktion ist in dieser Form lauffähig. Wie es dem Rechner genau möglich ist, aufgrund dieser Definition die Fakultät korrekt zu brerechnen, ergibt sich aus der Stackverarbeitung (vgl. Abstrakter Datentyp Stapel!) und läßt sich mit dem Kontourmodell (-->) beschreiben.
Weitere rekursive Funktionen sind z.B.
Die Fibonacci-Zahlen
Fib(n):fib(n-2)+f(n-1) für n>=3
Fib(n):=1 für n=1 und n=2
Aufgaben:
1. Definieren Sie die Potenzfunktion POT(a,n)=an rekursiv und entwickeln Sie eine PASCAL-Funktion dazu.
2. Überlegen Sie sich noch andere einfache mathematische Funktionen, die man rekursiv definieren kann!
Zusammengestellt von: Dennis Krumnow
|
|