Iteration, Rekursion

[Freaka]

Hi kann mir jemand einen Link posten, wo ich die Bedeutung dieser Begriffe finden kann. Oder kann sie mir jemand erklären??

Danke im voraus

[Woodstock]

Also, zu Iteration ist das

Iteration Statements

Iteration statements cause statements (or compound statements) to be executed zero or more times, subject to some loop-termination criteria. When these statements are compound statements, they are executed in order, except when either the break statement or the continue statement is encountered. (For a description of these statements, see The break Statement and The continue Statement.)

C++ provides three iteration statements — while, do, and for. Each of these iterates until its termination expression evaluates to zero (false), or until loop termination is forced with a break statement. Table 5.2 summarizes these statements and their actions; each is discussed in detail in the sections that follow.

Table 5.2 C++ Iteration Statements

Statement Evaluated At Initialization Increment

while Top of loop No No

do Bottom of loop No No

for Top of loop Yes Yes

Syntax

iteration-statement :

while ( expression ) statement

do statement while ( expression ) ;

for ( for-init-statement expressionopt ; expressionopt ) statement

for-init-statement :

expression-statement

declaration-statement

The statement part of an iteration statement cannot be a declaration. However, it can be a compound statement containing a declaration.

das einzige was ich in meiner Hilfe gefunden haben.

Zu Rekursion steht in meiner Hilfe gar nichts. Aber ich habe schon einmal rekursiv gearbeitet. Und zwar wollte ich alle Textdateien auf miener Festplatte finden. Dazu habe ich als erstes geschaut ob auf meiner Festplatte ein Ordner ist. Ist dem so, bin ich in den gewechselt. Gab es in dem wieder einen Ordner, so habe ich auch zuerst in den gewechselt bis ich etwas anderes gemacht habe. Solange bis ich keinen Ordner mehr hatte. Dann habe ich also in dem 'unterstern' Ordner angefangen nach Dateien zu suchen. Hatte ich alles durchsucht (und eventuell etwas damit gemacht) bin ich wieder in der Ordner darüber gewechselt. DOrt habe ich dann zuerst wieder geschaut ob noch ein weiterer Ordner existiert und gegebenenfalls in den gewechselt etc. Und das war rekursiv.

Bine

[Poldi]

Iteration = "hoch/runterzählen" einer Variable

Rekursion = rekursive funktionen rufen sich selbst auf, das ist ziemlich komplex, such mal hier auf dem board danach, da wirst du bestimmt fündig

[mst]

Häufig meint man mit Iteration aber auch Schleifen.

[gajUli]

Inkrementierung bedeutet Hochzaehlen! (Dekrementierung: Herunterzaehlen)

Iteration heisst einfach Wiederholung; wird meist durch Schleifen erreicht.

Rekursion ist eine Sonderform der Wiederholung. Der Begriff stammt aus der Mathematik. Rekursion kommt dort haeufig bei der Definition von Folgen zum tragen. In der Programmierung kann man diese sehr direkt mit Hilfe von rekursiven Funktionen, wie Poldi sie beschrieben hat, umsetzen.

Im letzter Konsequenz bewirkt aber beides das Gleiche. Ob man alle Zahlen von 30 bis 300 in einer Schleife aufaddiert oder mit einer rekursiven Funktion; der Computer tut dabei (bis auf die Funktionsparameter auf dem Stack) das Gleiche.

[Crush]

Ich weiß ja auch nicht ganz genau, ob das stimmt, aber ich sage mal, wie ich das ungefähr verstehe.

Bei Rekursionen rufen sich Funktionen selber immer wieder auf und sobald das Abbruchkriterium erfüllt ist, wird aus der untersten Schicht das Ergebnis nach "oben" hochgereicht und sozusagen wieder alles rückwärts aufgearbeitet (erfordert einen Stack)!

Bei Iterationen hat man feste Variablen, welche in einer Schleife durchlaufen werden und die für jeden weiteren Durchlauf neu berechnet/angepaßt werden. (Erfordert lediglich die Laufvariablen)

Jeder rekursive Ablauf ist (jedenfalls theoretisch) auch iterativ darstellbar. Der Vorteil der Iteration ist, daß es keinen Stacküberlauf geben kann und nicht die vorherigen Iterationsergebnisse und Prozessorregister auf dem Stack zwischengespeichert werden müssen - daher sind Iterationen üblicherweise schneller im Ablauf.

[gajUli]

@crush

Der Begriff erschoepft sich zwar nicht in rekursiven Funktionen. Was Du dazu schreibst, finde ich aber richtig und gut.

Wie siehts eigentlich mit void foo(void) bzgl. Stackbelastung aus?

[Poldi]

Original geschrieben von gaiusjUlius

Inkrementierung bedeutet Hochzaehlen! (Dekrementierung: Herunterzaehlen)

eeeh ups, hast recht, da hab ich zu schnell gelesen ... *fg*

[hoagi]

Wie siehts eigentlich mit void foo(void) bzgl. Stackbelastung aus?

Zumindest die Rücksprungadressen werden auf dem Stack gespeichert.

( Krieg ich jetzt ne eins ??? )

:WD

[gajUli]

Da bin ich mir nicht sicher. Eine Funktion ohne Parameter und ohne Return-Value koennte doch ein intelligenter Compiler vielleicht auch ohne Ruecksprungadressen auf dem Stack realisieren. Oder?

[Crush]

Eine Funktion ist aber definiert als ein Unterprogrammaufruf - und dafür gibt es ganz konkrete Assembler-Befehle, die auch immer konsequent vom Compiler verwendet werden - und da wird halt immer irgenwas auf dem Stack abgelegt und nachher wieder runtergenommen und das Minimum ist halt der Programm-Counter des Prozessors - sonst würde er ja nie wieder zurückfinden.

Eine Funktion, die nichts aufruft, zurückgibt und abarbeitet ist ja auch Schwachsinn, weil unnötig - ein theoretisches Kunstgebilde, das keiner braucht. Das, worauf Du damit abzielen würdest wäre Inline-Code - und wenn man den unbedingt will, dann soll man das auch für jeden deutlich sichtbar programmieren. Inline Functions sind ja auch nicht unbedingt eine Seltenheit - und die werden bestimmt auch ordentlich optimiert (muß ich mal austesten).

Solche Optimierungen würden Programmierer dazu verleiten zu stark vom logischen Aufbau abzuweichen und sich darauf zu verlassen, daß der Compiler das Kind schon irgendwie schaukeln wird - da würde meiner Meinung nach Chaoscode bei rauskommen.

[Crush]

Komisch, ich habe es nicht geschafft eine Inline-Funktion irgendwie optimiert zu compilieren, sodaß man im Debugger etwas anderes als einen call sieht. Vielleicht schafft das ja einer von Euch!

[gajUli]

Hab das mal ausprobiert. Der Debugger zeigt das Gleiche wie Du beschrieben hast, bei jedem Durchlauf einen weiteren call.

Die Calls selber sehen exakt so aus wie eine Schleife. Da wird einfach oben wieder reingesprungen mit einem absoluten Adressbranch. (bl, steht wohl fuer branch local)

Allerdings beginnt die Funktion mit zwei Assemblerbefehlen, die den Stack-Pointer ansprechen. Weiss aber nicht genau, was die veranstalten. Muss mal eine Moeglichkeit suchen, mir den Stack anzusehen.

Jedenfalls hab ich die Funktion eine Rekursion ohne Abbruch geschickt, worauf der Computer komplett abgestuerzt ist. Vielleicht war der Grund wirklich ein Stack-Overflow... confused:

[gugelhupf]

Also ich arbeite schon ein wenig mit Assembler und ich musste feststellen, dass Rekursion in diesem Bereich nicht so darstellbar ist wie z.B. in C.

Man "Jumpt" einfach in der Funktion auf die erforderlichen Labels mit verschiedenen Parametern und Registerwerten.

Ist übrigens auch ne gute Übung, um sich das Prinzip der Rekursion klarzumachen. Wenn man na weile auf Mnemonics herumgeturnt hat, dann is das gar nicht mehr so schwer nachzuvollziehen.

Ich wollte eine Rekursion über eine Stringsuche auf dem pysischen Speicherbereich implementieren, bekam aber mit den CALL-Aufrufen (über 60.000) Schwierigkeiten mit einem Stack der nicht über die Segmentgrenze ging.

Wie Crush schon sagte ist Iteration (wenn sie ordentlich implementiert wurde) meistens performanter, aber Rekursion (z.B. in binären Bäumen) ist meisten deutlich kürzer und besser lesbar.

[Crush]

Es findet ruckzuck ein Überlauf statt. Das liegt am Code-Model (small, tiny, huge, etc.) und am Prozessor, weil diese definitiv immer nur einen 64KB Stapel erlauben.

Die einzigste Lösung ist es einen dynamischen Stack-Handler selber zu schreiben, von mir aus als verkette Liste oder Ähnlichem - wie man damit jedoch die calls abfangen könnte (außer im Trace-Mode) wüßte ich jetzt auch nicht.

Man könnte Zugriffe auf den Adress-Bereich des Stacks versuchen abfangen (vielleicht geht sowas im Protected Mode?) und dann auf einen eigenen Stack-Handler umlenken.

Wenn man es schaffen könnte, allen Call-Befehlen einen illegalen Befehlswert zu verpassen, wäre es möglich das ganze über Exceptions zu lösen, bzw. wenn man nach den Calls den Stack "umräumt" auf einen eigenen dynamischen Stack, dann die Funktion normal aufruft und diesen "neuen Stack" beim Verlassen wieder richtig aberntet um mit RET wieder zurückzuspringen, dann wäre das Problem auch gelöst - diese würde vor und nach jedem Funktionsaufruf jedoch Macros erfordern.

Wäre mal eine Sache sich damit etwas zu beschäftigen... aber bestimmt gibt es schon andere, elegantere Lösungen - wir sind ja bestimmt nicht die ersten, die an die Grenze gestoßen sind.