Eine Gleichung, die jedes Glied einer Folge oder eines diskreten Arrays in Bezug auf vorhergehende Glieder und eventuell den Index definiert, zusammen mit Anfangsbedingungen, die die Folge eindeutig bestimmen.

Prinzip

Angabe eines Basisfalls und einer deterministischen Regel, die spätere Glieder mit früheren verknüpft, sodass die gesamte Folge schrittweise erzeugt wird; lineare Rekursionen erlauben algebraische Lösungsmethoden, nichtlineare erfordern andere Techniken.

Demonstration

Die Fibonacci‑Rekursion F_n = F_{n-1} + F_{n-2} mit F_0 = 0, F_1 = 1 erzeugt die Fibonacci‑Folge; ihre Linearität ermöglicht eine geschlossene Form über das charakteristische Polynom (Binetsche Formel).

Fehlanwendung

Eine Rekursion ohne hinreichende Anfangsbedingungen anzuwenden oder Lösungstechniken für lineare Rekursionen auf nichtlineare Rekursionen zu übertragen, was zu mehrdeutigen oder falschen Folgen führt.

Konsequenz

Rekursionen liefern konstruktive Definitionen, die sich für iterative Berechnung, Komplexitätsanalyse und asymptotische Abschätzungen eignen; lineare Rekursionen lassen sich auf polynomielle Charakteristiken und erzeugende Funktionen zurückführen.

Umkehrung

Eine explizite geschlossene Formel für das n‑te Glied, die keine vorangehenden Glieder zur Auswertung benötigt und direkte Berechnung sowie analytische Asymptotik liefert.

Abgrenzung

Bezieht sich auf diskret indizierte Sammlungen (Folgen, Arrays) und schließt kontinuierliche Differentialgleichungen aus, obwohl Analoga mit Differenzengleichungen bestehen; erfordert wohldefinierte Anfangs‑/Randdaten für Eindeutigkeit.

Semantische Spannung

Spannung zwischen dem breiteren Begriff 'Differenzengleichung' (einschließlich Verschiebungen und Inhomogenitäten) und 'Rekursionsrelation', das häufig für Folgen mit fester Vorwärtsregel verwendet wird.

Synthese

Eine Rekursionsrelation ist eine Regel plus Basisdaten, die rekursiv eine diskrete Folge erzeugt, indem jedes Glied durch frühere ausgedrückt wird, wodurch schrittweise Berechnung und für lineare Fälle algebraische Lösung und asymptotische Analyse möglich sind.