Rekursion
Bei der rekursiven Programmierung ruft sich eine Prozedur, Funktion oder Methode in einem Computerprogramm selbst wieder auf, bis eine Abbruchsbedingung erreicht ist. Rekursive Programme haben in der Regel keine gute Performance. Durch die wiederholten Funktionsaufrufe (Inkarnationen) wird immer wieder derselbe Methodeneintrittscode bearbeitet und bei jeder Inkarnation der Kontext gesichert, was zu zusätzlichem Programmcode und höherem Arbeitsspeicherverbrauch führt. Alle rekursiven Algorithmen lassen sich jedoch auch durch iterative Programmierung implementieren und umgekehrt.
Klassisches Beispiel für eine Rekursion ist die Berechnung der Fakultät. Die Fakultät ist das Produkt aller ganzen Zahlen von 1 bis zu dieser Zahl. Die Fakultät von 5! ist also 1 * 2 * 3 * 4 * 5 = 120.
Die Fakultät der Zahl 0 ist definitionsgemäß 1.
Die Fakultät einer
ganzen Zahl, die größer als Null ist, ist das Produkt dieser Zahl mit
der Fakultät der nächstkleineren ganzen Zahl.
Die Definition funktioniert so:
- Will man die Fakultät von 5 berechnen, so muss man zunächst die Fakultät von 4 berechnen und das Ergebnis mit 5 multiplizieren.
- 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.
- Die Fakultät von 1 ist also 1*1=1
- Die Fakultät von 2 ist also 1*1*2=2
- Die Fakultät von 3 ist also 1*1*2*3=6
- Die Fakultät von 4 ist also 1*1*2*3*4=24
- Die Fakultät von 5 ist also 1*1*2*3*4*5=120
Ein anderes beliebtes Beispiel ist das Erzeugen von Fraktalen, Bäumen usw.