Rekursion

Aus ProgrammingWiki

Iteration bezeichnet das wiederholte Durchlaufen von Anweisungen. Typischerweise wird dabei mitgezählt, wie oft die jeweilige Aktion erledigt wird. Wir kennen dafür die Sprachkonstrukte for-to, while-do, repeat-until.

def fak_it(n):
  ergebnis=1
  while n>1:
     ergebnis=ergebnis*n
     # print("ergebnis im "+str(n)+". Schritt: "+str(ergebnis))
     n=n-1
  return ergebnis
   
print(str(fak_it(4)))

Bei einer Rekursion erfolgt die Definition eines Problems, einer Funktion oder eines Verfahrens "durch sich selbst". Es handelt sich also wieder um eine Wiederholung, aber ohne Schleife. Dabei muss mindestens für einen Wert das Ergebnis des Verfahrens bekannt sein.

Es ist durchaus sinnvoll, Objekte mit sich selbst zu beschreiben.

def fak_rek(n):
  if n==0: # Abbruch-Bedingung (Ergebnis fuer 0! bekannt)
     # print("fak_rek(0)=1")
     return 1
  else:
     # print("fak_rek("+str(n)+") = "+str(n)+" * fak_rek("+str(n-1)+")")
     return n*fak_rek(n-1) # rekursiver Aufruf
      
print(str(fak_rek(4)))

Typischer Aufbau:

• if für das Ende der Selbstaufrufe
• Aufruf der Funktion selbst

Nachteile:

• jeder Aufruf kostet Zeit (prinzipiell langsamer)
• jeder Aufruf kostet Speichernplatz (Speicher im Stack (Speicherstapel))

PC-Prozessor arbeitet iterativ. Rekursionen werden durch Compiler/Interpreter aufgelöst.