#27-28 Rekursion

Question 1

Was ist Rekursion sowie Rekursive Funktionen?

Answer 1

• Rekursion: Selbstbezüglichkeit
  - Beispiel (Definition natürlicher Zahlen):
  - 1 ist eine natürliche Zahl
  - Wenn n eine natürliche Zahl ist, dann auch n+1
• Rekursive Funktion = eine Funktion, die sich selbst aufruft
  - Beispiel (Fakultät):
  - 0! = 1
  - n! = n * (n-1)! für n > 0
• Wichtig: Abbruchkriterium (im Beispiel für n=0)

Rekursion in C
In C ist es erlaubt, dass sich eine Funktion selbst aufruft.

int fakultaet(int n)
{
if(n == 0) {
return 1;
} else {
return n * fakultaet(n-1);
}
}
int main()
{
int x;
printf(“Bitte Zahl eingeben: “);
scanf(“%d”, &x);
printf(“Fakultaet: %d\n”, fakultaet(x));
return 0;
}

Question 2

Nenne Unterscheidungen von Rekursion und Iteration

Answer 2

Iteration: Anzahl von bestimmten Durchläufen bis “Abbruch”
Rekursion: Ergebnis wir wieder mit einbezogen in Funktion
- Für jede rekursive Lösung gibt es auch eine iterative, die auf
Schleifen basiert.
- Rekursiv oder iterativ? Entscheidungskriterien:
- Komplexität der einzelnen Lösungen
- Was ist einfacher zu programmieren?
- Welche Lösung ist leichter verständlich?
- Laufzeitverhalten
- Funktionsaufrufe kosten Zeit
- Speicherbedarf
- bei jedem Funktionsaufruf werden alle lokalen Variablen der Funktion erneut angelegt