Rekursive Programmierung

Der Artikl is im Dialekt Obaboarisch gschriem worn.

Mit rekursiver Programmiarung is gmoant dass a Problemlösung se sejba 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 Programmiasprach, 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 dodomid 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 mas 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 > 1)
         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 Programmiarung is oft via an Programmiara 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 easchtn Blick zwor de Schleifnvariable gsparrt, dodafia muaß da Rechna 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.

Oafache Aufgam han mit Schleifn auf jedn Foi effektiver zum Lösn. Bei aufwendigere Probleme ko zwar a Lösung, de auf Rekursiona vazicht a schneja sei, aba de is oft ned mit am vatretbarn Aufwand zum programmiern.

Rekursive Programmierung mit mehrare Funktiona

Es ko a zwoa oda mehra Funktiona gem, de se gegnseitig aufruafa. A des is dann a rekursive Programmiarung. A Beispui:

function Grod(Eingabe: integer): boolean;
 begin
   if Eingabe = 0
     then result := true
   else result := Ungrod(Eingabe - 1);
 end;

function Ungrod(Eingabe: integer): boolean;
 begin
   if Eingabe = 0
     then result := false
   else result := Grod(Eingabe - 1);
 end;

A Zoi is ungrod, wenn de Zoi - 1 grod is und umkehrt. Fia de Zoi 0 guid dass grod is, oiso kriagt ma vo Grod(0) den Wert "true" oiso wahr zruck und vo Ungrod(0) "false" oiso foisch.

Zum End kemma

Sakrisch aufpassn muaß ma, dass de Funktion auf jedn Foi irawanamoi zua am End kimmt. Es muaß auf jedn Foi dea Punkt erreicht wern, wo de Funktion ihra Antwort gem ko, ohne a weidas moi se sejba oda a andre mit ihra sejba vakettete Funktion aufrufa zmiaßn. Bei schwierigere Probleme is des ned so oafach Sichazumstelln, dass des mit jeda denkbarn Eingabe zua am Ergebnis kimmt. In da Theorie dads glanga, das ma irawanamoi zua am Ergebnis kimmt. In da Realität vabracht a jeda Funktionsaufruf weidan Speichaplotz und domit ko a Rekursion an Rechna scho relativ schnej zum Afgem zwinga. A grobe Grenz han 10000 Rekursionsschritt.

Mißbrauch fia Rechner-Sabotage

Archiv-Bombn

In gepacktn Archiv-Datein (z. B. ZIP) kenna gepackte Archiv-Dateien steckn. Des is a a Art vo Rekursion. Mit etwas Gschick ko ma so a Datei erstelln, de sejba recht kloa is, aba entpackt riesig groß. Da Trick is dabei, daß da angebliche Inhoid was sinnlos is, des si aba schee komprimiern loßt. A bekannts Beispui is de Datei 42.zip, de 42kByte groaß is, aba entpackt 4,5 Petabyte enthoid. Mit so na Archiv-Bombn ko ma jedn Rechna lahmlegn, auf dem vasuacht werd, de Datei zum öffnen. Der Ogriff zuid auf Anti-Viren-Software, wei de normalaweis Archiv-Dateien entpackt, um an Inhoid auf Viren untasuacha z'kinna.

Fork-Bombn

Da Begriff kimmt aus da Unix-Woid, wo a Programm mit dem Befehl "Fork" a Kopie vo si sejbst startn ko. Aba a in andere Betriebssysteme kenna Programme si sejba aufruafa, wos a wiada a Rekursion dorstellt. Wenn ma a Programm schreibt, des si sejba zwoa moi aufruaft und dann drauf wart, daß de aufgruafna Programme beendt wern ko ma domid a an jedn Rechna blockiern. Innahoib vo kiazasta Zeit hod ma zig-Tausend Instanzn vo dem Programm laffa, de sämtlichn Speicher und de Rechnaleistung vabracha.

Vawandte Themen

S' gibt a rekursive Abkiarzunga, do steht dann da easchte Buachstob vo da Abkiarzung via de ganze Abkiarzung. Soiche Abkiarzunga han grod bei Programmiara und in da Rechna-Wejd beliebt, wei de Leid des Konzept vo da Rekursion so spannend findn. A boar Beispui:

GNU: GNU is not Unix
Pine: P'ine is not Elm (Pine is a Linux-E-Mail-Programm und da Nachfolger vo Elm)
ATI: ATI Technologies Inc (A Firma, de Grafikkortn baut)