Rekursive Programmierung

Der Artikl is im Dialekt Obaboarisch gschriem worn.

Mit rekursiver Programmierung is gmoant daß a Problemlösung se säiba zua Problemlösung heanimmt. S' is a Sondervoi vo da Vorgehensweis a groß Problem in kloanere Probleme und de ollawei weida zum zaleng, bis ma bei oafache lösbare Probleme oglangt is. Ma bracht dazua a prozedurale Programmiersprach, de as rekursive Aufruafa vo Prozedurn und Funktiona zualost.

Beispui

A klassischs Beispui is de Brechnung vo da Fakultät:

$n!=1\cdot 2\cdot 3\cdot \ldots \cdot n$

des guid via olle ganzn positivn Zoin ohne d'Null (des han de natürlichn Zoin).

Desweidan is festglegt:

$0!=1.$

De naheliegende Lösung warad mit na Schleifn (S'Beispui is in Pascal gschriem)

function Fakultaet(Eingabe: integer): integer;
 var
   Schleife: integer;
 begin
   result := 1;
   for Schleife := 1 to Eingabe
     do result := result * Eingabe;
 end;

Eha zufällig und recht unelegant kriagt ma dodamit a as richtige Ergebnis fia a Eingabe vo Null. A Schleifn vo 1 bis 0 werd gor ned duachlaffa, as Ergebnis is aba scho ois oans festglegt worn.

Wenn ma wia friara mäglichst wenig Variablen eisetzn mog, ko ma's Problem a umdrahn und mit da heachstn Zoi ofanga. In dem Foi bracht ma no a deitliche Regel fia de Null, mit da Schleifn alloans dad ma ois Ergebnis fia Null a Null rauskriang.

function Fakultaet(Eingabe: integer): integer;
 begin
   if Eingabe = 0
     then result := 1
     else begin
       result := Eingabe;
       while (Eingabe > 0)
         do begin
            Eingabe := Eingabe - 1;
            result := result * Eingabe;
         end;
     end;
 end;

Wenn ma a boar Klammern in de Forml schreibt

$5!=(((1\cdot 2)\cdot 3)\cdot 4)\cdot 5$

ko ma erkenna:

$5!=4!\cdot 5$

$4!=3!\cdot 4$

$3!=2!\cdot 3$

$2!=1!\cdot 2$

Da Voiständigheid hoiba kimmt no

$1!=0!\cdot 1$

$0!=1$

dazua.

S' Problem Fakultät vo Null lost se ganz oafach per Definition mit am Ergebnis Oans lösn. Olle andern Probleme Fakultät vo n mit n>0 lossn se weida zleng in

$n!=(n-1)!\cdot n$

De Umsetzung in Pascal:

function Fakultaet(Eingabe: integer): integer;
 begin
   if Eingabe = 0
     then result := 1
     else result := Fakultaet(Eingabe - 1) * Eingabe;
 end;

De Lösung is de kiarzeste und bracht koane zusätzlichn Variablen.

Effizienz

Rekursive Programmierung is oft via an Programmierer effizient, wei se dadurch an Haffa Probleme iabasichtlich und elegant lösn lossn. De Abarbeitung vo so am Programm is aba ned so effizient wia andane Lösunga. In dem Beispui ham ma uns auf'n erstn Blick zwor de Schleifnvariable gsparrt, dodafia muaß da Rechner jetz a ganze Kettn vo Funktionsaufrufn vawoidn. Des Beispui mit da for-Schleifn bracht ollawei gleich vui Speicherplatz, s' bracht nua umso länger, je häha de Eingabe is. As rekursive Beispui bracht imma mehra Speicherplatz, entsprechend da Hech vo da Eingab.