Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenFreitag, 31. Oktober 2014 

Rekursion


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Rekursion bedeutet Selbstbezüglichkeit (von lat. recurrere = zurücklaufen). Sie tritt immer dann wenn etwas auf sich selbst verweist. Ein Element muss nicht direkt auf sich selbst eine Rekursion kann auch über mehrere Zwischenschritte Rekursion kann dazu führen dass merkwürdige Schleifen So ist z.B. der Satz "Dieser Satz unwahr" rekursiv da er von sich selber Eine etwas subtilere Form der Rekursion kann wenn zwei Dinge gegenseitig aufeinander verweisen. Ein sind die beiden Sätze: "Der folgende Satz wahr" "Der vorhergehende Satz ist nicht wahr". Probleme beim Verständnis von Rekursion beschreibt der "Um Rekursion zu verstehen muss man erst Rekursion verstehen".

Rekursion ist ein allgemeines Prinzip zur Lösung von Problemen. In vielen ist die Rekursion eine von mehreren möglichen sie führt oft zu "eleganten" mathematischen Lösungen. Als Rekursion bezeichnet man den Aufruf oder die einer Funktion durch sich selbst. Ohne geeignete Abbruchbedingung geraten solche rückbezüglichen Aufrufe in einen genannten infiniten Regress.

( Hinweis vorab: Rekursion oder rekursive Definitionen sind auf natürliche Zahlen -definierte Funktionen beschränkt. Hier sei auf das Rekursionsschema verwiesen. )

Die Grundidee der rekursiven Definition einer Funktion f ist: Der Funktionswert f (n+1) einer Funktion f : N 0 N 0 ergibt sich durch Verknüpfung bereits vorher berechneter Werte f (n) f (n-1) ... Falls außerdem die Funktionswerte von f für hinreichend viele Startargumente bekannt sind jeder Funktionswert von f berechnet werden. Das heißt im Klartext: einer rekursiven Definition einer Funktion f ruft sich die Funktion so oft auf bis ein vorgegebenes Argument (meistens 0) ist so dass die Funktion terminiert (sich

Die Definition von rekursiv festgelegten Funktionen eine grundsätzliche Vorgehensweise in der funktionalen Programmierung . Ausgehend von einigen gegebenen Funktionen (wie die Summen-Funktion) werden neue Funktionen definiert mithilfe weitere Funktionen definiert werden können.

Hier ein Beispiel für eine Funktion sum : N 0 N 0 die die Summe der ersten n Zahlen berechnet:

Die Funktion sum sei definiert durch: sum (n) = 0 + 1 + 2 n
oder besser: sum (n) = sum (n-1) + n ( Rekursionsschritt )
Das heißt also die Summe der n Zahlen lässt sich berechnen indem man Summe der ersten n - 1 Zahlen berechnet und dazu Zahl n addiert. Damit die Funktion terminiert legt hier für sum (0) = 0 ( Rekursionsanfang ) fest. Mit diesen Angaben lässt sich rekursive Definition angeben die eine beliebige (hier: natürliche ) Zahl x berechnet. Die Definition lautet also:

<math>\mathrm{sum}(n) = \left\{\begin{matrix} 0 && \mbox{falls && \mbox{(Rekursionsanfang)} \\ \mathrm{sum}(n-1)+n && \mbox{falls } \ge 1 && \mbox{(Rekursionsschritt)} \end{matrix}\right.</math>

Es gilt nun zum Beispiel:

<math>\begin{matrix}
\mathrm{sum}(3) & = & \mathrm{sum}(2)+3 & \\
 & = & \mathrm{sum}(1)+2+3 & \mbox{(Rekursionsschritt)} & = & \mathrm{sum}(0)+1+2+3 & \mbox{(Rekursionsschritt)} \\ = & 0+1+2+3 & \mbox{(Rekursionsanfang)} \\ & & 6  
\end{matrix}</math>

Ein Spezialfall der Rekursion ist die Iteration . Eine Iteration tritt auf wenn eine sich selbst nur am Anfang oder nur Ende ( Endrekursion ) innerhalb der Funktion aufruft.

In der Theoretischen Informatik spielen primitiv-rekursive Funktionen eine wichtige Rolle. Im Compilerbau ist der rekursive Abstieg eine Technik der eine Computersprache rekursiv geparst wird.



Bücher zum Thema Rekursion

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Rekursion.html">Rekursion </a>