Vergleich Rekursion <-> Iteration
Gemeinsamkeit
Beides sind Formen der Wiederholung von Teilen eines Algorithmus.
Unterschiede
Iteration ist Wiederholung durch Aneinanderreihung.
Als Kontrollstrukturen werden Schleifen eingesetzt.
Rekursion ist Wiederholung durch Ineinanderschachtelung.
Als Kontrollstrukturen werden Verzweigungen verwendet.
Iterative Lösungen sind effizienter. (Sie sind schnell und beanspruchen wenig Speicher.)
Rekursive Lösungen legen u.a. die Werte der aktuellen Parameter und der lokalen Variablen auf dem Stack (spezieller Bereich des Arbeitsspeichers) ab. Dadurch benötigen sie mehr Arbeitsspeicher und sind auch langsamer.
Die Quelltexte rekursiver Lösungen sind meist übersichtlicher als die entsprechenden Quelltexte iterativer Lösungen.
Aufgabe:
Teilen Sie ein in iterative bzw. rekursive Algorithmen:
ggT nach Euklid, monoalphabetische Substitution, Turm von Hanoi, Permutation von n Elementen, Suche im Labyrinth, Worteraten, Fakultät, "Hallo Welt"!