Rekursionsgleichung
Def. Rekursionsgleichung
Eine Rekursionsgleichung ist eine Gleichung (oder Ungleichung), die eine eine Funktion durch ihre eigenen Funktionswerte für kleinere Eingaben beschreibt.
Lösungsansätze für Rekursionsgleichungen
Substitutionsmethode
Wir erraten zuerst eine Schranke. Dann wird Induktion benutzt um die Korrektheit der Vermutung zu beweisen.
Rekursionsbaum-Methode
Die Rekursionsgleichung wird in einen Baum umgewandelt, dessen Knoten die in den verschiedenen Ebenen der Rekursion anfallenden Kosten darstellen. Dann wird dieser mit Techniken zur Beschränkung von Summenformeln gelöst.