dbLounge
Rekursion
Rekursion bezeichnet allgemein eine Funktion, die sich selber aufruft.
Viele Probleme, die mit Rekursion lösbar sind, können auch ohne gelöst werden; die rekursive Variante ist jedoch meist die elegantere mit dem kürzeren Code.

Da eine rekursive Funktion sich selber aufruft, ist es unbedingt notwendig, eine Abbruchbedingung einzuführen, die die Kette beendet. Ansonsten wird es zwangsläufig zu einer Endlosschleife von Funktionsaufrufen und damit zum Programmabsturz kommen.

Beim Einsatz von rekursiven Funktionen sollte man auch bedenken, dass jeder Funktionsaufruf Speicher im Stack verbraucht. In extremen Fällen kann somit der gesamte Stack gefüllt und das Programm zum Absturz gebracht werden.




Die Rekursion lässt ich besonders gut an einem Beispiel aus der Mathematik, an der Fakultät veranschaulich:

Um die Fakultät n! der Ganzzahl n zu erhalten, multipliziert man einfach alle natürlichen Zahlen von 1 bis n. (3! ist somit 3*2*1 = 6.)

Eine Funktion zur Berechnung der Fakultät kann man sowohl mit als auch ohne Rekursion umsetzen:



rem nicht-rekursive Funktion

function Fak1(n)

f=1

rem Berechnungen in einer Schleife durchführen

for i=1 to n

f=f*i

next i

endfunction f




rem rekursive Funktion

function Fak2(n)

rem Abbruchbedingung

if n<=1 then exitfunction 1

rem die Funktion ruft sich selber auf

f=n*Fak2(n-1)

endfunction f




Wie man sieht löst die nicht-rekursive Funktion die gesamte Berechnung in einem Funktionsaufruf, während die rekursive nur jeweils ein Teilproblem löst (die Fakultät von (n-1) mit n multiplizieren) und für die restliche Berechnung sich selbst aufruft. Das kann für viele Anwendungsbereiche (z.B. für Wegfindungs-Algorithmen) hilfreich sein.