Wir haben gesehen, dass mit Hilfe von Rekursion, wie mit bedingten Schleifen, nicht terminierende Berechnungen beschrieben werden können. In der Tat sind Rekursion und bedingte Schleifen gleichmächtig, das heißt jedes Programm mit bedingter Schleife kann in eines übersetzt werden, dass statt dieser Rekursion verwendet und umgekehrt. Im folgenden übersetzen wir beispielhaft eine Funktion mit bedingter Schleife in eine rekursive Funktion ohne Schleifen. Die umgekehrte Übersetzung rekursiver Funktionen in Schleifen betrachten wir nicht.
Die folgende Funktion fact_loop() berechnet die Fakultät des Parameters n mit Hilfe einer bedingten Schleife:
def fact_loop(n):
f = 1
i = 1
while i <= n:
f = f * i
i = i + 1
return f
Wir können diese Funktion systematisch in eine rekursive Funktion übersetzen. Dazu definieren wir eine Funktion fact_rec(), die neben dem Parameter n auch noch weitere Parameter für alle vor der Schleife definierten Variablen hat:
def fact_rec(n, f, i):
if i <= n:
f = f * i
i = i + 1
return fact_rec(n, f, i)
else:
return f
oder kürzer:
def fact_rec(n, f, i):
if i <= n:
return fact_rec(n, f*i, i+1)
else:
return f
Im Rumpf dieser Funktion testen wir die Bedingung der Schleife mit einer bedingten Verzweigung. Ist sie erfüllt, so führen wir den Rumpf der Schleife einmal aus und rufen die Funktion dann rekursiv mit geänderten Parametern auf. Ist die Schleifenbedingung nicht erfüllt, bricht die Rekursion ab und wir führen die Anweisungen aus, die nach der ursprünglichen Schleife
kommen, also return f.
Zur Initialisierung der zusätzlichen Parameter führen wir die Anweisungen vor der Schleife aus und rufen dann die Funktion fact_rec() auf.
def fact(n):
f = 1
i = 1
return fact_rec(n, f, 1)
Wir veranschaulichen die Auswertung des Aufrufs fact(4)
analog zur Auswertung von factorial(4) in Kapitel 8.1:
fact(4):
Das Ergebnis von fact(4) ist fact_rec(4, 1, 1)
fact_rec(4, 1, 1):
Die Schleifenbedingung ist erfüllt.
Das Ergebnis von fact_rec(4, 1, 1) ist fact_rec(4, 1*1, 1+1).
fact_rec(4, 1, 2):
Die Schleifenbedingung ist erfüllt.
Das Ergebnis von fact_rec(4, 1, 2) ist fact_rec(4, 1*2, 2+1).
fact_rec(4, 2, 3):
Die Schleifenbedingung ist erfüllt.
Das Ergebnis von fact_rec(4, 2, 3) ist fact_rec(4, 2*3, 3+1).
fact_rec(4, 6, 4):
Die Schleifenbedingung ist erfüllt.
Das Ergebnis von fact_rec(4, 6, 4) ist fact_rec(4, 6*4, 4+1).
fact_rec(4, 24, 5):
Die Schleifenbedingung ist nicht erfüllt.
Das Ergebnis von fact_rec(4, 24, 5) ist 24.
Das Ergebnis von fact(4) ist also 24.
Diesmal notieren wir die rekursiven Aufrufe nicht als verschachtelte Nebenrechnungen, da deren Ergebnisse nicht mehr weiter verrechnet sondern direkt als Ergebnis verwendet werden. Die Zwischenergebnisse werden im zweiten Parameter f von factRec mitgeführt, die Zählvariable im dritten Parameter i.
Die systematische Übersetzung der Fakultätsberechnung mit einer bedingten Schleife in eine rekursive Funktion führt also zu einer alternativen Implementierung, die sich von unserer ursprünglichen rekursiven Fakultätsfunktion sowohl syntaktisch als auch bezüglich ihrer Ausführung unterscheidet.
Die umgekehrte Übersetzung rekursiver Funktionen mit Hilfe von Schleifen ist nicht trivial. Das im folgenden Abschnitt gezeigte Programm lässt sich nicht so einfach ohne Rekursion ausdrücken (möglich ist es aber).