Rekursion

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

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

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)

Praktisches Leben

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

Programmierung

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

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

---

Andere Lexika

• Rekursion bei Wikipedia (Erste Wikipedia-Version)

---

---