Grundlagen der Informatik 2, Vorlesung 13: Rekursion

Viele Strukturen und Verfahren lassen sich sinnvoll durch Selbstreferenz ausdrücken. So ist beispielsweise eine Warteschlange rekursiv zu definieren wie folgt: eine leere Folge von Menschen ist eine Warteschlange (Rekursionsende) und eine Warteschlange, der man einen Menschen hinten anfügt, ist ebenfalls eine Warteschlange (Selbstbezüglichkeit). In dieser Vorlesung werden wir insbesondere einen Blick auf rekursive Algorithmen werfen und sehen, dass rekursive Definitionen nicht nur kompakt und elegant sein können, sondern zudem effizientere Verfahren wie Merge Sort motivieren können.