Rekursion: Unterschied zwischen den Versionen

Aus EINI
Wechseln zu: Navigation, Suche
 
(7 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
−
Ein '''rekursiver''' Algorithmus oder Programm ist ein Alorithmus oder Programm, welches sich selber direkt oder indirekt aufruft. Jede Rekursion kann theoretisch durch eine Schleife ersetzt werden und umgekehrt, jedoch ist dies nicht immer ratsam. Schleifen und Rekursionen sind also semmantisch äquivalent. Rekursion kommt vom lateinischen Wort ''recurrere'', was ''zurücklaufen'' bedeutet.  
+
Als '''rekursiv''' wird ein [[Programm]] oder [[Algorithmus]] bezeichnet, das/der sich selbst direkt oder indirekt aufruft.
 +
Eine '''Rekursive Funktion''' ist demnach eine Funktion, die sich selbst aufruft.
  
−
===Erstes Beispiel für eine Rekursion===
+
Rekursionen und [[Schleifen]] sind semantisch äquivalent und können daher durch durch das jeweils andere ersetzt werden. Dies ist jedoch nicht immer sinnvoll.
 +
 
 +
'''Rekursion''' kommt vom lateinischen Wort ''recurrere'', was '''zurücklaufen''' bedeutet.
 +
 
 +
=Erstes Beispiel<ref> Alle Rekursionsbeispiele werden hier zum besseren Verständnis im sogenannten [[Pseudocode]] notiert.</ref>: Fakultät=
 +
 
 +
==Definition==
  
 
'''Fakultät von ''n'' '''
 
'''Fakultät von ''n'' '''
 +
 +
Die Fakultät einer Zahl ist das Produkt aller natürlichen Zahlen (außer 0), die kleiner oder gleich dieser Zahl sind. Fakultät wird mit einem Ausrufezeichen hinter der Zahl notiert. Die Fakultät von 0 ist 1 (0! = 1).
  
 
  Eingabe: Eine natürliche Zahl n
 
  Eingabe: Eine natürliche Zahl n
Zeile 12: Zeile 21:
 
     ansonsten gib das Produkt von ''n'' und dem Algorithmus mit der Eingabe ''n''-1 zurück.
 
     ansonsten gib das Produkt von ''n'' und dem Algorithmus mit der Eingabe ''n''-1 zurück.
  
−
===Ausführung des Beispiels mit ''n'' = 3===
 
  
−
  '''Aufbau der Rekusion ("Hinweg")'''
+
==Ausführung mit ''n'' = 3==
 +
 
 +
  '''Aufbau der Rekursion ("Hinweg")'''
 
   
 
   
 
  ''Ebene:'' n = 3
 
  ''Ebene:'' n = 3
Zeile 44: Zeile 54:
 
  ''Rückgabe:'' 3 * 2 = 6
 
  ''Rückgabe:'' 3 * 2 = 6
  
−
===Aufbau einer Rekursion===
 
  
−
Jede Rekursion besteht aus einer Abbruch-/Terminierungsbedingung und einem Rekusionsrumpf. Der Rekusionsabbruch erfolgt, wenn die Terminierungsbedingung erfüllt ist. Diese Bedingung überprüft, ob die untereste Ebene des Rekusionsbaums errreicht wurde. Im obigen Beispiel ist dies die Überprüfung, ob n gleich 0 ist, da 0! gleich 1 ist. Sollte diese Bedingung nicht erfüllt werden, wird der Rekusionsrumpf ausgeführt. Im Rekursionsrumpf geschieht der Aufruf der Funktion für eine niedrigere Ebene und die Berechnung des Ergebnisses der aktuellen Ebene mit diesem. In dem Beispiel ist dies der Ansonsten-Pfad. Wichtig für eine funktionierenden Rekursion ist, dass die Bedingung irgendwann erreciht wird, da ansonsten die Rekusion nicht terminiert, s. Endlosrekursion.
 
  
 +
Mathematisch notiert sieht das ganze folgendermaßen aus:
  
−
===Zweites Beispiel===
+
3! = 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 * 0! = 3 * 2 * 1 * 1 = 3 * 2 * 1 = 3 * 2 = 6
−
'''Ist die Zahl ''n'' grade?'''
+
 
 +
 
 +
=Aufbau=
 +
 
 +
Jede Rekursion besteht aus einer Abbruch-/Terminierungsbedingung und einem Rekursionsrumpf.
 +
 
 +
Der Rekursionsabbruch erfolgt, wenn die '''Terminierungsbedingung''' erfüllt ist. Diese Bedingung überprüft, ob die unterste Ebene des [[Baum|Rekursionsbaums]] erreicht wurde. Im obigen Beispiel ist dies die Überprüfung, ob n gleich 0 ist, da 0! gleich 1 ist. Sollte diese Bedingung nicht erfüllt werden, wird der Rekursionsrumpf ausgeführt. Wichtig für eine funktionierende Rekursion ist, dass die Bedingung irgendwann erreicht wird, da ansonsten die Rekursion nicht terminiert ('''Endlosrekursion''').
 +
 
 +
Im '''Rekursionsrumpf''' geschieht der Aufruf der Funktion für eine niedrigere Ebene und die Berechnung des Ergebnisses der aktuellen Ebene mit diesem. In dem Beispiel ist dies der Ansonsten-Pfad.
 +
 
 +
 
 +
=Zweites Beispiel: Ungerade/Gerade=
 +
 
 +
==Vorgehensweise==
 +
 
 +
'''Ist die Zahl ''n'' gerade?'''
  
 
  '''1. Funktion'''
 
  '''1. Funktion'''
Zeile 66: Zeile 90:
 
       ansonsten gebe das Ergebnis der ''1. Funktion'' mit ''n-1'' zurück.
 
       ansonsten gebe das Ergebnis der ''1. Funktion'' mit ''n-1'' zurück.
  
−
===Ausführung des zweiten Beispiels mit ''n'' = 5===
+
==Ausführung mit ''n'' = 5==
  
 
  '''Aufbau der Rekursion ("Hinweg")'''
 
  '''Aufbau der Rekursion ("Hinweg")'''
 
   
 
   
 
  '''1. Funktion''' wird mit ''n'' = 5 aufgerufen
 
  '''1. Funktion''' wird mit ''n'' = 5 aufgerufen
−
  ''n'' ist ungleich ''0'', daher führe ''2. Funktion'' mit ''n'' = 4 aus
+
  ''n'' ist ungleich ''0'', daher führe ''2. Funktion'' mit ''n'' = 5-1 = 4 aus
 
    
 
    
 
   '''2. Funktion''' mit ''n'' = 4
 
   '''2. Funktion''' mit ''n'' = 4
−
   ''n'' ist ungeleich ''0'', daher führe ''1. Funktion'' mit ''n'' = 3 aus
+
   ''n'' ist ungleich ''0'', daher führe ''1. Funktion'' mit ''n'' = 4-1 = 3 aus
 
   
 
   
 
     '''1. Funktion''' mit ''n'' = 3
 
     '''1. Funktion''' mit ''n'' = 3
−
     ''n'' ist ungleich ''0'', daher führe ''2. Funktion'' mit ''n'' = 2 aus
+
     ''n'' ist ungleich ''0'', daher führe ''2. Funktion'' mit ''n'' = 3-1 = 2 aus
 
   
 
   
 
       '''2. Funktion''' mit ''n'' = 2
 
       '''2. Funktion''' mit ''n'' = 2
−
       ''n'' ist ungleich ''0'', daher führe ''1. Funktion'' mit ''n'' = 1 aus
+
       ''n'' ist ungleich ''0'', daher führe ''1. Funktion'' mit ''n'' = 2-1 = 1 aus
 
          
 
          
 
         '''1. Funktion''' mit ''n'' = 1
 
         '''1. Funktion''' mit ''n'' = 1
−
         ''n'' ist ungleich ''0'', daher führe ''2. Funktion'' mit ''n'' = 0 aus
+
         ''n'' ist ungleich ''0'', daher führe ''2. Funktion'' mit ''n'' = 1-1 = 0 aus
 
          
 
          
 
           '''2. Funktion''' mit ''n'' = 0
 
           '''2. Funktion''' mit ''n'' = 0
Zeile 106: Zeile 130:
 
  ''Rückgabe:'' ''Nein''
 
  ''Rückgabe:'' ''Nein''
  
−
=> ''5'' ist ungrade
+
=> ''5'' ist ungerade
 +
 
 +
=Direkte und indirekte Rekursion=
 +
 
 +
Bei der '''direkten Rekursion''' ruft sich die Funktion bei der Rückgabe selbst wieder auf. Dies trifft auf das erste Beispiel zu.
  
−
===Direkte und indirekte Rekursion===
+
Bei der '''indirekten Rekursion''' ruft Funktion ''f'' eine andere Funktion ''g'' auf, die wiederum ''f'' aufruft. Dies geschieht im zweiten Beispiel.
  
−
Bei der direkten Rekursion wird die Rekursion direkt aufgerufen, indem bei der Rückgabe die Funktion sich selber wieder aufgerufen wird. Beispiel 1 ist zum Beispiel eine direkte Rekursion. Bei der indirekten Rekursion wird die Rekursion indirekt aufgerufen, indem diese Funktion ''f'' eine andere Funktion ''g'' aufruft, die wiederum ''f'' aufruft.
+
=Verwendung=
  
−
===Verwendung von Rekursion===
+
=Fußnote=

Aktuelle Version vom 18. Januar 2017, 15:42 Uhr

Als rekursiv wird ein Programm oder Algorithmus bezeichnet, das/der sich selbst direkt oder indirekt aufruft. Eine Rekursive Funktion ist demnach eine Funktion, die sich selbst aufruft.

Rekursionen und Schleifen sind semantisch äquivalent und können daher durch durch das jeweils andere ersetzt werden. Dies ist jedoch nicht immer sinnvoll.

Rekursion kommt vom lateinischen Wort recurrere, was zurücklaufen bedeutet.

Erstes Beispiel[1]: Fakultät

Definition

Fakultät von n

Die Fakultät einer Zahl ist das Produkt aller natürlichen Zahlen (außer 0), die kleiner oder gleich dieser Zahl sind. Fakultät wird mit einem Ausrufezeichen hinter der Zahl notiert. Die Fakultät von 0 ist 1 (0! = 1). 

Eingabe: Eine natürliche Zahl n
Ausgabe: Die Fakultät von n
Vorgehensweise:
   Wenn n gleich 0,
   dann gib 1 zurück,
   ansonsten gib das Produkt von n und dem Algorithmus mit der Eingabe n-1 zurück.


Ausführung mit n = 3

Aufbau der Rekursion ("Hinweg")

Ebene: n = 3
Ausführung: n ist ungleich 0, berechne daher das Produkt von 3 und (3-1)!
Aufruf: Fakultät(2)

  Ebene: n = 2
  Ausführung: n ist ungleich 0, berechne daher das Produkt von 2 und (2-1)!
  Aufruf: Fakultät(1)

    Ebene: n = 1
    Ausführung: n ist ungleich 0, berechne daher das Produkt von 1 und (1-1)!
    Aufruf: Fakultät(0)

      Ebene: n = 0
      Ausführung: n ist nun gleich 0, gib also 1 zurück
    
Abbau der Rekursion ("Rückweg")
    
      Rückgabe: Fakultät(0) = 1
    
    Ebene: n = 1
    Rückgabe: 1 * 1 = 1
  
  Ebene: n = 2
  Rückgabe: 2 * 1 = 2

Ebene: n = 3
Rückgabe: 3 * 2 = 6


Mathematisch notiert sieht das ganze folgendermaßen aus:

3! = 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 * 0! = 3 * 2 * 1 * 1 = 3 * 2 * 1 = 3 * 2 = 6


Aufbau

Jede Rekursion besteht aus einer Abbruch-/Terminierungsbedingung und einem Rekursionsrumpf.

Der Rekursionsabbruch erfolgt, wenn die Terminierungsbedingung erfüllt ist. Diese Bedingung überprüft, ob die unterste Ebene des Rekursionsbaums erreicht wurde. Im obigen Beispiel ist dies die Überprüfung, ob n gleich 0 ist, da 0! gleich 1 ist. Sollte diese Bedingung nicht erfüllt werden, wird der Rekursionsrumpf ausgeführt. Wichtig für eine funktionierende Rekursion ist, dass die Bedingung irgendwann erreicht wird, da ansonsten die Rekursion nicht terminiert (Endlosrekursion).

Im Rekursionsrumpf geschieht der Aufruf der Funktion für eine niedrigere Ebene und die Berechnung des Ergebnisses der aktuellen Ebene mit diesem. In dem Beispiel ist dies der Ansonsten-Pfad.


Zweites Beispiel: Ungerade/Gerade

Vorgehensweise

Ist die Zahl n gerade? 

1. Funktion
Eingabe: Eine natürliche Zahl n
Ausgabe: Ja, wenn n gerade ist, Nein, wenn n ungerade ist.
Vorgehensweise:
     Wenn n gleich 0 ist, dann gebe Ja zurück,
     ansonsten gebe das Ergebnis der 2. Funktion für n-1 zurück.

2. Funktion
Eingabe: Eine natürliche Zahl n
Ausgabe: Ja, wenn n ungerade ist, Nein, wenn n gerade ist. 
Vorgehensweise:
     Wenn n gleich 0 ist, dann gebe Nein zurück,
     ansonsten gebe das Ergebnis der 1. Funktion mit n-1 zurück.

Ausführung mit n = 5

Aufbau der Rekursion ("Hinweg")

1. Funktion wird mit n = 5 aufgerufen
n ist ungleich 0, daher führe 2. Funktion mit n = 5-1 = 4 aus
  
  2. Funktion mit n = 4
  n ist ungleich 0, daher führe 1. Funktion mit n = 4-1 = 3 aus

    1. Funktion mit n = 3
    n ist ungleich 0, daher führe 2. Funktion mit n = 3-1 = 2 aus

      2. Funktion mit n = 2
      n ist ungleich 0, daher führe 1. Funktion mit n = 2-1 = 1 aus
        
        1. Funktion mit n = 1
        n ist ungleich 0, daher führe 2. Funktion mit n = 1-1 = 0 aus
       
          2. Funktion mit n = 0
          n ist gleich 0, daher
          Rückgabe: Nein

Abbau der Rekursion ("Rückweg")

          1. Funktion mit n = 1
          Rückgabe: Nein

        2. Funktion mit n = 2
        Rückgabe: Nein
  
      1. Funktion mit n = 3
      Rückgabe: Nein

   2. Funktion mit n = 4
   Rückgabe: Nein

1. Funktion mit n = 5
Rückgabe: Nein

=> 5 ist ungerade

Direkte und indirekte Rekursion

Bei der direkten Rekursion ruft sich die Funktion bei der Rückgabe selbst wieder auf. Dies trifft auf das erste Beispiel zu.

Bei der indirekten Rekursion ruft Funktion f eine andere Funktion g auf, die wiederum f aufruft. Dies geschieht im zweiten Beispiel.

Verwendung

Fußnote

  1. ↑ Alle Rekursionsbeispiele werden hier zum besseren Verständnis im sogenannten Pseudocode notiert.
Von „https://ls14-eini.cs.tu-dortmund.de/index.php?title=Rekursion&oldid=1942“