Die Webseiten der Fachschaft Informatik am ERG Saalfeld

Rekursion

Definition

Rekursion ist ein Selbstaufruf mit Abbruchbedingung

Erläuterung an einem Beispiel

Die Fakultät von 5 kann so schreiben:

  5! = 5 * 4 * 3 * 2 * 1

oder wenn man die letzten 4 Faktoren zusammenfasst, also wieder als Fakultät schreibt:

  5! = 5 * 4!

allgemein kann man das so schreiben:

  n! = n * (n - 1)!

Da bedeutet: die Fakultät von n wird berechnet, indem man auf der rechten Seite wieder die Fakultät aufruft. Aber: es wird nicht die Fakultät von n aufgerufen, sondern von n-1. Das bedeutet, die "Stufe" wird verringert. Fragt sich nur "wie lange?"

Es wird also noch eine Abbruchbedingung gebraucht. Üblicherweise wird genommen:

  1! = 1

Auf der Seite "Bestimmung der Fakultät von 5 mit Bierdeckeln" wird beschrieben, wie man sich die Realisierung im Computer mit einem Stack anhand des Modells "Bierdeckelstapel" vorstellen kann. Dabei übernimmt der Bierdeckelstapel das Speichern der noch zu erledigenden Aufgaben, was im Computer der Stack übernimmt.

Es ergibt sich damit folgendes Aufrufschema:

Aufruf-Schema für fak(5)

fak(5)	=	120

5 * fak(4)	=	5 * 24

4 * fak(3)	=	4 * 6

3 * fak(2)	=	3 * 2

2 * fak(1)	=	2 * 1

fak(1)	=	1

Zitat: Du kannst dir die Rekursion wirklich wie eine Treppe vorstellen, die nach unten führt. Jede Stufe ist ein weiterer Funktionsaufruf. Wenn dann irgendwann mal eine Funktion beendet wird, dann steigst du [...] wieder auf. [1]

zur Programmierung

Wir schreiben (wegen der Programmierung) ab jetzt immer die Abbruchbedingung zuerst! Die (rekursive) Definition der Fakultät sieht so aus:

  1! = 1
  n! = n * (n - 1)!

Das setzen wir jetzt quasi 1:1 in eine rekursive Subroutine fak um:

def fak (n):
  if n==1:
      rueckgabe = 1           #Abbruchbedingung
  else:
      rueckgabe = n*fak(n-1)  #rekursiver Ausdruck
  return rueckgabe

Zur Fakultät gibt es eine eigene Seite mit Aufgaben. Hier ging es nur darum zu erklären, was Rekursion ist und wie man die programmtechnisch umsetzt.

Weblinks

zurück