Rekursion

Rekursion (Rekurrenz, Rekursivität) stammt vom lateinischen recurrere (zurücklaufen; englisch recursion)

Übrigens: Die PlusPedia ist NICHT die Wikipedia. Wir sind ein gemeinnütziger Verein, PlusPedia ist werbefrei. Wir freuen uns daher über eine kleine Spende!

1 Definition

• „Um Rekursion zu verstehen, muss man erst einmal Rekursion verstehen.“
• Kürzeste Definition für Rekursion: „siehe Rekursion.“
• Bei einer Rekursion wird ein Problem damit gelöst, dass man Zwischenergebnisse wiederum nach gleichem Muster weiterverwendet.
• Es gibt die Direkte Rekursion und eine Indirekte

1.1 Primitive Rekursion

• Primitive Rekursion ist stets durch eine Iteration ersetzbar; Der Aufruf-Baum enthält keine Verzweigungen (Aufruf-Kette)
• Rekursion tritt am Anfang oder am Ende auf. (Hinweis)

2 Praktisches Leben

• "Dieser Satz ist unwahr." (Selbstbezug) (Direkt)
• "Der folgende Satz ist wahr. Der vorhergehende Satz ist unwahr". (Indirekt)

3 Programmierung

Rekursion tritt beim Programmieren auf. Hier wird immer wieder dieselbe Funktion aufgerufen.

3.1 Beispiele

• Die Summe von Zahlen ist: sum(x) = x + sum(x-1) wenn (0 dann 0)

sum(n)
 = 0 (falls n = 0 Rekursionsanfang)
 oder sum(n-1) + n (Wenn n>=1 Rekursionsschritt)
 sum(3) = sum(2) + 3
 sum(2) = sum(1) + 2
 sum(1) = sum(0) + 1
 sum(0) = 0 
 --> 0+1+2+3 = 6

• Fakultät n! = n * (n-1)! bis n=0 und n!=0 ist 1

fakultät_rekursiv (n)
if n <= 1
  then return 1
  else return n * fakultät_rekursiv (n-1)

Eine iterative Lösung sieht wie folgt aus;
  fakultät_iterativ (n)
  fakultät := 1
  faktor := 2
  while faktor <= n
    fakultät := fakultät * faktor
    faktor := faktor + 1
  return fakultät

---

5 Andere Lexika

• Rekursion bei Wikipedia (Erste Wikipedia-Version)

---

---