Rekursion: Unterschied zwischen den Versionen

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche
K (- Kurzinfo Java)
(f)
Zeile 1: Zeile 1:
{{Zitat wpde|
 
 
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.
 
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.
  
 
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.
 
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).
+
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.  
|Rekursion|21.11.2006}}
+
  
==Beispiel==
+
== Beispiel ==
  
 
  Fakultät:
 
  Fakultät:
Zeile 34: Zeile 32:
  
  
==Listenausgabe==
+
== Listenausgabe ==
 
(Setzt [[Java/List]] o.ä. voraus)
 
(Setzt [[Java/List]] o.ä. voraus)
  
Zeile 53: Zeile 51:
 
{{Übung|
 
{{Übung|
 
* Vergleichen Sie die iterativen und rekursiven Fakultätsmethoden-Varianten. Übersetzen Sie den Pseudo-Code in Java.
 
* 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.
+
* 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.
 
* Recherchieren Sie nach weiteren Beispielen.
 
}}
 
}}
Zeile 59: Zeile 57:
  
 
[[Kategorie:Java]]
 
[[Kategorie:Java]]
[[Kategorie:Linksammlung]]
 
[[Kategorie:Unterrichtsideen/Informatik]]
 

Version vom 27. August 2019, 20:49 Uhr

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.

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.

Inhaltsverzeichnis

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)

    private void rekursiveAusgabe() {
        if (liste.isBehind()){
            System.out.println("Fertig.");
        }
        else {
            System.out.println(liste.getItem()+"\n"); 
            liste.next();
            rekursiveAusgabe();
            System.out.println("*");
        }
    }
Hand.gif   Ü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.