Hauptinhalt
Informationstechnik
Kurs: Informationstechnik > 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
© 2023 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 x, start superscript, n, end superscript berechnen, wobei x eine reelle Zahl und n eine ganze Zahl ist. Es ist einfach, wenn n 0 ist, da x, start superscript, 0, end superscript, equals, 1 für beliebige x ist. Das ist ein guter Basisfall.
Mal sehen was passiert, wenn n positiv ist. Wir erinnern uns daran, dass die Multiplikatoren von Potenzen von x, durch die Addition der Exponenten erreicht wird: x, start superscript, a, end superscript, dot, x, start superscript, b, end superscript, equals, x, start superscript, a, plus, b, end superscript. Das gilt für jede Basis x und jeden Exponenten a und b. Wenn also n positiv und gerade ist, dann gilt x, start superscript, n, end superscript, equals, x, start superscript, n, slash, 2, end superscript, dot, x, start superscript, n, slash, 2, end superscript. Wenn du y, equals, x, start superscript, n, slash, 2, end superscript rekursiv berechnen willst, dann könntest du x, start superscript, n, end superscript als y, dot, y berechnen. Aber was ist, wenn n positiv und ungerade ist? Dann ist x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x, wobei n, minus, 1 entweder 0 oder positiv und gerade ist. Wir haben aber gerade gesehen, wie man die Potenzen von x berechnen kann, wenn der Exponent entweder 0 oder positiv und gerade ist. Daher kannst du x, start superscript, n, minus, 1, end superscript rekursiv berechnen und dann dieses Ergebnis verwenden, um x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x zu berechnen.
Was passiert, wenn n negativ ist? Dann gilt: x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript. Der Exponent minus, n ist positiv, da es die Negation einer positiven Zahl ist. So kannst du x, start superscript, minus, n, end superscript rekursiv berechnen und den Kehrwert bilden.
Setzen wir diese Beobachtungen zusammen, erhalten wir den folgenden rekursiven Algorithmus für die Berechnung von x, start superscript, n, end superscript:
- Der Basisfall tritt ein, wenn n, equals, 0 und x, start superscript, 0, end superscript, equals, 1.
- Wenn n positiv und gerade ist, berechne rekursiv y, equals, x, start superscript, n, slash, 2, end superscript und dann ist x, start superscript, n, end superscript, equals, y, dot, y. Beachte, dass du in diesem Fall nur einen rekursiven Anruf ausführst, indem du x, start superscript, n, slash, 2, end superscript nur einmal berechnest, und anschließend das Ergebnis dieses rekursiven Anrufs mit sich selbst multiplizierst.
- Wenn n positiv und ungerade ist, berechne rekursiv x, start superscript, n, minus, 1, end superscript, so dass der Exponent entweder 0 oder positiv und gerade ist. Dann ist x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x.
- Wenn n negativ ist, berechne rekursiv x, start superscript, minus, n, end superscript, so dass der Exponent positiv wird. Dann ist x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript.
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.