Fibonacci-Zahlen können wir rekursiv wie folgt berechnen.
def fib(n):
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)
Die Auswertung von fib(3) erfolgt wie folgt.
`fib(3)` auswerten
`fib(2)` auswerten
`fib(1)` auswerten
Ergebnis ist `1`
`fib(0)` auswerten
Ergebnis is `0`
Ergebnis ist `1 + 0 = 1`
`fib(1)` auswerten
Ergebnis ist `1`
Ergebnis ist `1 + 1 = 2`
def binary(n):
if n <= 1:
return str(n)
else:
return binary(n//2) + str(n%2)
Minimalversion der Dokumentation:
binary(6)
binary(3)
binary(1)
"1"
"1" + "1" = "11"
"11" + "0" = "110"
Bei der Ausführung von binary(n) wird binary() insgesamt l mal aufgerufen, wenn l die nächstgrößere ganze Zahl zum Zweierlogarithmus von n ist.
Hier sind zwei Varianten der zu definierenden Funktion, die sich darin unterscheiden, welcher Teil des Ergebnisses mit einem rekursiven Aufruf erzeugt wird.
def from_to_tail(lower,upper):
if lower > upper:
return []
else:
return [lower] + from_to_tail(lower+1,upper)
def from_to_init(lower,upper):
if lower > upper:
return []
else:
return from_to_init(lower,upper-1) + [upper]
Die Funktion from_to_tail() erzeugt alle Elemente des Ergebnisses bis auf das erste mit rekursiven Aufrufen.
from_to_tail(3,5)
from_to_tail(4,5)
from_to_tail(5,5)
from_to_tail(6,5)
[]
[5] + [] = [5]
[4] + [5] = [4,5]
[3] + [4,5] = [3,4,5]
Die Funktion from_to_init() hingegen erzeugt alle Elemente bis auf das letzte mit rekursiven Aufrufen.
from_to_init(3,5)
from_to_init(3,4)
from_to_init(3,3)
from_to_init(3,2)
[]
[] + [3] = [3]
[3] + [4] = [3,4]
[3,4] + [5] = [3,4,5]
Als weitere Alternative können wir auf eine Implementierung mit zwei rekursiven Aufrufen angeben, die sowohl die vorderen als auch die hinteren Elemente berechnen.
def from_to_both(lower,upper):
if lower > upper:
return []
else:
mid = (lower + upper) // 2
return from_to_both(lower,mid-1) + [mid] + from_to_both(mid+1,upper)
Hier werden entsprechend zwei rekursive Aufrufe als Nebenrechnungen auf gleicher Ebene ausgewertet.
from_to_both(3,5)
from_to_both(3,3)
from_to_both(3,2)
[]
from_to_both(4,3)
[]
[] + [3] + [] = [3]
from_to_both(5,5)
from_to_both(5,4)
[]
from_to_both(6,5)
[]
[] + [5] + [] = [5]
[3] + [4] + [5] = [3,4,5]
Die Prozedur print_twice() bricht ab, wenn die übergebene Liste leer ist und gibt ansonsten das erste Element einmal vor und einmal nach dem rekursiven Aufruf aus. Beim rekursiven Aufruf wird eine Teilliste mit allen restlichen Einträgen übergeben.
def print_twice(a):
if len(a) > 0:
print(a[0])
print_twice(a[1:len(a)])
print(a[0])
Der Aufruf put_wave(n) gibt insgesamt $2^n-1$ Zeilen aus. Die mittlere besteht aus der Zeichenkette "~~^", die n mal hintereinander gehängt ausgegeben wird. Davor und danach werden rekursiv jeweils Wellen der Größe n-1 ausgegeben, so dass insgesamt das folgende Muster entsteht (hier für n=4):
irb> put_wave(4)
~~^
~~^~~^
~~^
~~^~~^~~^
~~^
~~^~~^
~~^
~~^~~^~~^~~^
~~^
~~^~~^
~~^
~~^~~^~~^
~~^
~~^~~^
~~^
Jede zweite Zeile enthält die Zeichenkette "~~^" genau einmal, jede vierte (ab der zweiten) zweimal, jede achte (ab der vierten) dreimal und so weiter.
Die Funktion zero() hat einen Parameter n. Im Rumpf von zero() wird der Rückgabewert mit Hilfe einer bedingten Verzweigung bestimmt. Die Abbruchbedingung testet, ob der Wert des Parameters n gleich 0 ist. Falls ja, wird mit Hilfe einer return Anweisung der Wert 0 zurückgegeben. Falls nicht, wird zero() zunächst rekursiv mit dem Argument n-1 aufgerufen. Danach wird zero() noch einmal rekursiv mit dem Ergebnis des ersten Aufrufs als Argument aufgerufen. Das Ergebnis des zweiten Aufrufs wird schließlich mit Hilfe einer return Anweisung zurückgeliefert.
Der Aufruf zero(3) wird wie folgt ausgewertet.
zero(3)
3 == 0 ist false
zero(2)
2 == 0 ist false
zero(1)
1 == 0 ist false
zero(0)
0 == 0 ist true
Ergebnis von zero(0) ist 0
zero(0)
0 == 0 ist true
Ergebnis von zero(0) ist 0
Ergebnis von zero(1) ist 0
zero(0)
0 == 0 ist true
Ergebnis von zero(0) ist 0
Ergebnis von zero(2) ist 0
zero(0)
0 == 0 ist true
Ergebnis von zero(0) ist 0
Ergebnis von zero(3) ist 0
zero() mit einer natürlichen Zahl als Argument liefert als Ergebnis 0 zurück.zero()-Aufrufen. n Anzahl Aufrufe
----- ---------------
0 1
1 1+1+1 = 3
2 1+3+1 = 5
3 1+5+1 = 7
4 1+7+1 = 9
zero(n) mit einer natürlichen Zahl $n$ als Argument werden insgesamt $2n+1$ Aufrufe von zero() ausgewertet.