Rekursion: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
(Die Seite wurde neu angelegt: „Unter dem Schlagwort Rekursion werden folgende Sachverhalte zusammengefasst: * rekursive Methoden * rekursive Datenstrukturen =rekursive Methoden= Rekursive…“)
 
 
(3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
[[Kategorie:Informatik]]
[[Kategorie:Informatik-Q1]]
[[Kategorie:Informatik-Abitur]]
Unter dem Schlagwort Rekursion werden folgende Sachverhalte zusammengefasst:
Unter dem Schlagwort Rekursion werden folgende Sachverhalte zusammengefasst:
* rekursive Methoden
* rekursive Methoden
Zeile 18: Zeile 21:
==einfaches Beispiel==
==einfaches Beispiel==


Die folgende rekursive Methode berechnet n! = 1*2*3*...*n:
Die folgende rekursive Methode berechnet n! = 1*2*3*...*n


<code>
<code>
// rekursive Methode mit Parameter
// n wird bei jedem Aufruf eins runtergezählt!
 
  public int fakultaet(int n) {
  public int fakultaet(int n) {
   //Abbruchbedingung
   '''//Abbruchbedingung'''
   if (n <= 1) {
   if (n <= 1) {
     return 1;
     return 1;
   }
   }
   // rekursiver Aufruf fuer n-1
   '''// rekursiver Aufruf fuer n-1'''
   int zahl = fakualtaet(n-1);
   int zahl = '''fakualtaet(n-1)''';
  // Sachlogik
   int ergebnis = n * zahl;
   int ergebnis = n * zahl;
   return ergebnis;
   return ergebnis;
  }
  }
</code>
</code>


==Wo kommt das vor?==
==Wo kommt das noch vor?==


rekursive Methoden braucht man bei folgenden Themen:
rekursive Methoden braucht man bei folgenden Themen:


* [http://sibiwiki.de/wiki/index.php?title=Binärbaum_(Methoden)#Rekursion Rekursion bei Binärbäumen]
* [[Binärbaum_(Methoden)#Rekursion|Rekursion bei Binärbäumen]]<br/>Unter anderem werden Inorder- Preorder und Post-Order Traversierungen von Binärbäumen rekursiv programmiert.
* [[Quicksort]]
 
* [[Graph#Tiefendurchlauf|Tiefendurchlauf bei Graphen]]
 
=rekursive Datenstrukturen=
 
[[Binärbaum|Binärbäume]] sind als Datenstruktur rekursiv definiert.
Denn jeder Binärbaum enthält seinerseits zwei Binärbäume (den rechten und den linken).

Aktuelle Version vom 23. Januar 2022, 18:13 Uhr

Unter dem Schlagwort Rekursion werden folgende Sachverhalte zusammengefasst:

  • rekursive Methoden
  • rekursive Datenstrukturen

rekursive Methoden

Rekursive Methoden sind Methoden, die sich selber aufrufen, um z.B. eine Berechnug auszuführen.

Wichtig sind dabei folgende Elemente:

  • ein Parameter, in dem man je nach Rekursionsstufe einen anderen Wert übergeben kann.
  • eine Abbruchbedingung für das Rekursionsende - sonst läuft die Methode ewig weiter.
  • ein (oder mehrere) rekursive Aufrufe.

einfaches Beispiel

Die folgende rekursive Methode berechnet n! = 1*2*3*...*n


// rekursive Methode mit Parameter
// n wird bei jedem Aufruf eins runtergezählt!
 
public int fakultaet(int n) {
  //Abbruchbedingung
  if (n <= 1) {
    return 1;
  }
  // rekursiver Aufruf fuer n-1
  int zahl = fakualtaet(n-1);
  // Sachlogik
  int ergebnis = n * zahl;
  return ergebnis;
}

Wo kommt das noch vor?

rekursive Methoden braucht man bei folgenden Themen:

rekursive Datenstrukturen

Binärbäume sind als Datenstruktur rekursiv definiert. Denn jeder Binärbaum enthält seinerseits zwei Binärbäume (den rechten und den linken).