Einige der kennengelernten Sortier-Algorithmen sind rekursiv. Wir wollen uns die Rekursion am Beispiel der Fakultät nochmals anschauen und eine weitere ganz spezielle rekursive Funktion kennenlernen.
Fakultät
Dateinamen
EF-Informatik/docs/Algorithmen/faculty.py
Programmieren Sie selbst die Fakultätsfunktion und führen Sie diese in VS Code im Debug-Modus aus. Sehen Sie sich insbesondere den Stack an und versuchen Sie zu verstehen, wie die Rekursion funktioniert.
Halten Sie Ihre Erkenntnisse fest!
Betrachten Sie nochmals die Sortieralgorithmen, die Sie bei der Zeitmessung verwendet haben. Welche davon sind rekursiv?
Ackermann-Funktion
Schauen Sie sich das obige Video an und programmieren Sie die Ackermann-Funktion in Python. Versuchen Sie diese für die im Video vorkommenden Werte zu berechnen.
Dateinamen
EF-Informatik/docs/Algorithmen/ackermann.py
def check_sum(ord_list):
if len(ord_list) <= 0:
return 0
elif len(ord_list) < 2:
return ord_list[0]
return (ord_list[0] + ord_list[1]) * len(ord_list) + check_sum(ord_list[2:])
print(check_sum([4, 2, 3, 3, 12]))
Was macht der obige Code? Führen Sie den Code für die gegebene Liste von Hand aus - welches Ergebnis kommt raus?
Analysieren Sie das Laufzeitverhalten des Codes. Wie viele Rekursionsaufrufe braucht es bei einer Liste mit n Elementen?
In welcher Komplexitätsklasse liegt der Code?
def check_sum2(liste):
cnt[0] += 1
if len(liste) == 0:
return 0
elif len(liste) == 1:
return liste[0] * liste[0]
idx = len(liste) // 2 # durch 2 teilen und das Ergebnis abrunden
if liste[0] < liste[idx]:
return check_sum2(liste[:idx]) * liste[idx]
else:
return check_sum2(liste[idx:]) * liste[0]
print(check_sum2([1,4,3,6,2]))
print(check_sum2([1,2,3,4,5,6,7,8,9]))
print(check_sum2([9,8,7,6,5,4,3,2,1]))
Was macht der obige Code? Führen Sie den Code für die gegebenen Listen von Hand aus - welches Ergebnis kommt raus?
Analysieren Sie das Laufzeitverhalten des Codes. Wie viele Rekursionsaufrufe braucht es bei einer Liste mit n Elementen? Tipp: Wie verändert sich die Listengrösse bei jedem Rekursionsaufruf?
In welcher Komplexitätsklasse liegt der Code?
⭐ Schizophrene Zahlen
Dateinamen
EF-Informatik/docs/Algorithmen/schizo.py
Schreiben Sie eine Funktion schizo(n), die für eine gegebene Zahl n die schizophrene Zahl so wie im Artikel beschrieben berechnet.
Beachten Sie: Python rundet standardmässig die 16. Nachkommastelle. Sollen mehr Nachkommastellen dargestellt werden, können die Anzahl Nachkommastellen erhöht werden.
Dies geht mit dem Modul decimal:
from decimal import Context, Decimal
from math import sqrt
wurzel2_normal = sqrt(2)
wurzel2_decimal = Decimal(2).sqrt(Context(prec=1000))
print(f'Auf 15 Stellen: {wurzel2_normal}')
print(f'Auf 1000 Stellen: {wurzel2_decimal}')
def schizo(n):
pass
Rekursion