Movatterモバイル変換

Rekursive Programmierung

aus Wikipedia, der freien Enzyklopädie

Bei derrekursiven Programmierung ruft sich eineProzedur,Funktion oderMethode in einemComputerprogramm selbst wieder auf (d. h. enthält eineRekursion). Auch der gegenseitige Aufruf stellt eine Rekursion dar.

Wichtig bei derrekursiven Programmierung ist eineAbbruchbedingung in dieserFunktion, weil sich das rekursiveProgramm sonst theoretisch unendlich oft selbst aufrufen würde.

RekursiveProgrammierung kann unter anderem inprozeduralen undobjektorientierten Programmiersprachen angewandt werden. Obwohl diese Sprachen in ihrem Sprachstandard dieRekursion ausdrücklich zulassen, stellen Selbstaufrufe und gegenseitige Aufrufe hier (aufgrund der verwendetenProgrammierparadigmen) jedoch eher die Ausnahme dar. Auch wenn in der Praxis zur Verbesserung desProgrammierstils auch hier durchaus häufig auf Rekursion zurückgegriffen wird, sind die meistenFunktionen in diesen Sprachen doch reiniterativ.

In einigen Sprachen, wie z. B. in manchenfunktionalen Programmiersprachen oderMakroprozessoren, muss die rekursive Programmiermethode zwingend verwendet werden, daiterative Sprachkonstrukte fehlen.

Beispiele

[Bearbeiten |Quelltext bearbeiten]

Fakultät

[Bearbeiten |Quelltext bearbeiten]

Ein Beispiel für die Verwendung einerrekursiven Programmierung ist die Berechnung derFakultät einer Zahl. Die Fakultät ist dasProdukt aller ganzen Zahlen von 1 bis zu dieser Zahl. Die Fakultät von 4 ist also $1\cdot 2\cdot 3\cdot 4=24$ .

Mathematiker definieren die Fakultät meistens so (eine rekursive Definition):

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 dieFakultä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

In einerProgrammiersprache wie Pascal, die rekursive Programmierung zulässt, kann man dieFakultät folgendermaßen eingeben:

Man definiert eineFunktionfactorial, die eine Zahlx als Eingabewert bekommt. Diese Funktion multipliziertx mit dem Rückgabewert vonfactorial(x - 1) außer beix = 0, dann liefert die Funktion das Ergebnis 1. Dies ist die Abbruchbedingung:

Rekursive Implementation der Fakultätsfunktion

functionfactorial(x:Integer):Integer;beginifx=0thenfactorial:=1elsefactorial:=x*factorial(x-1);end;

Mit der Startzahlx = 4 würde derComputer rechnen:

4 * (3 * (2 * (1 * factorial(0))))

heraus kommt dann das richtige Ergebnis, nämlich 24.

Binäre Suche

[Bearbeiten |Quelltext bearbeiten]

Diebinäre Suche in einem vorsortiertenArray lässt sichrekursiv implementieren. Wenn das mittlere Element kleiner als das gesuchte Element ist, wird die hintere Hälfte des Arrays rekursiv durchsucht. Wenn es größer als das gesuchte Element ist, wird die vordere Hälfte des Arrays rekursiv durchsucht. Ist es gleich dem gesuchten Element, ist die Suche beendet.

Die Abbruchbedingung für dieRekursion ist erfüllt, wenn das mittlere Element gleich dem gesuchten Element ist, die Suche also erfolgreich ist, oder wenn der Endindex kleiner als der Startindex ist, die Suche also erfolglos ist.

Die folgendeFunktion (Methode) für dierekursive binäre Suche ist in derProgrammiersprache C#:

intRekursiveBinaereSuche(int[]werte,intgesuchterWert,intstartIndex,intendIndex){if(endIndex<startIndex){// Wenn Element nicht gefunden, dann null zurückgebenreturnnull;}intmittlererIndex=(startIndex+endIndex)/2;if(werte[mittlererIndex]==gesuchterWert){// Wenn Element gefunden, dann Index zurückgebenreturnmittlererIndex;}else{if(werte[mittlererIndex]<gesuchterWert){// Rekursiver Aufruf der Funktion für die hintere HälftereturnRekursiveBinaereSuche(werte,gesuchterWert,mittlererIndex+1,endIndex);}else{// Rekursiver Aufruf der Funktion für die vordere HälftereturnRekursiveBinaereSuche(werte,gesuchterWert,startIndex,mittlererIndex-1);}}}

Effizienz

[Bearbeiten |Quelltext bearbeiten]

Rekursive Programme haben in der Regel keine gutePerformance. Durch die wiederholten Funktionsaufrufe (Inkarnationen) wird immer wieder derselbe Methodeneintrittscode bearbeitet und bei jeder Inkarnation derKontext gesichert, was zu zusätzlichemProgrammcode und höheremArbeitsspeicherverbrauch führt. Alle rekursivenAlgorithmen lassen sich jedoch auch durchiterative Programmierung implementieren und umgekehrt.

Fakultät

[Bearbeiten |Quelltext bearbeiten]

Man hätte dieFakultät auch soimplementieren können:

functionfactorial(x:Integer):Integer;vari,number:Integer;beginnumber:=1;fori:=1toxdonumber:=number*i;factorial:=number;end;

Hierbei gilt die Regel, dass für einfache Probleme eineiterative Implementierung häufig effizienter ist. So sollte z. B. auch die Fakultätsfunktion der Effizienz wegen in der Praxis iterativ implementiert werden. Bei komplizierten Problemstellungen (z. B. Aufgaben mitBäumen) hingegen lohnt sich oftmals der Einsatz einer rekursiven Lösung, da für solche Probleme eine iterative Formulierung schnell sehr unübersichtlich – und ineffizient – werden kann, da im schlimmsten Fall derStack durch den iterativenAlgorithmus selbst verwaltet werden muss, was sonst derProzessor direkt erledigt.

Nicht allehöheren Programmiersprachen lassen rekursive Aufrufe zu. Ein Beispiel dazu ist älteresFortran. Ab Fortran 90 sind rekursive Aufrufe möglich. AndereProgrammiersprachen sind dagegen grundsätzlich rekursiv (wie z. B.Prolog). Solche rekursiven Programmiersprachen und auch andere Sprachen wie z. B.Scheme setzen dieRekursion meistens effizient um.

Implementierung

[Bearbeiten |Quelltext bearbeiten]

Rekursion wird in der Regel durch einenStack implementiert, der die Rücksprungadressen, aber auch alle lokalen Variablen und eventuell Funktionsergebnisse aufnimmt. Würde man, wie im obenstehenden Beispiel, dieFakultät von 4 berechnen, so würde jeder Aufruf folgende Informationen auf den Stack legen:

Platz für Ergebnis
Argumentx
Rücksprungadresse

Zunächst würde im Hauptprogramm alsofac(4) aufgerufen und damit die folgenden Informationen auf denStack gelegt:

Stapelanfang	$\rightarrow$	1	Platz für Ergebnis
		2	4 (Argument)
Stapelzeiger	$\rightarrow$	3	Rücksprungadresse ins Hauptprogramm

Die Fakultätsfunktion prüft jetzt, ob das Argument 0 ist. Da dies nicht der Fall ist, wird4*fac(3) berechnet. Zunächst muss alsofac mit dem Argument 3 aufgerufen werden:

Stapelanfang	$\rightarrow$	1	Platz für Ergebnis
		2	4 (Argument)
		3	Rücksprungadresse ins Hauptprogramm
		4	Platz für Ergebnis
		5	3 (Argument)
Stapelzeiger	$\rightarrow$	6	Rücksprungadresse in die Fakultätsfunktion

Das Argument ist wieder ungleich 0, also geht’s weiter mit3*fac(2).

Stapelanfang	$\rightarrow$	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	$\rightarrow$	9	Rücksprungadresse in die Fakultätsfunktion

Das Argument ist wieder ungleich 0, also2*fac(1).

Stapelanfang	$\rightarrow$	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	$\rightarrow$	12	Rücksprungadresse in die Fakultätsfunktion

Das Argument ist wieder ungleich 0, also1*fac(0).

Stapelanfang	$\rightarrow$	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	$\rightarrow$	15	Rücksprungadresse in die Fakultätsfunktion

Jetzt ist das Argument 0, das Ergebnis also 1. Wir holen die Rücksprungadresse und das Argument vomStack und schreiben die 1 in den dafür vorgesehenen Platz. DerRücksprung führt in die Fakultätsfunktion zurück:

Stapelanfang	$\rightarrow$	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	$\rightarrow$	13	1 (Ergebnis)

Jetzt kann man das Ergebnis mit dem Argument multiplizieren (1*1). Das neue Ergebnis ist wieder 1. DieRücksprungadresse und das Argument werden vomStack geholt und das neue Ergebnis in den dafür vorgesehenen Platz geschrieben.Rücksprung in die Fakultätsfunktion:

Stapelanfang	$\rightarrow$	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	$\rightarrow$	10	1 (Ergebnis)

Wiederum wird das Ergebnis mit dem Argument multipliziert (1*2). Zurück in die Fakultätsfunktion:

Stapelanfang	$\rightarrow$	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	$\rightarrow$	7	2 (Ergebnis)