Rekursive Funktionen, alle Zweige immer mit return versehen?

Tamoko

Ich habe eine Frage zu rekursiven Funktionen allgemein und zwar zeichnet sich eine rekursive Funktion ja dadurch aus, dass sie sich selbst wieder auffruft und es min. eine Abbruchbedingung gibt.
Mir ist dabei etwas aufgefallen: In manchen Funktionen wenn man z.B. rechnet (Fakultätsfunktion rekursiv) braucht man ja zwingend ein return, weil das Ergebnis ja immer in den nächst höheren Funktionsaufruf weitergereicht werden muss. Es gibt aber Situationen in denen es egal zu sein scheint, ob man vor den rekursiven Aufruf ein return schreibt oder nicht.
Im Folgenden Beispiel macht es keinerlei Unterschied:

char* reverse(char const *wort, char *revWort, int const size, int z)
{
    if(z == size)
        return revWort;
    else {
        revWort[z] = wort[size-1-z];
        reverse (wort, revWort, size, ++z);
    }
}

char* reverse(char const *wort, char *revWort, int const size, int z)
{
    if(z == size)
        return revWort;
    else {
        revWort[z] = wort[size-1-z];
        return reverse (wort, revWort, size, ++z);
    }
}

Gibt es da ne allgemeine Richtlinie wie eine rekursive Funktion möglichst aufgebaut sein sollte? Oder schreibt man generell einfach vor jeden Zweig (ob rekursiv oder nicht nicht rekursiv) ein return.
Selbst bei void Funktionen wie der Folgenden?

void printNumbers(int n)
{
    if(n == 1)
        cout << "1" << endl;
    else {
        cout << n << endl;
        return printNumbers(n-1);   // Hier ists ja theoretisch voellig egal
    }
}

In anderen Fällen kann man eine Funktion so umstrukturieren, dass man auch ohne return auskommt.

bool palindrom(char word[], int size, int p)
{
    if(size == 1)
        return true;
    if(p < size/2){
        if(word[p] == word[size-1-p]){
            palindrom(word, size, ++p);
        }else
            return false;
     }
     return true;
}

bool palindrome(char word[], int size, int p)
{
    if(size == 1 || p == size/2)
        return true;
    if(word[p] == word[size-1-p])
        return palindrom(word, size, ++p);
    return false;
}

Gibt es da eine allgemeine Richtlinie wie eine rekursive Funktion möglichst aufgebaut sein sollte? Oder schreibt man generell einfach vor jeden Zweig (ob rekursiv oder nicht nicht rekursiv) immer ein return?

Danke für eure Geduld.

Mechanics

Warum sollte man da grundsätzlich ein return schreiben, erst recht, wenn die Funktion void zurückgibt? Außerdem muss das semantisch auch gar nicht Sinn ergeben.

Was ich z.B. öfter habe, sind rekursive Funktionen, die Baumstrukturen (z.B. in der GUI) durchlaufen und etwas machen. Kann gut sein, dass so eine Funktion eine Datenstruktur per Referenz reinbekommt und die auffüllt. Und kann gut sein, dass da eine Schleife ist, die für jeden Unterknoten wieder rekursiv die Funktion aufruft - das ist aber kein return.

Im Folgenden Beispiel macht es keinerlei Unterschied:

Doch, die ohne return ist falsch und ein Compiler wird eine Warnung ausgeben, wenn du Warnungen einschaltest (was du immer tun solltest).

Da du den Wert nicht benutzt, kannst du alternativ auch eine void Funktion schreiben.

Swordfish

Rekursive Funktionen, alle Zweige immer mit return versehen?

Sorry, ich habe deinen Text nicht gelesen. Aber es gilt die Faustregel: Rechtshänder die rechte Faust, linkshänder die linke.

Ne, ernsthaft: Gibt eine Funktion mit einem Rückgabetyp (edit gegen Klugscheißer: einem Rückgabetyp der nicht void ist) nichts zurück und du verwendest den (nicht) zurückgegebenen Wert ist es undefined behavior. Mehr gibt es dazu eigentlich nicht zu sagen. Sonst kannst du return; schreiben so oft du lustig bist.

//edit: Da steht die Kacke:

[stmt.return]:

[...] Flowing off the end of a constructor, a destructor, or a non-coroutine function with a cv void return type is equivalent to a return with no operand. Otherwise, flowing off the end of a function other than main or a coroutine ([dcl.fct.def.coroutine]) results in undefined behavior.

//edit: was interessanteres ...

@Swordfish sagte in Rekursive Funktionen, alle Zweige immer mit return versehen?:

undefined behavior

schreibt ihr eigendlich BE oder AE?

It0101

Die Antwort ist: ja
Jeder mögliche Weg durch eine Funktion sollte einen Wert zurückgeben, sofern es kein void-Rückgabewert ist. Das gilt nicht nur für Rekursionen, sondern für alle Funktionen.

Deine Funktion 'palindrom' ( unabhängig von ihrer Funktionalität ) würde bei mir so aussehen:


bool palindrom( const std::string &word, int position = 0 )
{
    if ( word.empty() )
        return false; // String ist leer

    if ( word.size() == 1 )
        return true; // Woerter der Laenge eins sind immer Palindrome

    if ( position >= word.size() / 2 )
        return true; // Haben die Haelfte des Wortes ueberschritten. Wenn bis hierher nie 'false' aufgerufen wurde, ist es ein Palindrom

    if ( word[ position ] != word[ word.size() - 1 - position ] )
        return false; // Kein Palindrom, da Buchstaben unterschiedlich sind

    return palindrom( word, ++position );
}

Man sieht durch diese Schreibweise in der Funktion ganz gut, dass jeder mögliche Weg durch die Funktionen auch ein "return" hat.

Bashar

Dein reverse funktioniert, weil die Rückgabe des rekursiven Aufrufs im gleichen Register steht wie das wo die Rückgabe der Funktion selbst erwartet wird (was irgendwo logisch ist, weil es dieselbe Funktion ist.) Offensichtlich ist das nicht koscher, weil der Compiler sich jederzeit entscheiden kann das anders zu machen, und daher undefined behavior.

TGGC

@Tamoko sagte in Rekursive Funktionen, alle Zweige immer mit return versehen?:

: In manchen Funktionen wenn man z.B. rechnet (Fakultätsfunktion rekursiv) braucht man ja zwingend ein return,

Das ist offensichtlich falsch. Es gibt ja keine Vorgabe, das ein Ergebnis unbedingt der return Value zu sein hat.

fac(int& r,int f){r = f<2?1:f*fac(f-1);}

ne aber bei einer funktion, die einen wert zurück gibt, sollte man auch eine entsprechende anweisung geben.
ob die rechenwerte über den rückgabewert, über referenzen oder über globale variablen ausgetauscht werden, ist bei rekursion völlig unerheblich.

TGGC

Das ist genau was ich sagte: "ob die rechenwerte über den rückgabewert, über referenzen oder über globale variablen ausgetauscht werden, ist bei rekursion völlig unerheblich" und das ein Rückgabewert in einigen Sprachen mit return zurückgegeben wird, sind zwei orthogonale Fakten.

Swordfish

@Swordfish sagte in Rekursive Funktionen, alle Zweige immer mit return versehen?:

Gibt eine Funktion mit einem Rückgabetyp [...] nichts zurück und du verwendest den (nicht) zurückgegebenen Wert ist es undefined behavior.

Da war doch was. Ich habe es schon geahnt daß ich da blödsinn geschrieben habe. Das ist einer der netten subtilen Unterschiede zwischen C und C++. In C++ ist es schon undefined behaviour wenn das return-statement fehlt. In C erst wenn man das (nicht) zurückgegebene dingsti verwendet.

ISO/IEC 9899:201x N1570 §6.9.1/12:

If the } that terminates a function is reached, and the value of the function call is used by the caller, the behavior is undefined.

Also

C

int foo(void) {}

int main(void)
{
    foo();
}

darf man, aber

C++

int foo() {}

int main()
{
    foo();
}

darf man strenggenommen nicht tunfisch. Aber

C

int foo(void) {}

int main(void)
{
    int bar = foo();
}

darf man wiederum auch nicht. Das darf man aber wirklich wirklich nicht. Das (nicht) zurückgegebene dingsti könnte zufällig je nach Typ eine trap representation sein die durch die Zuweisung zwangsweise gelesen würde.

(edit für Klugscheißer: wenn jetzt jemand daherkommt der mir erzählt daß es wegen no effect und as-if sowieso jeder compiler ignorieren kann ... ich schwör alter. amoklauf.)

ja eigentlich ist das alles ganz einfach. keine ahnung, warum die leute immer meinen, sie müssten irgendwelche experimente ala "kann man nicht auch...?" machen.