Rekursive Programmierung

Stichpunkte

Allgemein
	Bei der rekursiven Programmierung ruft sich eine Prozedur
	Funktion oder Methode in einem Computerprogramm selbst wieder auf
	Auch der gegenseitige Aufruf stellt eine Rekursion dar
	Wichtig dabei ist eine Abbruchbedingung in dieser Funktion
	weil sich das rekursive Programm sonst (theoretisch) bis in alle Ewigkeit selbst aufrufen würde
	Die rekursive Programmierung findet oft Anwendung in prozeduralen und objektorientierten Programmiersprachen
	stellen Selbstaufrufe und gegenseitige Aufrufe bei der Programmierung die Ausnahme dar
	Obwohl diese Sprachen in ihrem Sprachstandard die Rekursion ausdrücklich zulassen
	Die meisten Programme in diesen Sprachen sind rein iterativ
	wie z
	In einigen Sprachen
	B. in manchen funktionalen Programmiersprachen oder Makroprozessoren
	muss die rekursive Programmiermethode zwingend verwendet werden
	da iterative Sprachkonstrukte fehlen
	Ein Beispiel für die Verwendung einer rekursiven Programmierung ist die Berechnung der Fakultät einer Zahl
	Die Fakultät ist das Produkt aller ganzen Zahlen von 1 bis zu dieser Zahl
	Die Fakultät von 4 ist also <math>1 cdot 2 cdot 3 cdot 4 = 24<math>
	Mathematiker definieren die Fakultät meistens so (eine rekursive Definition): Die Fakultät der Zahl 0 ist definitionsgemäß 1
	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 2*1=2 Die Fakultät von 3 ist also 3*2=6 Die Fakultät von 4 ist also 4*6=24 In einer Sprache wie Pascal
	ist das Produkt dieser Zahl mit der Fakultät der nächstkleineren ganzen Zahl. Die Definition funktioniert so: Will man die Fakultät von 4 berechnen
	kann man die Fakultät folgendermaßen eingeben: Man definiert eine Funktion fac
	die eine Zahl x als Eingabewert bekommt
	die rekursive Programmierung zulässt
	Die Fakultät einer ganzen Zahl
	die größer als Null ist
	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
	Diese Funktion multipliziert x mit dem Rückgabewert von fac(x-1) außer x=0
	dann liefert die Funktion das Ergebnis 1
	nämlich 24
	Dies ist die Abbruchbedingung: Rekursive Implementation der Fakulätsfunktion function fac(x : Integer): Integer; begin if x = 0 then fac := 1 else fac := x * fac(x - 1); end; Mit der Startzahl x=4 würde der Computer rechnen: fac(4*fac(3*fac(2*fac(1)))) heraus kommt dann das richtige Ergebnis
	Rekursive Programme haben keine gute Performance
	was zu hohem Arbeitsspeicherverbrauch führt
	Durch die wiederholten Funktionsaufrufe wird immer wieder derselbe Methodeneintrittscode bearbeitet und jedesmal der Kontext gesichert
	Die meisten rekursiven Algorithmen lassen sich jedoch durch iterative Programmierung implementieren
	Ergebnis: Integer; begin Ergebnis:=1; for i:=1 to x do Ergebnis:=Ergebnis*i; fac:=Ergebnis; end; Nicht alle höheren Programmiersprachen lassen rekursive Aufrufe zu; ein Beispiel dazu ist Fortran. [Bearbeiten]
	Man hätte die Fakultät auch so implementieren können: Iterative Implementation der Fakulätsfunktion function fac(x : Integer): Integer; var i
Implementation
	aber auch alle lokalen Variablen und evtl
	der die Rücksprungadressen
	Rekursion wird in der Regel durch einen Stack implementiert
	Funktionsergebnisse aufnimmt
	die Fakultät von 4 berechnen
	Würde man
	ob das Argument 0 ist
	so würde jeder Aufruf folgende Informationen auf den Stapel legen: Platz für Ergebnis Argument x Rücksprungadresse Zunächst würde im Hauptprogramm also fac(4) aufgerufen und damit die folgenden Informationen auf den Stapel gelegt: Stapelanfang <math>rightarrow<math> 1 Platz für Ergebnis 2 4 (Argument) Stapelzeiger <math>rightarrow<math> 3 Rücksprungadresse ins Hauptprogramm Die Fakultätsfunktion prüft jetzt
	wie im obenstehenden Beispiel
	wird 4*fac(3) berechnet
	Da dies nicht der Fall ist
	Zunächst muss also fac mit dem Argument 3 aufgerufen werden: Stapelanfang <math>rightarrow<math> 1 Platz für Ergebnis 2 4 (Argument) 3 Rücksprungadresse ins Hauptprogramm 4 Platz für Ergebnis 5 3 (Argument) Stapelzeiger <math>rightarrow<math> 6 Rücksprungadresse in die Fakultätsfunktion Das Argument ist wieder ungleich 0
	also1*fac(0). Stapelanfang <math>rightarrow<math> 1 Platz für Ergebnis 2 4 (Argument) 3 Rücksprungadresse ins Hauptprogramm 4 Platz für Ergebnis 5 3 (Argument) 6 Rücksprungadresse in die Fakultätsfunktion 7 Platz für Ergebnis 8 2 (Argument) 9 Rücksprungadresse in die Fakultätsfunktion 10 Platz für Ergebnis 11 1 (Argument) 12 Rücksprungadresse in die Fakultätsfunktion 13 Platz für Ergebnis 14 0 (Argument) Stapelzeiger <math>rightarrow<math> 15 Rücksprungadresse in die Fakultätsfunktion Jetzt ist das Argument 0
	also geht's weiter mit 3*fac(2). Stapelanfang <math>rightarrow<math> 1 Platz für Ergebnis 2 4 (Argument) 3 Rücksprungadresse ins Hauptprogramm 4 Platz für Ergebnis 5 3 (Argument) 6 Rücksprungadresse in die Fakultätsfunktion 7 Platz für Ergebnis 8 2 (Argument) Stapelzeiger <math>rightarrow<math> 9 Rücksprungadresse in die Fakultätsfunktion Das Argument ist wieder ungleich 0
	das Ergebnis also 1
	also2*fac(1). Stapelanfang <math>rightarrow<math> 1 Platz für Ergebnis 2 4 (Argument) 3 Rücksprungadresse ins Hauptprogramm 4 Platz für Ergebnis 5 3 (Argument) 6 Rücksprungadresse in die Fakultätsfunktion 7 Platz für Ergebnis 8 2 (Argument) 9 Rücksprungadresse in die Fakultätsfunktion 10 Platz für Ergebnis 11 1 (Argument) Stapelzeiger <math>rightarrow<math> 12 Rücksprungadresse in die Fakultätsfunktion Das Argument ist wieder ungleich 0
	Wir holen die Rücksprungadresse und das Argument vom Stapel und schreiben die 1 in den dafür vorgesehen Platz
	Der Rücksprung führt in die Fakultätsfunktion zurück: Stapelanfang <math>rightarrow<math> 1 Platz für Ergebnis 2 4 (Argument) 3 Rücksprungadresse ins Hauptprogramm 4 Platz für Ergebnis 5 3 (Argument) 6 Rücksprungadresse in die Fakultätsfunktion 7 Platz für Ergebnis 8 2 (Argument) 9 Rücksprungadresse in die Fakultätsfunktion 10 Platz für Ergebnis 11 1 (Argument) 12 Rücksprungadresse in die Fakultätsfunktion Stapelzeiger <math>rightarrow<math> 13 1 (Ergebnis) Jetzt kann man das Ergebnis mit dem Argument multiplizieren (1*1)
	Das neue Ergebnis ist wieder 1. Die Rücksprungadresse und das Argument werden vom Stapel geholt und das neue Ergebnis in den dafür vorgesehenen Platz geschrieben
	Rücksprung in die Fakultätsfunktion: Stapelanfang <math>rightarrow<math> 1 Platz für Ergebnis 2 4 (Argument) 3 Rücksprungadresse ins Hauptprogramm 4 Platz für Ergebnis 5 3 (Argument) 6 Rücksprungadresse in die Fakultätsfunktion 7 Platz für Ergebnis 8 2 (Argument) 9 Rücksprungadresse in die Fakultätsfunktion Stapelzeiger <math>rightarrow<math> 10 1 (Ergebnis) Wiederum wird das Ergebnis mit dem Argument multipliziert (1*2)
	Zurück in die Fakultätsfunktion: Stapelanfang <math>rightarrow<math> 1 Platz für Ergebnis 2 4 (Argument) 3 Rücksprungadresse ins Hauptprogramm 4 Platz für Ergebnis 5 3 (Argument) 6 Rücksprungadresse in die Fakultätsfunktion Stapelzeiger <math>rightarrow<math> 7 2 (Ergebnis) Das Ergebnis wird mit dem Argument multipliziert (2*3)
	Zurück in die Fakultätsfunktion: Stapelanfang <math>rightarrow<math> 1 Platz für Ergebnis 2 4 (Argument) 3 Rücksprungadresse ins Hauptprogramm Stapelzeiger <math>rightarrow<math> 4 6 (Ergebnis) Das Ergebnis wird mit dem Argument multipliziert (6*4)
	Zurück ins Hauptprogramm StapelanfangStapelzeiger <math>rightarrow<math> 1 24 (Ergebnis) Das Hauptprogramm muss dann nur noch das Ergebnis 24 vom Stapel holen
	Siehe auch: Quicksort

[X] Schliessen

Dieser Artikel basiert auf dem Artikel Rekursive Programmierung aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.