Buchempfehlung
MySQL kurz & gut
MySQL kurz & gut
Das preiswerte Taschen- buch stellt MySQL-rele- vante Inhalte systematisch und knapp dar, sodass es sich optimal zum Nach- schlagen beim Pro- grammieren eignet. [Mehr Infos...]
FreeBASIC-Chat
Es sind Benutzer im FreeBASIC-Chat online.
(Stand:  )
FreeBASIC bei Twitter
Twitter FreeBASIC-Nachrichten jetzt auch über Twitter erhalten. Follow us!

Tutorial

Iteration und Rekursion

von RedakteurVoltaSeite 1 von 1

Unter Iteration versteht man ein mehrmaliges Ausführen einer Aktion. Typischerweise zählt man dabei mit, zum wievielten Mal die Aktion jeweils erledigt wird:

SUB Pizzaessen()
  VOM ersten BIS zum letzten Bissen
  schneide diesen Bissen ab und iss ihn auf
FERTIG

Unter Rekursion versteht man ebenfalls eine wiederholte Ausführung, doch diesmal gibt es keine Zählschleife, sondern die Aktion erklärt sich 'durch sich selbst':

SUB Pizzaessen()
  WENN Teller leer DANN
    FERTIG
  SONST
    schneide einen Bissen ab und iss ihn auf
Pizzaessen()

Hier ruft sich die Funktion Pizzaessen() ständig selbst auf. 'Immer wieder Pizzaessen(), bis der Teller leer ist'. Der Vorgang stoppt irgendwann, da bei jedem Ablauf das Pizzastück kleiner wird.

Ein unvermeidliches Beispiel:
Du kennst die Fakultäts-Funktion: n! = n*(n-1)! aus der Mathematik.

Function Fakultaet(n)
  if n = 1 then return 1
  return n * Fakultaet(n-1)
End Function

Vergleichen wir mit der Iteration. Wir multiplizieren die Zahlen von 1 bis n auf:

Function Fakultaet(n)
  DIM AS INTEGER tmp
  tmp = 1
  while n > 1
    tmp = n * tmp
    n = n - 1
  wend
  return tmp
End Function

Aber mal ehrlich: diese iterative Version ist irgendwie umständlich und 'mathematisch'....

Das menschliche Gehirn denkt lieber rekursiv als iterativ!

Rekursion bietet sich dann an, wenn man ein gestelltes Problem durch eine Funktion immer wieder schrittweise in ein etwas einfacheres Problem umwandeln kann.

Mit der Rekursion lassen sich eine Reihe von Problemen recht elegant lösen, es heißt aber auch, dass man jedes durch Rekursion lösbare Problem auch durch Iteration lösen kann.

Die Rekursion findet bspw. bei Sortieralgorithmen Anwendung, der Quicksort-Algorithmus wird häufig rekursiv implementiert. Das Durchlaufen eines Dateisystems (Verzeichnishierarchie) bietet sich ebenfalls für die Rekursion an.

Im Grunde wird im Computer jede Rekursion aufgelöst, da der Prozessor des PC selbst nur iterativ arbeitet. Diese Umsetzung wird vom Compiler/Interpreter der Programmiersprache erledigt. Nicht alle Programmiersprachen unterstützen Rekursion gleich gut.

Rekursive Prozeduren sind als etwas heikel in Hinsicht auf den Stack einzustufen. Da die Stackbereinigung erst mit dem Rücksprung (ret) aus der Prozedur erfolgt, kann es passieren, dass der gesamte Speicher auf dem Stack verbraucht wurde bevor überhaupt der erste Rücksprung erfolgt. Der Verbrauch steigt umso schneller, je mehr Parameter und lokale Variablen die Prozedur verwendet.
Insofern ist bei der rekursiven Programmierung darauf zu achten, dass es immer eine Abbruchbedingung gibt, die auf jeden Fall wirkt. Zusätzlich sollte darauf geachtet werden, dass ausreichend Stack reserviert wurde, damit vor dem Abbruch nicht ein Überlauf entsteht oder bereits wichtiger Speicher überschrieben wurde.

Beachte bei der Rekursion:

Quellen:
Prof. Wolfgang Urban, HIB Wien Externer Link!Rekursion.pdf
André Müller Externer Link!Das Assemblertutorial für die Programmierung der x86er Prozessoren

 

Zusätzliche Informationen und Funktionen
  • Das Tutorial wurde am 26.04.2008 von RedakteurVolta angelegt.
  • Die aktuellste Version wurde am 07.11.2008 von RedakteurVolta gespeichert.
  Bearbeiten Bearbeiten  

  Versionen Versionen