< Java(Unterschied zwischen Seiten)
main>Ugh |
|
| Zeile 1: |
Zeile 1: |
| {{Babel-2|Java|Links}}
| | <div class="uk-panel" style="width:20ch"> |
| {{Zitat wpde|
| | <div class="uk-border-circle">{{#avatar:{{{1|{{REVISIONUSER}}}}}|s}}</div> |
| Als '''Rekursion''' (auch Rekurrenz oder Rekursivität), von lateinisch recurrere entspr. zurücklaufen, bezeichnet man den Aufruf oder die Definition einer Funktion durch sich selbst. Die gegenseitige Rekursion bildet sich durch den gegenseitigen Verweis zweier oder mehrerer Funktionen auf einander.
| | <div class="uk-center">[[Benutzer:{{{1|{{REVISIONUSER}}}}}|{{{1|{{REVISIONUSER}}}}}]]</div> |
| | | </div> |
| In vielen Fällen ist die Rekursion eine von mehreren möglichen Problemlösungsstrategien, sie führt oft zu eleganten mathematischen Lösungen. In der Regel sind rekursive Programme (als Darstellung eines rekursiven Problems) zwar wesentlich kompakter (also kürzer) als die iterativen Varianten, dafür sind sie etwas langsamer und der Speicheraufwand ist höher.
| |
| | |
| Ohne geeignete Abbruchbedingung geraten solche rückbezüglichen Aufrufe in einen so genannten infiniten Regress (umgangssprachlich Endlosschleife). Zur Vermeidung von infinitem Regress insbesondere in Computerprogrammen bedient man sich der semantischen Verifikation von rekursiven Funktionen. Der Beweis, dass kein infiniter Regress vorliegt, wird dann zumeist mittels einer Schleifeninvariante geführt (siehe auch Invariante). Dieser Beweis ist allerdings nicht immer möglich (siehe Halteproblem).
| |
| |Rekursion|21.11.2006}}
| |
| | |
| ==Beispiel== | |
| | |
| Fakultät:
| |
| 5! = 1 * 2 * 3 * 4 * 5
| |
| | |
| ===rekursiv===
| |
| 1 fakultät_rekursiv(n)
| |
| 2 {
| |
| 3 wenn n <= 1
| |
| 4 dann return 1
| |
| 5 sonst return ( n * fakultät_rekursiv(n-1) )
| |
| 6 }
| |
| | |
| ===iterativ===
| |
| 1 fakultät_iterativ(n)
| |
| 2 {
| |
| 3 fakultät = 1
| |
| 4 faktor = 2
| |
| 5 solange faktor <= n
| |
| 6 {
| |
| 7 fakultät = fakultät * faktor
| |
| 8 faktor = faktor + 1
| |
| 9 }
| |
| 10 return fakultät
| |
| 11}
| |
| | |
| | |
| ==Listenausgabe== | |
| (Setzt [[Java/List]] o.ä. voraus)
| |
| | |
| <java>
| |
| private void rekursiveAusgabe() {
| |
| if (liste.isBehind()){
| |
| System.out.println("Fertig.");
| |
| }
| |
| else {
| |
| System.out.println(liste.getItem()+"\n");
| |
| liste.next();
| |
| rekursiveAusgabe();
| |
| System.out.println("*");
| |
| }
| |
| }
| |
| </java>
| |
| | |
| {{Übung| | |
| * Vergleichen Sie die iterativen und rekursiven Fakultätsmethoden-Varianten. Übersetzen Sie den Pseudo-Code in Java.
| |
| * Analysieren Sie die oben stehende Methode rekursiveAusgabe(). Gehen Sie dabei vor allem auch auf die Bildschirmausgabe der Sternchen ein.
| |
| * Recherchieren Sie nach weiteren Beispielen.
| |
| }} | |
| | |
| [[Kategorie:Java]]
| |
Version vom 19. September 2019, 19:39 Uhr
