Rekursion in Python 

Übungsfragen

?   Übungsfrage

Funktionsdefinition

def f( n ):
    return n * f( n - 1 ) if n else 1

Welchen Wert hat die oben definierte Funktion für einen Aufruf mit dem Argumentwert «0»?

Welchen Wert hat die oben definierte Funktion für einen Aufruf mit dem Argumentwert «1»?

Welchen Wert hat die oben definierte Funktion für einen Aufruf mit dem Argumentwert «2»?

Welchen Wert hat die oben definierte Funktion für einen Aufruf mit dem Argumentwert «3»?

Welchen Wert hat die oben definierte Funktion für einen Aufruf mit dem Argumentwert «4»?

Welchen Wert hat die oben definierte Funktion für einen Aufruf mit dem Argumentwert «5»?

Inkarnationen von Funktionen ⃗

Wir können sagen, daß der Parameter »i« in dem folgenden Programm den Wert «2» hat.

main.py

def f( i ):
    return i
print( f( i=2 ))

Inkarnationen

f i 2

Protokoll

2

Aber welchen Wert hat »i« im folgenden Programm?

main.py

def f( i ):
    return i
print( f( i=5 )) 
print( f( i=2 )) 

Inkarnationen

f i 5
f i 2

Protokoll

5
2

Um den Wert von »i« in solch einem Fall genau beschreiben zu können, benötigen wir den Begriff der Inkarnation !

Bei der Auswertung des Aufrufs »f( i=5 )« wird eine Inkarnation der Funktion »f« angelegt, in welcher der Parameter »i« an den Wert «5» gebunden ist.

Bei der Auswertung des Aufrufs »f( i=2 )« wird eine Inkarnation der Funktion »f« angelegt, in welcher der Parameter »i« an den Wert «2» gebunden ist.

Eine Inkarnation  ist eine Kopie  einer Funktion mit einer eigenen Bindungstabelle.

Im obigen Programm gibt es zwei Inkarnation der Funktion »f«, und jede hat ihre eigene Bindungstabelle. In der ersten Bindungstabelle ist der Name »i« an den Wert «5» gebunden, in der zweiten an den Wert «2».

Auf diese Weise kann man nun auch verstehen, wie die Ausgabe »3« des folgenden Programms entsteht.

main.py

def f( i ):
    return i
print( f( i=( 1 + f( i=2 ))))

Inkarnationen

f i 2
f i 3

Protokoll

3

Der Parameter der „inneren“ Inkarnation von »f« ist an den Wert «2» gebunden, Der Parameter der „äußeren“ Inkarnation an den Wert «3».

Nachdem wir nun den Begriff der Inkarnation kennengelernt haben, können wir uns nun auch Fällen zuwenden, in denen mehrere Inkarnation einer Funktion gleichzeitig  existieren.

main.py

def f( i ):
    print( i )
    f( i - 1 ) if i else None
    print( i )
f( 1 )

Inkarnationen

f i 1
> f i 0

Protokoll

1
0
0
1

Im obigen Programme wird während der Aktivität der Inkarnation »f i 1« eine weitere Inkarnation »f i 0« angelegt.

In »f i 1« ist »i« dauerhaft an «1» gebunden. In »f i 0« ist »i« dauerhaft an «0» gebunden.

Durch den Aufruf »f( 1 )« wird zunächst »f i 1« aktiv. »f i 1« gibt dann mit »print( i )« »1« aus.

Durch den Aufruf »f( i - 1 )« wird dann eine weitere f-Inkarnation »f i 0« angelegt, in welcher »i« an «0» gebunden ist. Dies „innere“ Inkarnation »f i 0« existiert nun gleichzeitig zu der äußeren Inkarnation »f i 1«. Die innere Inkarnation »f i 0« gibt dann zweimal »0« aus.

Danach endet  die innere Inkarnation »f i 0«. Das Programm befindet sich jetzt wieder in der äußeren Inkarnation »f i 1«, in der »i« immer noch an «1» gebunden ist. In dieser äußeren Inkarnation befindet sich das Programm nun hinter  dem Aufruf »f( i - 1 )«. Daher führt es dann auch noch das zweite »print( i )« aus, welches dann wieder »1« ausgibt.

Während des Ablaufs der inneren Inkarnation gab es also zwei  Bindungen des Namens »i« gleichzeitig : Zum einem war dieser in der inneren Inkarnation an den Wert «0» gebunden, zum anderen war er in der äußeren Inkarnation an den Wert «1» gebunden.

Einfache Rekursion (Endrekursion) ⃗

Bei der einfachen Rekursion (Endrekursion) ruft sich eine Funktion am Ende wieder selbst auf. Dadurch kann eine Funktion sich immer wieder selbst „wiederholen“.

Skript

def schleife():
    eingaben = input( "Zahl? " )
    zahl = int( eingaben )
    print( "Quadrat =", zahl * zahl )
    schleife()
schleife()

Protokoll

Zahl? 2
Quadrat = 4
Zahl? 5
Quadrat = 25
Zahl? 

Rekursion mit Wiederherstellung ⃗

Bei der Rekursion mit Wiederherstellung werden lokale Variablen einer umgebenden Inkarnation beobachtbar wieder hergestellt.

main.py

def g( i ):
    print( i )
    pass
    print( i )
def f( i ):
    print( i )
    g( i - 1 ) 
    print( i )
f( 1 )

Protokoll

1
0
0
1

main.py

def f( i ):
    print( i )
    f( i - 1 ) if i else None
    print( i )
f( 1 )

Protokoll

1
0
0
1

Die beiden Inkarnationen sichtbar gemacht (Pseudocode)

def f( 0 ):
    print( 0 )
    f( 0 - 1 ) if 0 else None
    print( 0 )
def f( 1 ):
    print( 1 )
    f( 1 - 1 ) if 1 else None
    print( 1 )
f( 1 )

Protokoll

1
0
0
1

Beispiel Reihenfolge umkehren ⃗

Auf diese Weise können wir nun ein Programm schreiben, das beliebig viele eingegebene Zahlen in umkehrter Reihenfolge  wieder ausgibt.

Skript

def f():
    s = input( 'Zahl (0 zum Beenden)? ' )
    f() if int( s )else None
    print( s )if int( s )else None
    
f()

Protokoll

Zahl (0 zum Beenden)? 2
Zahl (0 zum Beenden)? 4
Zahl (0 zum Beenden)? 1
Zahl (0 zum Beenden)? 0
1
4
2

Hinweis für den Dozenten  ► Hier kann der Debugger von IDLE vorgeführt werden.

Begrenzung der Tiefe der Rekursion ⃗

Die Tiefe der Rekursion ist normalerweise auf 1000 begrenzt. Dieser Wert könnte zwar vom Programmierer erhöht werden, was aber das Risiko mit sich bringt, daß das Programm dann bei zu tiefer Rekursion auf unkontrollierte Weise  abstürzt. Daher sollte dieser Wert nicht  (oder nur von Experten) erhöht werden.

main.py

from sys import getrecursionlimit
from sys import setrecursionlimit
print( getrecursionlimit() )
setrecursionlimit( 2000 )
print( getrecursionlimit() )

Protokoll

1000
2000