Informatik Rekursion und Iteration unterschied?
Servus, wir machen in Info gerade Haskell und da werden die Konzepte der Rekursion und Iteration besprochen.
Ich versteh den Unterschied einfach noch nicht. Könnte mir das einer einfach zusammenfassen?
Rekursion und Iteration rufen sich doch beide selber im Funktionsrumpf auf und dekrementieren bis beim conditional statement ein False erscheint. Ich kann den Unterschied einfach nicht sehen.
Danke schonmal für die Antworten :D
2 Antworten
Rekursion funktioniert durch das Aufrufen einer Funktion in sich selbst.
def fibonacci(number)
if number < 2
return number
else
return fibonacci(number - 1) + fibonacci(number - 2)
end
end
Bei diesem Beispiel geht es um die Fibonacci Folge und der Code gibt schlussendlich die Zahl der Fibonacci Folge aus, welche an der Stelle von Number steht. Wenn Number = 6, dann ist der Wert 8, denn die Folge geht 1 1 2 3 5 8 13 21 ... (Es wird mit 1 begonnen und jede nächste Zahl ist die Addition der beiden vorangegangen Zahlen) und 8 ist an der 6ten Stelle der Folge. Die Funktion berechnet das, indem sie den Input number nimmt, diesen verändert (hier in number -1 und number -2) und damit wieder die Funktion aufruft. Das geht solange, bis die Abbruchbedingung number < 2 eintritt, dann wird einfach number zurückgegeben. Danach löst sich diese Rekursion von unten nach oben auf, sodass die zu beginn aufgerufene Funktion einen Wert zurückgibt. Also wird number jedes mal kleiner, wenn die Funktion wieder in der Rekursion aufgerufen wird, bis sie die Abbruchbedingung erfüllt, dann gibt diese einen Wert zurück, dieser wird dann an die nächste Ebene weitergegeben, der die Funktion aufgerufen hat. Das geht dann bis fibonacci(number-1) und fibonacci (number-2) einen Rückgabewert hat, dieser wird dann addiert und bildet den Rückgabewert von fibonacci(number).
(Hoffe das ist irgendwie verständlich)
Bei einer Iteration wird einfach ein Schleifenkonstrukt genutzt um wiederholt irgendwelche Operationen durchzuführen. Zum Beispiel mit einer While Schleife. In dieser gibt es auch eine Abbruchbedingung, jedoch wird die Funktion nicht in sich selbst aufgerufen um den Effekt der widerholten Anwendung von Operationen zu erzielen, sondern eben nur die Schleife.
Wäre wohl etwas wie:
fibonacci (number) //für number >0
int n1 = 0;
int n2 = 1;
for (i=2, i<=number, i++)
int k;
k = n1 + n2;
n1 = n2;
n2 = k;
return n2;
Hab jetzt nicht wirklich drüber nachgedacht und hoffe ich hab kein dummen Fehler drin, aber so müsste das etwa funktionieren.
Wie du siehst wird die Widerholung durch die for-Schleife durchgeführt und nicht durch das Aufrufen der Funktion in sich selbst.
Bei der einen sache( rekursiv) ruft die funktion sich selbst auf. das ist ein unterschied. der ausstieg muss deswegen in der funktion selbst festgelegt werden.
iterativ ist meist an for-schleifen erkennbar. zum beispiel der klassiker: berechneFakultaet
Bei for-schleifen zählt man ja irgendwas hoch, was verhindert eine rekursive funktion das auch zu machen?
bei dem rekursiven funktionsaufruf kommt es darauf an, dass das ergebnis beim jeweiligen rücksprung aus der funktion vom stapel gelesen wird.
das ist bei der iterativen nicht der fall.
trotzdem können durchaus bei der rekursion auch schleifen auftauchen.
Ich hab die Rekursion jetzt im tieferen Verstanden, aber kannst du mir bitte nochmal den Code als Iteration wiedergeben, damit ich das Konzept nochmal verstehe? Vielen Dank