Wer ist online?
Buchempfehlung
FreeBASIC-Chat
FreeBASIC-Nachrichten jetzt auch über Twitter erhalten. Follow us!Tutorial
Iteration und Rekursion
von  Volta | Seite 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:
- jeder Funktionsaufruf kostet Zeit. Also ist Rekursion prinzipiell langsamer als Iteration. Auch bei FreeBASIC zeigt sich, dass oft eine Prozedur in iterativer Version schneller arbeitet als eine rekursive Version.
- jeder Funktionsaufruf kostet Speicherplatz. Also belegt die Rekursion viel Speicher auf dem Stack.
Quellen:
Prof. Wolfgang Urban, HIB Wien 
Rekursion.pdf
André Müller Das Assemblertutorial für die Programmierung der x86er Prozessoren
| Zusätzliche Informationen und Funktionen | |||||||
|---|---|---|---|---|---|---|---|
|
|||||||
Bearbeiten
Versionen