Teilermenge ermitteln

[Eichhoernchen]

da sagt man einmal rekusion und schon hat man ne Welle losgetreten!

Ich weiß zwar nicht warum, aber mein Info lehrer will fast immer das wir Probleme rekursiv lösen!

Gibt es einen Vorteil wenn man es über Wiederaufrufe macht?

[marabu]

Als Faustregel kann man formulieren: rekursiv definierte Probleme lassen sich über rekursive Algorithmen sehr elegant lösen, performanter ist in der Regel der iterative Algorithmus.

marabu

[BlackJack]

Zitat von alzaimar:

Dein Beispiel f:= f(f(x)) ist auch rekursiv nicht lösbar (-> Endlosschleife).

naja war ja nur ein Beispiel, man muss da halt noch code mit abbruchkriterien drumrum schreiben.

@marabu: wieder was dazu gelehrnt. gibt es denn ein standardverfahren, wie man eine rekursive implementierung in eine iterative umwandelt?

[marabu]

Hi BlackJack,

ein einziges Standardverfahren kann es nicht geben, da die Rekursion selbst Varianten kennt - nicht jede Rekursion ist linear und selbst die linearen weisen nicht ausnahmslos eine tail recursion auf. Die Schematisierung des Transformationsprozesses interessiert die Informatiker auch heute noch, z.B. bei der Implementierung funktionaler Sprachen (Lisp, Hope, Miranda, Haskell).

Magst du einen kleinen Einblick? Klick

marabu

[negaH]

Jede rekursive Funktion wird und muß in eine iterative umwandelbar sein.
Es gibt aber iterative Funktionen die nicht rekursiv gelösst werden können.

Die rekursive Schreibweise ist nur eine andere Form eines iterativen Verfahrens. Der einzigste Unterschied liegt in der meist einfacheren Begreiflichkeit der rekursiven Verfahren für den Menschen.

Für ds oben angesprochene Problem der Kombinatorik hätte sich auch ein Blick in die CodeLib gelohnt. Dort findest du bestimmt einige Sourcen.

Gruß Hagen

[Robert Marquardt]

Zitat von dizzy:

Gibt es denn mittlerweile eine rein iterative Lösung zun den "Türmen von Hanoi"? Zu meiner Schulzeit jedenfalls war imho noch keine bekannt. (Zumindest meinte dies unserer (entgegen der landläufigen Üblichkeit) relativ gute Info-Lehrer...)

Ja es gibt.
http://de.wikipedia.org/wiki/T%C3%BCrme_von_Hanoi

[marabu]

Hallo Hagen,

Zitat von negaH:

Es gibt aber iterative Funktionen die nicht rekursiv gelösst werden können.

mit diesem Satz widersprichst du einigen Koryphäen auf dem Gebiet der Informatik. Prof. David Gries (damals Cornell University) schreibt in seinem Buch "The Science of Programming" (Chapter 18 - Using Iteration Instead of Recursion):

Zitat:

... in theory at least, any recursive program can be written iteratively (and vice versa), ...

Spricht aus deinen Worten eine innere Überzeugung (wie "die Erde ist eine Scheibe") oder ist deine Aussage missverständlich, weil ungenau? Zielst du vielleicht auf die von mir angedeutete Grundhaltung, dass nicht jeder Versuch, die "Korrektheit" eines durch vollständige Induktion untermauerten Algorithmus gegen einen kleinen prozentualen Performanzgewinn durch iterative Implementierung einzutauschen, vernünftig ist?

Freundliche Grüße vom marabu


@BlackJack: In dem von mir hier zitierten Buch versucht der Autor einige Vorgehensweisen zur Schematisierung der Transformation zu vermitteln.

[BlackJack]

Zitat von marabu:

@BlackJack: In dem von mir hier zitierten Buch versucht der Autor einige Vorgehensweisen zur Schematisierung der Transformation zu vermitteln.

naja so sehr wollte ich mich in die materie eigentlich nicht einarbeiten, aber das pdf von dir war schon echt interessant (auch wenn mir der C++ -(und Haskel?) Code manchmal einige schwierigkeiten bereitet hat).