Binäre Exponentiation (ein Beispiel für die Einführung der Rekursion)

Ein zentrales Ziel dieser Unterrichtseinheit ist die anschauliche Einführung der Rekursion. Dies geschieht anhand der binäre Exponentiation, eine Methode zur effizienten Berechnung von Potenzen der Form x^k. Statt Exponenten naiv in k-1 Schritten zu multiplizieren, reduziert dieser Algorithmus die Anzahl der Multiplikationen drastisch, indem das Problem in identische Teilprobleme aufgeteilt wird. Die Einheit besteht aus drei Teilen. Auf eine problemorientierte Einführung in die Thematik folgt die schrittweise Implementierung des Algorithmus in Python. Den Abschluss bilden vertiefende Übungen.