Hauptinhalt
Kurs: Informatik > Lerneinheit 1
Lektion 6: Rekursive Algorithmen- Rekursion
- Die Fakultät
- Challenge: Iterative Fakultät
- Rekursive Fakultät
- Challenge: Rekursive Fakultät
- Eigenschaften von rekursiven Algorithmen
- Verwende Rekursion zum bestimmen ob ein Wort ein Palindrom ist
- Challenge: Ist ein String ein Palindrome?
- Die Potenzen einer Zahl berechnen
- Challenge: Rekursive Potenzen
- Mehrere Rekursionen mit dem Sierpinski-Dreieck
- Die Effizienz von rekursiven Funktionen verbessern
- Projekt: Rekursive Kunst
© 2024 Khan AcademyNutzungsbedingungenDatenschutzerklärungCookie-Meldung
Die Potenzen einer Zahl berechnen
JavaScript hat eine eingebaute
pow
-Funktion, die die Potenz einer Zahl berechnen kann. Trotzdem können wir eine ähnlich-effiziente Funktion schreiben, die rekursiv arbeitet. Die einzige Einschränkung dabei ist, dass der Exponent ganzzahlig sein muss.Angenommen, du willst berechnen, wobei eine reelle Zahl und eine ganze Zahl ist. Es ist einfach, wenn 0 ist, da für beliebige ist. Das ist ein guter Basisfall.
Mal sehen was passiert, wenn positiv ist. Wir erinnern uns daran, dass die Multiplikatoren von Potenzen von , durch die Addition der Exponenten erreicht wird: . Das gilt für jede Basis und jeden Exponenten und . Wenn also positiv und gerade ist, dann gilt . Wenn du rekursiv berechnen willst, dann könntest du als berechnen. Aber was ist, wenn positiv und ungerade ist? Dann ist , wobei entweder 0 oder positiv und gerade ist. Wir haben aber gerade gesehen, wie man die Potenzen von berechnen kann, wenn der Exponent entweder 0 oder positiv und gerade ist. Daher kannst du rekursiv berechnen und dann dieses Ergebnis verwenden, um zu berechnen.
Was passiert, wenn negativ ist? Dann gilt: . Der Exponent ist positiv, da es die Negation einer positiven Zahl ist. So kannst du rekursiv berechnen und den Kehrwert bilden.
Setzen wir diese Beobachtungen zusammen, erhalten wir den folgenden rekursiven Algorithmus für die Berechnung von :
- Der Basisfall tritt ein, wenn
und . - Wenn
positiv und gerade ist, berechne rekursiv und dann ist . Beachte, dass du in diesem Fall nur einen rekursiven Anruf ausführst, indem du nur einmal berechnest, und anschließend das Ergebnis dieses rekursiven Anrufs mit sich selbst multiplizierst. - Wenn
positiv und ungerade ist, berechne rekursiv , so dass der Exponent entweder 0 oder positiv und gerade ist. Dann ist . - Wenn
negativ ist, berechne rekursiv , so dass der Exponent positiv wird. Dann ist .
Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.
Willst du an der Diskussion teilnehmen?
Noch keine Beiträge.