Rekursionsrelation

Eine Rekursionsrelation, auch Rekurrenzrelation, definiert eine Folge durch Bezüge auf frühere Glieder. Typischerweise wird sie zusammen mit Anfangs- oder Randbedingungen angegeben, zum Beispiel a_0 und eventuell weitere Anfangswerte, und durch eine Gleichung, die a_n in Abhängigkeit von vorhergehenden Gliedern bestimmt. Ziel ist es, eine explizite Form für a_n oder zumindest das langfristige Verhalten der Folge zu beschreiben.

Formen und Begriffe: Rekursionsrelationen lassen sich unter anderem unterscheiden in lineare versus nichtlineare, sowie homogene versus nicht-homogene Rekursionen. Eine lineare Rekursion mit konstanten Koeffizienten hat die Form a_n = c1 a_{n-1} + c2 a_{n-2} + ... + ck a_{n-k} + f(n), wobei f(n) eine zulässige Funktionskomponente sein kann. Homogen bedeutet, dass kein zusätzlicher Term ohne vorherige Glieder auftaucht (f(n) = 0). Gängige Beispiele sind die Fibonacci-Folge F_n = F_{n-1} + F_{n-2} mit F_0 = 0, F_1 = 1.

Lösungstechniken: Bekannte Methoden sind das Ausklammern bzw. Durchlaufen der Rekursion (Induktion), die Verwendung der charakteristischen Gleichung für lineare homogene Rekursionen, sowie Generating-Functions-Ansätze. Bei nicht-homogenen Rekursionen wird oft eine besondere Lösung bestimmt und zur allgemeinen Lösung addiert. Für viele rekursionsbasierte Algorithmen lässt sich zudem mit dem Master-Theorem der Zeitaufwand für T(n) = a T(n/b) + f(n) abschätzen.

Bedeutung: Rekursionsrelationen treten in Mathematik und Informatik auf, um Folgen zu definieren, und dienen zur Analyse von Algorithmen, Sequenzen und numerischen Verfahren. Ihre Lösung liefert oft Einblicke in Wachstumsraten und Grenzverhalten.