Rekursion

Die einfachste Definitionen einer Rekursion ist ein Selbstaufruf. Wichtig bei der Ausführung von rekursiven Programmen ist eine Abbruchbedingung, die definiert, wann das Programm sich nicht mehr selbst aufrufen soll.

Achtung:
In der Informatik werden unter rekursiven Programmen solche verstanden, die sich selbst aufrufen.
In der Mathematik sind rekursive Funktionen solche, die durch sich selbst beschrieben werden.

Beispiel:
Mathematische Rekursion Fakultät: N! = N•((N-1)!)

Beispiele zu Rekursionen

Rekursionen werden im Folgenden an mehreren Programmierbeispielen erläutert.

Zur Berechnung der Fakultät wurde zuvor ein iterativer Algorithmus vorgestellt. Es gibt jedoch auch eine rekursive Lösung zur Berechnung von Fakultäten:

 

faculty_r.m
function faculty = faculty_r(n)
%FACULTY_R Berechnet die Fakultät von n rekursiv
if (n <= 1)
faculty = 1;
else
faculty = n*faculty_r(n-1);
end
end

 

 

Der Selbstaufruf wird in Zeile 6 deutlich: In der Funktion "faculty_r" wird durch den Befehl "faculty = n*faculty_r(n-1);" die Funktion selbst erneut aufgerufen.

 

Ein weiteres Beispiel zur Veranschaulichung von rekursiven Funktionen ist die Berechnung der N-ten Fibonacci-Zahl. Die dazugehörige Formel lautet:
FN = FN-1 + FN-2 mit F0 =0 und F1 = 1

fibonacci.m
function fibo = fibonacci(N)
% Berechnet rekursiv die N-te Fibonacci-Zahl
%
% Vordefinierte Werte:
% fibonacci(0) = 0;
% fibonacci(1) = 1;

switch N
case 0
fibo = 0;
case 1
fibo = 1;
otherwise
% Rekursiver Aufruf
fibo = fibonacci(N-1) + fibonacci(N-2);
end

Sie sehen, dass die Implementierung in dieser Form sehr kompakt und übersichtlich ist. Seien Sie jedoch bereit, MatLab mit Strg + c zu terminieren, wenn Sie höhere Fibonacci-Zahlen abfragen. Dies liegt an der langen Laufzeit des Programmes bei hohen Zahlen (siehe Komplexität im GeDV-Skript). Es handelt sich um ein exponentielles Wachstum der Laufzeit und der Aufrufe.

Einfacher ist die Berechnung einer Liste, welche die Fibonacci-Zahlen enthält. Die Berechnung dieser Liste ist mit linearer Komplexität in Bezug auf Laufzeit und Speicherplatz möglich. Die Berechnung einer solchen Liste wäre aber kein rekursives Verfahren.