Die Rekursion – der Selbstaufruf von Prozeduren – ist eine der großen Errungenschaften der Programmiertechnik. In der Mathematik ist dieses Prinzip schon lange als Induktion bekannt. Aber bis in die sechziger Jahre wurde es als Programmierparadigma noch nicht verwandt. Dabei ist es einer der elegantesten Formulierungskalküle, die die Informatik kennt.
Die Kunst des Programmierens besteht unter anderem darin, eine Aufgabe in sich ständig wiederholende Teilaufgaben zu zerlegen. Erst das Prinzip der Schleife, der gesteuerten Wiederholung macht die Zahl der geschriebenen Statements wesentlich kürzer als die Zahl der ausgeführten Schritte und damit ein Programm wirklich potent.
Wir kennen die for- und die while-Schleife. Die Programmierung, die mit dieser Art Schleifen auskommt, nennen wir iterative Programmierung. Ein Schleife anderer Art liefert der Selbstaufruf von Prozeduren. Dies führt zur rekursiven Programmierung. Es wird nicht ein Block immer wieder durchlaufen (Iteration), sondern ein Block wird in sich selbst verschachtelt (Rekursion).
Dies führt zu einer erstaunlichen Eleganz der Beschreibung eines Problems: das Problem wird in Teilprobleme gleicher Art zerlegt. Das setzt Selbstähnlichkeit voraus: das Problem ähnelt seinen Teilproblemen. Wenn dies der Fall ist, kann das Problem beschrieben werden, indem man seine Zerlegung beschreibt, was in der Regel eine sehr kurze Beschreibung ist.
Der andere Vorteil ist, dass der Rechenaufwand der rekursiven Implementierung eines Problems durch eine Rekursionsgleichung beschrieben und in der Regel einfach errechnet werden kann.
Ein Nachteil ist, dass diese Art der Schleifenbildung ineffiziente Programme liefern kann, wenn dieselben Rechnungen mehrfach gerechnet werden. Dann liegt der Vorteil in der Eleganz und Lesbarkeit des Programms und nicht in seiner Effizienz, d.h. seinem geringen Rechenaufwand.
Wir wollen ein Programm für die Funktion 2n schreiben. Wir wissen 2n = 2 *2n-1 für n > 0 und 20 = 1.
1. Möglichkeit:
x = 1;
for i = 1 to n do x = 2x.
2. Möglichkeit:
x = 1;
i = 1;
while i <=
n do begin x = 2x; i = i+1 end.
3. Möglichkeit:
function exp(n:
integer): integer;
begin
if n = 0 then result:= 1
else result:= exp(n-1) * 2
end.
Beispiel 23
result = 2
result = 4
result = 8
exp(0)
= 1
exp(1)
= exp(0)*2
exp(2) = exp(1)*2
exp(3) = exp(2)*2
Wie programmiert man
rekursiv.
Zunächst muß die Aufgabe so präzisiert
werden, dass erkennbar ist, in welche selbstähnlichen Teilaufgaben sie
zerfällt. Dann erstellt man eine formale induktive Definition, die man
direkt in ein rekursives Programm übersetzen kann. Schließlich
macht man sich anhand einer Beispieleingabe klar, ob die Aufrufe der Prozedur
wie gedacht ablaufen.
Beispiel 2n
1. Präzisierung: 2n
= 2 * 2*...*2 (n-mal) und 20
= 1.
2.
induktive Definition: 2n = 1 falls n = 0 und 2n = 2 * 2n-1 sonst.
3. rekursives Programm:
wie oben.
4.
Test: wie oben.
Beispiel n!
1. Präzisierung: n!
= 1 * 2 * 3 ... * n und 0! = 1.
2. induktive Definition: n! = 1 falls n = 0 und n! = (n - 1)! * n sonst.
3.
rekursives
Programm:
function
fac (n : integer) : integer
begin
if
n = 0 then result:= 1
else
result:= fac(n-1)* n
end;
4.
Test: für n = 3
result = 1
result = 2
result = 6
fac(0)
= 1
fac(1)
= fac(0)*1
fac(2) = fac(1)*2
fac(3) = fac(2)*6
Beispiel ggT(m, n) (größter
gemeinsamer Teiler von m und n)
1.
Präzisierung: ggT(m, n) = größte Zahl, die m und n
ohne Rest teilt.
2.
induktive Definition: ggT(m, n) = m, falls n = 0, und ggT(m, n) = ggT
(n, m mod n), falls n > 0.
3. rekursives Programm:
function ggT(m,n: integer): integer;
begin
if
n = 0 then result := m
else result := ggT(n, m mod n);
end;
4. Test: ggT
(15, 12)
1. Aufruf m = 15, n = 12
2. Aufruf m = 12, n = 3
3. Aufruf n = 3, n = 0
result = 3
result
= 3
result
= 3