Ausarbeitung Rekursion (1)

Ausarbeitung für die Matura der 5HIB

Rekursion

Rekursion Rekursive Funktionen sind Funktionen, die sich immer wieder selbst aufrufen. Meist führt die Verwendung von Rekursion zu der saubersten und elegantesten Lösung einer Problemstellung. Jedoch ist die Aufgabe nicht immer durch Rekursion zu lösen. Der Code ist in dem meisten Fällten kürzer, als bei einer iterativen Lösung (mit Schleifen), jedoch ist der (Arbeits-)Speicherverbrauch des Programms größer und die Programmabarbeitung langsamer (bedingt durch die vielen Funktionsaufrufe). Möglich ist die Rekursive Programmierung bei prozeduralen- und objektorientierten Programmiersprachen, nicht jedoch bei Prozessorientierten. Jede Implementierung mit Hilfe von Rekursion benötigt zwangsweise eine Abbruchbedingung, welche der Funktion sagt, ob sie sich jetzt ein weiteres Mal aufrufen soll oder nicht. Ohne Abbruchbedingung würde das Programm in einer Endlosschleife hängen bleiben, und unweigerlich abstürzen (Stack-Overflow, da nicht beliebig viele Funktionen hintereinander aufgerufen werden können).

Beispiel: int fakultaet (int n) { if (n <= 1) { return 1; } else { return (n * fakultaet(n – 1)); } } Diese Funktion berechnet die Fakultät einer gegebenen Zahl. Die Abbruchbedingung ist hier in der dritten Zeile zu finden (if (n <= 1) return 1;). Diese Funktion ruft sich selber immer wieder mit dem um eins verminderten Anfangsargument auf, solange dieses größer als eins ist.

Zur Erklärung: Will man die Fakultät von 4 berechnen, so muss man zunächst die Fakultät von 3 berechnen und das Ergebnis mit 4 multiplizieren. Will man die Fakultät von 3 berechnen, so muss man zunächst die Fakultät von 2 berechnen und das Ergebnis mit 3 multiplizieren. Will man die Fakultät von 2 berechnen, so muss man zunächst die Fakultät von 1 berechnen und das Ergebnis mit 2 multiplizieren. Will man die Fakultät von 1 berechnen, so muss man zunächst die Fakultät von 0 berechnen und das Ergebnis mit 1 multiplizieren. Die Fakultät von 0 ist nach Definition 1. (<- das ist die Abbruchbedingung) Die Fakultät von 1 ist also 1*1=1 Die Fakultät von 2 ist also 2*1=2 Die Fakultät von 3 ist also 3*2=6 Die Fakultät von 4 ist also 4*6=24

Anders kann man auch schreiben: faktorielle(4 * faktorielle(3* faktorielle(2* faktorielle(1* faktorielle(0)))))

Seite 1 von 2

von Fabian Kasper

Ausarbeitung für die Matura der 5HIB

Rekursion

Quellen: http://de.wikipedia.org/wiki/Rekursive_Programmierung http://de.wikipedia.org/wiki/Rekursion http://www.hib-wien.at/leute/wurban/informatik/Rekursion.pdf

Seite 2 von 2

von Fabian Kasper