Rekursive Programmierung

Aus Wikipedia
Wexln zua: Navigation, Suach
Der Artikl is im Dialekt Obaboarisch gschrim worn.

Mit rekursiver Programmierung is gmoant dass 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[VE | Weakln]

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 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[VE | Weakln]

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.

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 schneller sei, aba de is oft ned mit am vatretbarn Aufwand zum programmiern.

Rekursive Programmierung mit mehrare Funktiona[VE | Weakln]

Es ko a zwoa oda mehra Funktiona gem, de se gegnseitig aufruafa. A des is dann a rekursive Programmierung. 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[VE | Weakln]

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 säiba oda a andre mit ihra säiba vakettete Funktion aufrufa zmiaßn. Bei schwierigere Probleme is des ned so oafach sicherzumstelln, 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 Speicherplatz und domit ko a Rekursion an Rechner scho relativ schnäi zum Aufgem zwinga. A grobe Grenz han 10000 Rekursionsschritt.

Mißbrauch fia Rechner-Sabotage[VE | Weakln]

Archiv-Bombn[VE | Weakln]

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 säiba 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 Rechner 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[VE | Weakln]

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

Vawandte Themen[VE | Weakln]

S' gibt a rekursive Abkiarzunga, do steht dann da erste Buachstob vo da Abkiarzung via de ganze Abkiarzung. Soiche Abkiarzunga han grod bei Programmierer und in da Rechner-Wäid 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 Grafikkarten baut)

Do kunst a no schaung[VE | Weakln]