Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
  


informatik artikel (Interpretation und charakterisierung)

Berechnung von gliedern rekursiver folgen


1. Java
2. Viren



Das wohl naheliegendste Einsatzgebiet ist das Berechnen von Gliedern rekursiver Folgen. Hier bietet sich der Eisatz von rekursiven Funktionen an, die selbst einen Wert annehmen können. Beim Aufruf der Funktion muß überprüft werden, ob die als Parameter übergebene Nummer des Gliedes Eins ist. Wenn dies der Fall ist, wird der Funktion der Wert für a1 übergeben und die Funktion beendet. Andernfalls wird der Funktion ein Wert zugewiesen, der aus einer Berechnung mit dem Funktionswert des vorhergehenden Gliedes resultiert, was einen Selbstaufruf mit dem um eins verringerten Parameter zur Folge hat - der Vorgang beginnt von neuem.
Im Folgenden sollen zwei Beispiele näher betrachtet werden:


3.1.1 Die Fakultätsfunktion

Die Glieder der Fakultätsfunktion erhält man, indem man alle ganzen Zahlen von 1 bis inklusive der Nummer des zu berechnenden Gliedes multipliziert. So ergibt sich für das dritte Glied zum Beispiel 6, für das fünfte schon 120. Die Fakultätsfunktion läßt sich leicht in der rekursiven Form darstellen: an = n * a(n-1), wobei das erste Glied den Wert Eins besitzt. Auf diesem Bildungsgesetz basiert das folgende Programm:

program fakultaet;

uses crt;
var i : integer;

function fakt(n : integer) : real;
begin
if n=1 then fakt:=1 else fakt:=fakt(n-1)*n;

end;

begin
clrscr;
writeln(\' Fakultätsberechnungsprogramm von Stefan Krywult\');
write(\'n = \');

readln(i);
writeln(i,\'! = \',fakt(i));

readln;
clrscr;

end.

Zunächst gibt der Benützer die Zahl ein, deren Fakultät berechnet werden soll. Sie wird in der Integervariablen i zwischengespeichert und dann der rekursiven Funktion fakt als mit n bezeichneter Parameter übergeben. Nun beginnt eine rekursive Schleife: Solange n größer als eins ist, erfolgen Selbstaufrufe, und die Werte, welche die Funktion dabei zurückliefert, werden mit dem jeweils gültigen n multipliziert. Ist n gleich eins, wird der Funktion der Wert Eins zugewiesen.
Nun folgt der genaue Ablauf der Rekursion, wenn als Startparameter Drei übergeben wurde:

Rekursionsebene: 1 n = 3 n 1 fakt := fakt(2)*3
Rekursionsebene: 2 n = 2 n 1 fakt := fakt(1)*2
Rekursionsebene: 3 n = 1 n = 1 fakt := 1
Rekursionsebene: 2 n = 2 n 1 fakt := 1*2 fakt := 2
Rekursionsebene: 1 n = 3 n 1 fakt := 2*3 fakt := 6 => fakt(3) = 6



3.1.2 Die Ackermann-Funktion

Wesentlich schwerer ist es, die Ackermann-Funktion zu berechnen. Sie ist eine zweidimensionale Funktion, das heißt, sie benötigt zwei Parameter. Ihr Bildungsgesetz sieht so aus:


n + 1 für m = 0, n > 0
A(m,n) = A(m-1, 1) für m > 0, n = 0

A(m-1, A(m, n-1)) für m > 0, n > 0


Doch auch diese Funktion läßt sich fast nach dem selben Schema wie die Fakultätsfunktion programmieren: Zuerst muß ermittelt werden, welcher der drei Fälle vorliegt (bei der Fakultät waren es nur zwei: n=1 oder n>1). Dann erfolgt entweder ein Selbstaufruf mit den entsprechenden Parametern oder die einfache Berechnung A=n+1.
Mit folgender Pascalfunktion lassen sich Werte der Ackermann-Funktion berechnen, der restliche Programmcode kann dem Anhang entnommen werden (A1, "ackermann"):


function ack(m, n : integer) : integer;
begin

If (m=0) and (n>0) then ack := n+1
If (m>0) and (n=0) then ack := ack(m-1,1);
If (m>0) and (n>0) then ack := ack(m-1, ack(m,n-1));
end;

Der Rekursionsablauf ist bei dieser Funktion nur schwer zu durchschauen, da sie sich oftmals sogar zweimal selbst aufruft: Sie ruft sich auf, um den Parameter für den eigentlichen Selbstaufruf zu erhalten. Da die Wahrscheinlichkeit, daß beide Parameter größer als Eins sind, ziemlich groß ist, verzweigt sich die Funktion häufig.
Das heißt: Die Funktion ruft sich zweimal auf, diese beiden Funktionen rufen sich wieder zweimal auf und so weiter. Die Zahl der Selbstaufrufe wächst daher stetig. Die rekursive Berechnung der Ackermann-Funktion ist deshalb sehr zeit- und speicherintensiv. Hier wäre es günstiger, die wesentlich schwierigere, aber zeit- und speichersparende iterative Variante zu wählen.
Um den komplizierten Ablauf der Funktionsberechnung zu zeigen, folgt nun die Beschreibung des Ablaufes nach dem Funktionsaufruf ack(1, 1):

Rekursionsebene: 1 m = 2 n = 1 m > 0 n > 0 ack := ack(1, ack(2,0))
Rekursionsebene: 2 m = 2 n = 0 m > 0 n = 0 ack := ack(1, 1)
Rekursionsebene: 3 m = 1 n = 1 m > 0 n > 0 ack := ack(0,ack(1,0))
Rekursionsebene: 4 m = 1 n = 0 m > 0 n = 0 ack := ack(0,1)
Rekursionsebene: 5 m = 0 n = 1 m = 0 n > 0 ack := 1+1 ack := 2
Rekursionsebene: 4 m = 1 n = 0 m > 0 n = 0 ack := 2
Rekursionsebene: 3 m = 1 n = 1 m > 0 n > 0 ack := ack(0, 2);
Rekursionsebene: 4 m = 0 n = 2 m = 0 n > 0 ack := 2 + 1 ack := 3
Rekursionsebene: 3 m = 1 n = 1 m > 0 n > 0 ack := 3
Rekursionsebene: 2 m = 2 n = 0 m > 0 n > 0 ack := 3
Rekursionsebene: 1 m = 2 n = 1 m > 0 n > 0 ack := ack(1, 3)
Rekursionsebene: 2 m = 1 n = 3 m > 0 n > 0 ack := ach(0, ack(1, 2))
Rekursionsebene: 3 m = 1 n = 2 m > 0 n > 0 ack := ach(0, ack(1, 1))
Rekursionsebene: 4 m = 1 n = 1 m > 0 n > 0 ack := ach(0, ack(1, 0))
Rekursionsebene: 5 m = 1 n = 0 m > 0 n = 0 ack := ach(0, 1)
Rekursionsebene: 6 m = 0 n = 1 m = 0 n > 0 ack := 1+1 ack := 2
Rekursionsebene: 5 m = 1 n = 0 m > 0 n = 0 ack := 2
Rekursionsebene: 4 m = 1 n = 1 m > 0 n > 0 ack := ach(0, 2)
Rekursionsebene: 5 m = 0 n = 2 m = 0 n > 0 ack := 2 + 1 ack := 3
Rekursionsebene: 4 m = 1 n = 1 m > 0 n > 0 ack := 3
Rekursionsebene: 3 m = 1 n = 2 m > 0 n > 0 ack := ach(0, 3)
Rekursionsebene: 4 m = 0 n = 3 m > 0 n > 0 ack := 3 + 1 ack := 4
Rekursionsebene: 3 m = 1 n = 2 m > 0 n > 0 ack := 4
Rekursionsebene: 2 m = 0 n = 3 m > 0 n > 0 ack := ach(0, 4)
Rekursionsebene: 3 m = 0 n = 4 m = 0 n > 0 ack := 4 +1 ack := 5
Rekursionsebene: 2 m = 0 n = 3 m > 0 n > 0 ack := 5
Rekursionsebene: 1 m = 2 n = 1 m > 0 n > 0 ack := 5

 
 



Datenschutz
Top Themen / Analyse
indicator Rechenmaschine von Wilhelm Schickard
indicator Parallele Schnittstelle -
indicator Internet --- -
indicator Linux als Server
indicator Netz-Topologien
indicator News
indicator Windows-
indicator Antiviren bzw. Schutz:
indicator Das Phase-Change-Verfahren
indicator ANSI C




Datenschutz
Zum selben thema
icon Netzwerk
icon Software
icon Entwicklung
icon Windows
icon Programm
icon Unix
icon Games
icon Sicherheit
icon Disk
icon Technologie
icon Bildung
icon Mp3
icon Cd
icon Suche
icon Grafik
icon Zahlung
icon Html
icon Internet
icon Hardware
icon Cpu
icon Firewall
icon Speicher
icon Mail
icon Banking
icon Video
icon Hacker
icon Design
icon Sprache
icon Dvd
icon Drucker
icon Elektronisches
icon Geschichte
icon Fehler
icon Website
icon Linux
icon Computer
A-Z informatik artikel:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #

Copyright © 2008 - : ARTIKEL32 | Alle rechte vorbehalten.
Vervielfältigung im Ganzen oder teilweise das Material auf dieser Website gegen das Urheberrecht und wird bestraft, nach dem Gesetz.
dsolution