Rekursion: Unterschied zwischen den Versionen

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche
(Akt)
({{Seite umgezogen}})
 
Zeile 1: Zeile 1:
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.
+
{{Seite umgezogen}}
 
+
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.
+
 
+
{{Übung|
+
* Vergleichen Sie die iterativen und rekursiven Fakultätsmethoden-Varianten. Übersetzen Sie den Pseudo-Code in Java.
+
* Analysieren Sie die oben stehende Methode <code>rekursiveAusgabe()</code>. Gehen Sie dabei vor allem auch auf die Bildschirmausgabe der Sternchen ein.
+
* Recherchieren Sie nach weiteren Beispielen.
+
}}
+
== 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)
+
 
+
<source lang="java">
+
    private void rekursiveAusgabe() {
+
        if (liste.isBehind()){
+
            System.out.println("Fertig.");
+
        }
+
        else {
+
            System.out.println(liste.getItem()+"\n");
+
            liste.next();
+
            rekursiveAusgabe();
+
            System.out.println("*");
+
        }
+
    } 
+
</source>
+
 
+
== Siehe auch ==
+
 
+
* [[Rekursion]]
+
 
+
 
+
[[Kategorie:Java]]
+

Aktuelle Version vom 30. August 2019, 18:56 Uhr

Diese Seite wurde in das neue Projekt ZUM Unterrichten umgezogen.

ZUM Unterrichten ist das neue Projekt der ZUM e.V. für die interaktive Erstellung von Lerninhalten.

Diese Seite findet sich ab sofort unter: https://unterrichten.zum.de/Java/Rekursion