Direkt zum Inhalt

Lexikon der Mathematik: Rekursionsformel

ein Grundinstrument der Numerischen Mathematik wie auch anderer Teildisziplinen der Mathematik.

Eine Rekursionsformel ist eine Beziehung („Formel“), die eine von einem o.B.d.A. ganzzahligen Index abhängige Größe (Funktionswert, Folgenelement o.ä.) a(n) in Beziehung setzt zu einem oder mehreren vorangehenden Elementen a(n − 1), a(n − 2), ….

Kennt man ein genügend großes Anfangsstück dieser Folge, so kann man also mittels der Rekursionsformel die ganze Folge berechnen. Man spricht dann auch von einer rekursiven Definition.

Ein sehr einfaches Beispiel ist die Rekursionsformel zur Berechnung der Fakultät einer natürlichen Zahl: \begin{eqnarray}n!:=n\cdot (n-1)!.\end{eqnarray} Kennt man hier das „Anfangsstück“ 0! = 1, so kann man mittels (1) alle Fakultäten von n berechnen.

Ein zweites Beispiel ist gegeben durch die Rekursionsformel zur Berechnung der Tschebyschew- Polynome (erster Art) Tn; es gilt: \begin{eqnarray}{T}_{n}(x):=2x{T}_{n-1}-{T}_{n-2}(x).\end{eqnarray} Die Kenntnis von T0(x) = 1 und T1(x) = x macht es auch hier möglich, alle Tschebyschew-Polynome zu berechnen.

Rekursionsformeln sind aus offensichtlichen Gründen auch sehr geeignet zur direkten Implementierung in Algorithmen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos