Rekursion: Unterschied zwischen den Versionen

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche
(f)
(Akt)
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.
+
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.
Zeile 5: Zeile 5:
 
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.  
 
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 ==
 
== Beispiel ==
  
Zeile 10: Zeile 15:
 
  5! = 1 * 2 * 3 * 4 * 5
 
  5! = 1 * 2 * 3 * 4 * 5
  
===rekursiv===
+
== rekursiv ===
 
  1 fakultät_rekursiv(n)
 
  1 fakultät_rekursiv(n)
 
  2 {
 
  2 {
Zeile 18: Zeile 23:
 
  6 }
 
  6 }
  
===iterativ===
+
=== iterativ ===
 
  1 fakultät_iterativ(n)
 
  1 fakultät_iterativ(n)
 
  2 {
 
  2 {
Zeile 49: Zeile 54:
 
</source>
 
</source>
  
{{Übung|
+
== Siehe auch ==
* 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.
+
* [[Rekursion]]
* Recherchieren Sie nach weiteren Beispielen.
+
}}
+
  
  
 
[[Kategorie:Java]]
 
[[Kategorie:Java]]

Version vom 29. August 2019, 08:03 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.

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.

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("*");
        }
    }

Siehe auch