• Hauptseite
• Artikel
• Bearbeiten
• Versionen
• Spezialseiten
• Hochladen

C-sharp-rekursion

Grundsätzliches

• Rekursion ist ein Verfahren zur Problemlösung
• ein rekursives Verfahren teilt ein großes Problem in kleine 'gleichartige’ Probleme (allgemeiner Fall, general Case)
• es muss ein kleines’’, ohne Rekursion direkt lösbares Problem geben. (Terminierungsfall, Base Case)
• es gibt immer eine nicht rekursive Lösung

Beispiele

a) S(n) sei die Summe der ersten n ganzen Zahlen mit S(1) = 1

general Case: S(n) = S(n-1) + N (S(n) = großes Problem, S(n-1)...= kleineres Problem)

S ist durch sich selbst definiert -> Rekursion

Base Case: S(1) = 1

 
mit n > 0
 
static uint S(uint N)
{
   if(n == 1)
      return 1;
   return S(n-1) + n;
}
 

Jeder Aufruf eines Unterprogramms legt seine lokalen Variablen auf dem Laufzeitstack ab.

b) Fibonacci zahlen:

general Case:

base case:

 
static uint F(uint i)
{
   if( i == 0 || i == 1)
      return i;
   return F(i-2) + F(i-1);
}
 

Daraus ergeben sich folgende Aufrufe

Die Anzahl der Unterprogammaufrufe A_i zur Berechnung der i-ten Fibonacci-Zahl ist

z.B. ist für die 42. Fibonacci-Zahl :

Aufrufe notwendig

• rekursive Lösungen sind meistens einfach
• rekursive Lösungen sind bezgl. Speicherbedarf und CPU-Bedarf nicht optimal

Weitere Informationen

• hier gehören noch externe Links hin