Rekursive Programmierung

Der Artikl is im Dialekt Obaboarisch gschriem 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

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

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

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 dad's 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.

Vawandte Themen

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: Pine 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