Rekursion

Rekursion, Aufruf einer Prozedur oder Funktion durch sich selbst.

Damit keine unendliche Folge von Prozeduraufrufen entsteht, muß es einen Rekursionsanfang geben, bei dem kein weiterer Prozeduraufruf nötig ist.

Iteration, Berechnung innerhalb einer Schleife unter Verwendung der im vorherigen Schleifendurchlauf berechneten Werte.

Jedes rekursive Programm kann in ein iteratives Programm umgeschrieben werden. Manche Probleme lassen sich wesentlich einfacher und natürlicher rekursiv lösen.

Die Fakult„ät ist definiert durch

Dies läßt sich sofort in eine rekursive Funktion umschreiben:

   FUNCTION fakul(n: integer): real;
   BEGIN
      IF n>0 THEN fakul:=fakul(n-1)*n   (* Rekursion *) 
      ELSE IF n=0 THEN fakul:=1  (* Rekursionsanfang *) 
      ELSE writeln('Fehler');
   END;

In diesem Fall ist eine iterative Lösung einfacher und zu bevorzugen:

   FUNCTION fakul(n: integer): real; 
   VAR i: integer; f: real; 
   BEGIN
      f:=1; 
      FOR i:=1 TO n DO f:=f*i; 
      fakul:=f;
   END;

Beachte bei der rekursiven Lösung, daß die lokale Variable n mit jedem erneuten Aufruf von fakul neu angelegt wird und daher nach jedem Rücksprung den gleichen Wert besitzt wie vor dem entsprechenden Aufruf.

Rekursion liegt auch dann vor, wenn eine Prozedur sich nicht direkt, sondern indirekt über eine andere Prozedur aufruft. Schwierigkeit dabei: Jede Prozedur muß vor ihrer ersten Verwendung definiert sein.

In diesem Beispiel ist beim Aufruf von b innerhalb von a die Prozedur b noch nicht definiert. Vertauschen der Reihenfolge von a und b nützt nichts, da dann a innerhalb von b undefiniert wäre.

Abhilfe: FORWARD -Deklaration der Prozedur vor der ersten Verwendung.

Parameterliste und (bei Funktionen) Funktionswerttyp werden nur bei der FORWARD -Deklaration angegeben. Wenn die Prozedur schließlich wirklich definiert wird, werden diese Angaben nicht mehr wiederholt.

Rekursionen sind nicht in allen Programmiersprachen erlaubt. PASCAL und C erlauben Rekursionen, während sie n vielen FORTRAN -Dialekten verboten sind.