Rekursion
Rekursion ist eine wichtige Programmiertechnik, bei der eine Funktion sich selbst aufruft. Ein Beispiel ist die Berechnung von Fakultäten. Die Fakultät von 0 ist als 1 definiert. Die Fakultät von n, einer ganzen Zahl größer als 0, ist das Produkt aus allen ganzen Zahlen im Bereich von 1 bis n.
Verwenden der Rekursion
Im folgenden Absatz wird eine Funktion zur Berechnung von Fakultäten beschrieben.
"Wenn die Zahl kleiner als 0 ist, wird sie zurückgewiesen. Ist die Zahl keine ganze Zahl, wird sie zurückgewiesen. Ist die Zahl gleich 0, ist die Fakultät 1. Ist die Zahl größer als 0, wird sie mit der Fakultät der nächstkleineren Zahl multipliziert."
Zum Berechnen der Fakultät einer Zahl, die größer als 0 ist, müssen Sie die Fakultät für mindestens eine weitere Zahl berechnen. Die Funktion muss sich für die nächstkleinere Zahl selbst aufrufen, bevor sie für die aktuelle Zahl ausgeführt werden kann. Dies ist ein Beispiel für eine Rekursion.
Rekursion und Iteration (Schleifen) hängen eng miteinander zusammen. Eine Funktion kann mit einer Rekursion oder mit einer Iteration dasselbe Ergebnis zurückgeben. In der Regel kann eine bestimmte Berechnung mit der einen oder anderen Technik durchgeführt werden, und Sie müssen lediglich die einfachste oder am besten geeignete Vorgehensweise auswählen.
Obwohl Rekursionen häufig sinnvoll sind, passiert es leicht, dass Sie eine rekursive Funktion erstellen, die niemals ein Ergebnis zurückgibt und auch nie einen Endpunkt erreicht. Eine solche Rekursion veranlasst den Computer, eine so genannte "Endlosschleife" auszuführen. Ein Beispiel: Übergehen Sie die erste Regel (negative Zahlen betreffend) aus der verbalen Beschreibung für die Berechnung der Fakultät, und versuchen, Sie die Fakultät einer negativen Zahl zu berechnen. Dies schlägt fehl, da Sie für die Berechnung der Fakultät von z. B. -24 die Fakultät von -25 berechnen müssen. Um die Fakultät von -25 zu berechnen, müssen Sie zuerst die Fakultät von -26 berechnen usw. Es ist offensichtlich, dass hierbei niemals ein Endpunkt erreicht wird.
Ein weiteres Problem, das im Zusammenhang mit einer Rekursion auftreten kann, besteht darin, dass eine rekursive Funktion u. U. alle verfügbaren Ressourcen beansprucht (z. B. Systemspeicher und Stapelspeicher). Jedes Mal, wenn eine rekursive Funktion sich selbst aufruft (oder eine andere Funktion aufruft, die die ursprüngliche Funktion aufruft), belegt sie Ressourcen. Diese Ressourcen werden bei Beendigung der rekursiven Funktion freigegeben, aber eine Funktion, die zu viele Rekursionsebenen aufweist, belegt möglicherweise alle verfügbaren Ressourcen. Wenn dies geschieht, wird eine Ausnahme ausgelöst.
Deshalb ist es sehr wichtig, rekursive Funktionen mit größter Sorgfalt zu entwerfen. Wenn Sie befürchten, dass eine Rekursion zu einem unerwünschten Ergebnis (oder zu einer Endlosschleife) führt, entwerfen Sie die Funktion so, dass sie zählt, wie oft sie sich aufruft, und dass eine Obergrenze für die Anzahl der Aufrufe gesetzt wird Wenn die Funktion sich dann öfter aufruft, als der Grenzwert zulässt, kann die Funktion automatisch beendet werden. Der optimale Wert für die maximale Anzahl der Iterationen hängt von der rekursiven Funktion ab.
Im Folgenden finden Sie die Funktion zur Berechnung der Fakultät noch einmal, diesmal als JScript-Code. Typanmerkung wird verwendet, damit die Funktion nur ganze Zahlen akzeptiert. Wird eine ungültige Zahl übergeben (z. B. eine Zahl kleiner als null), löst die throw-Anweisung einen Fehler aus. Andernfalls wird eine rekursive Funktion verwendet, um die Fakultät zu berechnen. Die rekursive Funktion verwendet zwei Argumente: eines für das Fakultätsargument und eines für den Zähler, der die aktueller Rekursionsebene protokolliert. Wenn der Zähler die maximale Rekursionsebene nicht erreicht, wird die Fakultät der ursprünglichen Zahl zurückgegeben.
function factorialWork(aNumber : int, recursNumber : int ) : double {
// recursNumber keeps track of the number of iterations so far.
if (aNumber == 0) { // If the number is 0, its factorial is 1.
return 1.;
} else {
if(recursNumber > 100) {
throw("Too many levels of recursion.");
} else { // Otherwise, recurse again.
return (aNumber * factorialWork(aNumber - 1, recursNumber + 1));
}
}
}
function factorial(aNumber : int) : double {
// Use type annotation to only accept numbers coercible to integers.
// double is used for the return type to allow very large numbers to be returned.
if(aNumber < 0) {
throw("Cannot take the factorial of a negative number.");
} else { // Call the recursive function.
return factorialWork(aNumber, 0);
}
}
// Call the factorial function for two values.
print(factorial(5));
print(factorial(80));
Ausgabe dieses Programms:
120
7.156945704626378e+118