Prefix in rekursiven Funktionen

[Mattin]

Guten Tag,

ich habe eine kleines Verständnisproblem und würde mich freuen, wenn mir jemand vielleicht kurz Zeit nimmt und mir auf die Sprünge hilft.

Soweit ich weiß gibt es ja die Prefix (--n) und Postfix (n--) möglichkeiten um variablen um den Wert 1 zu verringern. Nach meinem Verständnis liegt der Unterschied darin, dass bei einem Funktionsaufruf mit dem Prefix die Zahl erst um eins verringert wird und dann die Funktion aufgerufen wird, bei Postfix verwendung jedoch erst die Funktion mit dem ursprünglichen Wert aufgerufen wird und die Variable danach um 1 verringert.

Nun zum eigentlichen Problem:

um die Fakultät zu berechnen habe ich folgende rekursive Funktion geschrieben

int fac(int n)
{
    int f = 1;
    if(n>1)
    {
        f = n*fac(--n);
    }
    return f;
}

nach meinem bisherigen Verständnis sollte diese Schreibweise äquivalent zu

int fac(int n)
{
    int f = 1;
    if(n>1)
    {
        f = n*fac(n-1);
    }
    return f;
}

sein, ist es jedoch nicht. Die erste Variante liefert für fac(5) als Ergebnis die Fakultät von 4, die zweite Variante hingegen jedoch das richtige Ergebnis.

Und nun was mich völlig aus dem Konzept bringt:

int fac(int n)
{
    int f = 1;
    if(n>1)
    {
        f = n*f*fac(--n);
    }
    return f;
}

f wird bei jedem Funktionsaufruf auf 1 initialisiert, es sollte sich also am Ergebnis nichts ändern... dem ist aber nicht so. Beim Aufruf der letzten Funktion wird wieder das richtige Ergebnis fac(5)=120 geliefert.

Könnte mir jemand bitte erklären was da abgeht??

Würde mich sehr über Antworten freuen.

Viele Grüße,
Martin

[KN4CK3R]

Beim ersten Code ändert das

n*fac(--n);

beide 'n'. Also auch das n*fac. Aber das willst du eigentlich gar nicht verändern hier.

[Mattin]

Ok, Soweit so gut... aber warum bewirkt nun eine Multiplikation mit dem auf 1 initialisierten f eine Änderung?

[manni66]

Es ist nicht definiert, in welcher Reihenfolge die Operationen ausgewertet werden, d.h. ob zunächst des n vorne betrachtet und dann --n für den Funktionsaufruf ausgewertet wird oder anders herum. Durch die Multiplikation mit 1 ändert der Compiler die Reihenfolge => anderes (jetzt "richtiges") Ergebnis.

[sebi707]

manni66 schrieb:

Durch die Multiplikation mit 1 ändert der Compiler die Reihenfolge => anderes (jetzt "richtiges") Ergebnis.

Und das auch rein Zufällig. Ich habe hier gerade mal VS 2013 getestet und da ändert das multiplizeren mit f nichts und man kriegt immer noch das falsche Ergebniss.

Hier kann man mehr nachlesen: http://stackoverflow.com/questions/4176328/undefined-behavior-and-sequence-points

[camper]

f = n*fac(--n);

Das Verhalten dieses Programmes ist undefiniert (1.9/15). Zwischen der Modifizierung des Objektes n in

--n

und dem Lesen des Zustandes des Objektes n im Teilausdruck

n

besteht keine Reihenfolge der Ausführung. Das Programm darf also legitimerweise die Festplatte formatieren.

Vergleiche mit

int& prefix_dec(int& n) { return --n; }
int fac(int n)
{
    int f = 1;
    if(n>1)
    {
        f = n*fac(prefix_dec(n));
    }
    return f;
}

Wiederum ist es so, dass der Multiplikationsoperator keine Reihenfolge bei der Auswertung der beiden Operanden induziert. Allerdings findet hier die Modifikation des Objektes n innerhalb der Funktion prefix_dec statt.
Die speziellere Regel zu Funktionsaufrufen besagt u.a., dass
1. jeder Nebeneffekt der Auswertung einer Funktion einerseits erst nach Betreten jener Funktion stattfindet und bei Verlassen der Funktion abgeschlossen ist, und
2. jder Nebeneffekt der Auswertung der Funktionsargumente bei Betreten der Funktion abgeschlossen ist (hier nicht relevant), und
3. jeder andere Teil der Auswertung des Ausdruckes, der den Funktionsaufruf enthält, in unbestimmter Weise entweder vor oder nach dem Funktionsaufruf stattfindet (es sei denn eine speziellere Regel gibt eine bestimmte Reihenfolge vor).

Der wesentliche Unterschied zum ursprünglichen Fall ist der, dass eine Reihenfolge der Auswertung der kritischen Operationen (Modifikation von n und Zugruff auf den Wert von n) besteht. Der Compiler ist also gezwungen, Code zu erzeugen, der bei jedem Auftreten entweder den linken oder aber den rechten Operanden zuerst auswertet. Welche Wahl der Compiler trifft bleibt unbestimmt. Konsistenz wird dabei nicht verlangt, selbst der mehrfache Aufruf mit denselben Werten gerantiert also nicht gleiche Ergebnisse (diese Konsistenz wird nur in Hinblick auf mehrfache Aufrufe des gesamten Programmes verlangt, 1.9/5). Ein

assert( fac(5) == fac(5) );

darf fehlschlagen (reale Compiler werden in der Regel in konsistenter Weise reagieren, die Sprache schreibt das aber nicht vor - praktisch müsste man für diesen Effekt kräftig nachhelfen, z.B. indem eine inline Funktion in verschiedenen ÜEs verwendet wird und diese ÜEs mit unterschiedliche Optimierungsoptionen compiliert werden).

Beide Varianten sind folglich böse.

[sebi707]

Was soll jetzt genau der Unterschied sein? Du meinst bei der Variante ohne Funktion können sich Lesen und Schreiben überlappen, sodass ich beispielsweise auf einer 32 Bit Architektur mit 64 Bit ints nur die "halbe" Subtraktion beim lesen von n sehe?

[Columbo]

sebi707 schrieb:

Was soll jetzt genau der Unterschied sein? Du meinst bei der Variante ohne Funktion können sich Lesen und Schreiben überlappen, sodass ich beispielsweise auf einer 32 Bit Architektur mit 64 Bit ints nur die "halbe" Subtraktion beim lesen von n sehe?

Inwiefern ist es überhaupt sinnvoll so eine Frage zu stellen? Das Verhalten ist undefiniert, und damit kann prinzipiell alles passieren. Welchen Effekt das in der Praxis genau hat, hängt völlig von verschiedenen Dingen ab.

[sebi707]

Ich habe einfach versucht campers ziemlich lange Antwort zu verstehen. Es gibt ja auch sonst Dinge die in C++ undefiniert sind aber nicht dazu führen, dass meine Festplatte formatiert wird. Zum Beispiel

int c = ++a * ++b;

Da ist auch nicht definiert ob zuerst a oder b incrementiert wird, aber trotzdem sind am Ende alle Werte klar definiert.

So habe ich auch campers Ausführungen verstanden:
- Ohne Funktion: Alles kann passieren, bis zum Formatieren der Festplatte.
- Mit Funktion: Der Compiler muss zumindest eins nach dem anderen ausführen. Damit kriege ich zwar ein irgendwie zufälliges Ergebnis aber es stürzt nicht ab und das Ergebniss muss eines der beiden Fälle (oder 2^N Fälle bei der Rekursion) ergeben.

[Columbo]

Es gibt ja auch sonst Dinge die in C++ undefiniert sind aber nicht dazu führen, dass meine Festplatte formatiert wird.

Wenn du nicht sowieso dabei bist, eine Operation auszuführen die mit entsprechenden Argumenten deartiges tun könnte: Es ist wahrscheinlicher, dass Volkard in Stöckelschuhen und Latex vor deinem Haus auftaucht. Warum also nicht das als ein Beispiel nehmen? Volkard hat sicherlich nichts dagegen? (Also wie eine Schlampe gekleidet durch die Nachbarschaft zu rennen, meine ich. Nicht Subjekt eines dummen Witzes zu sein, das würde niemals jemand wagen.)

Da ist auch nicht definiert ob zuerst a oder b incrementiert wird

Nicht spezifiziert. Kann auch beides gleichzeitig passieren.

aber trotzdem sind am Ende alle Werte klar definiert.

Alle möglichen.

Alles kann passieren, bis zum Formatieren der Festplatte.

Laut Standard - der aber keine Festplatten kennt. Und wenn ich nach x86 gehe, würde eine race condition oder so per se nichts schädliches anrichten.

---

Der Unterschied ist hier vorzufinden:

If A is not sequenced before B and B is not sequenced before A, then A and B are unsequenced. [ Note: The execution of unsequenced evaluations can overlap. — end note ]
Evaluations A and B are indeterminately sequenced when either A is sequenced before B or B is sequenced before A, but it is unspecified which. [ Note: Indeterminately sequenced evaluations cannot overlap, but either could be executed first. — end note ]

I.e. im Fall n + n++ ist es sogar möglich dass, wie am Anfang des zitierten Paragraphen auch impliziert*, beide Ausdrücke gleichzeitig ausgewertet werden. Das würde zu einer race condition führen. Ich nehme an dass, da die Implementierungen nicht dazu verdonnert werden sollten, derartiges zu behandeln oder ihre Optimierung anzupassen, man es als undefiniert abgestempelt hat.

(Muss es aber nicht sein, ein relativ neues Paper von Sutter und Stroustrup beschäftigt sich damit die Auswertungsreihenfolge festzulegen.)

Wie auch immer, für Funktionen ändert sich die Lage wie folgt:

§1.9/15 schrieb:

Every evaluation in the calling function (including other function calls) that is not otherwise specifically sequenced before or after the execution of the body of the called function is indeterminately sequenced with respect to the execution of the called function.

I.e., die Ausführung des Inkrements innerhalb der Funktion ist indeterminately sequenced im Vergleich zum Zugriff auf den Wert der Variable. Wir haben also lediglich unspezifiziertes Verhalten, das in keinster weise konsistent sein braucht.

* Impliziert wird, dass für den + -Operator keine Ausnahme bezüglich

Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced. [ Note: In an expression that is evaluated more than once during the execution of a program, unsequenced and indeterminately sequenced evaluations of its subexpressions need not be performed consistently in different evaluations. — end note ]

besteht.