In Bezug auf Stack-Wiederverwendung einer Funktion selbst aufrufen?

Question

Wenn sich eine Funktion bei der Definition von Variablen zur selben Zeit selbst aufruft würde dies zu einem Stapelüberlauf führen? Gibt es in gcc eine Option, denselben Stack wiederzuverwenden?

void funcnew(void) 
{ 
    int a=10; 
    int b=20; 
    funcnew(); 
    return ; 
} 

kann eine Funktion den Stack-Frame wiederverwenden, den sie früher verwendet hat? Was ist die Option in gcc, um den gleichen Frame in Tail-Rekursion wieder zu verwenden?

Answer 1

Nein, jede Rekursion ist ein neuer Stapelrahmen. Wenn die Rekursion unendlich tief ist, ist der benötigte Stapel ebenfalls unendlich, so dass Sie einen Stapelüberlauf erhalten.

Answer 2

Auch ohne die Parameter zu definieren, erhalten Sie einen Stackoverflow. Da wird die Rücksendeadresse auch auf den Stack geschoben.

Es ist (ich habe das kürzlich gelernt) möglich, dass der Compiler Ihre Schleife in eine Tail-Rekursion optimiert (wodurch der Stack überhaupt nicht wächst). Link to tail recursion question on SO

Answer 3

Ja. Siehe

-foptimize-Geschwister-Anrufe

Optimize Geschwister und Schwanz rekursive Aufrufe.

Aktiviert bei den Pegeln -O2, -O3, -Os.

Ihre Funktion kompiliert wird:

funcstack: 
.LFB0: 
    .cfi_startproc 
    xorl %eax, %eax 
    jmp func 
    .cfi_endproc 

(beachten Sie den Sprung zu func)

den Stapelrahmen wiederverwendet, wenn eine Funktion Ende durch einen Aufruf - das in seiner vollen Allgemeinheit gehören Manipulation der Stack, um die Parameter an die richtige Stelle zu setzen und den Funktionsaufruf durch einen Sprung an den Anfang der Funktion zu ersetzen - ist eine bekannte Optimierung namens [i] tail call removal [/ i]. Es wird von einigen Sprachen (zum Beispiel Schema) für rekursive Aufrufe vorgeschrieben (ein rekursiver Aufruf ist die natürliche Art, eine Schleife in diesen Sprachen auszudrücken). Wie oben erwähnt, hat gcc die Optimierung für C implementiert, aber ich bin mir nicht sicher, welcher andere Compiler es hat, ich würde nicht davon für portablen Code abhängig sein. Und beachte, dass ich nicht weiß, welche Einschränkung es gibt - ich bin mir nicht sicher, dass zum Beispiel gcc den Stapel manipuliert, wenn die Parametertypen unterschiedlich sind.

Answer 4

Ja, in einigen Fällen kann der Compiler etwas ausführen, das Endanrufoptimierung genannt wird. Sie sollten das mit Ihrem Compiler-Handbuch überprüfen. (AProgrammer scheint das GCC-Handbuch in seiner Antwort zitiert zu haben.)

Dies ist eine wesentliche Optimierung, wenn beispielsweise funktionale Sprachen implementiert werden, in denen ein solcher Code häufig vorkommt.

Answer 5

Sie können den Stapelrahmen insgesamt nicht löschen, da er für die Rücksendeadresse benötigt wird. es sei denn, Sie verwenden die Tail-Rekursion, und Ihr Compiler hat sie zu einer Schleife optimiert. Aber um technisch völlig ehrlich zu sein, können Sie alle Variablen im Rahmen beseitigen, indem Sie sie statisch machen. Allerdings ist dies mit ziemlicher Sicherheit nicht was Sie tun möchten, und Sie sollten es nicht tun, ohne genau zu wissen, was Sie tun, die Sie als diese Frage zu stellen hatten, tun Sie nicht.

Answer 6

Wie andere bereits angemerkt haben, ist dies nur möglich, wenn (1) Ihr Compiler die Tail Call-Optimierung unterstützt und (2) Ihre Funktion für eine solche Optimierung geeignet ist. Die Optimierung besteht darin, den vorhandenen Stapel wiederzuverwenden und ein JMP (d. H. Ein GOTO in Assembly) anstelle eines CALLs auszuführen.

Tatsächlich ist Ihre Beispielfunktion tatsächlich für eine solche Optimierung geeignet. Der Grund dafür ist, dass das Letzte, was Ihre Funktion vor der Rückkehr macht, sich selbst anrufen soll; es muss nichts tun nach der letzte Anruf an funcnew(). Allerdings werden nur bestimmte Compiler eine solche Optimierung durchführen. GCC zum Beispiel wird es tun. Weitere Informationen finden Sie unter Which, if any, C++ compilers do tail-recursion optimization?

Das klassische Material dazu ist die faktorielle Funktion. Lassen Sie uns eine rekursive faktorielle Funktion machen, die nicht für Tail-Call-Optimierung (TCO) geeignet ist.

int fact(int n) 
{ 
    if (n == 1) return 1; 
    return n*fact(n-1); 
} 

Das letzte, was sie tut, ist n mit dem Ergebnis aus fact(n-1) zu multiplizieren. Indem wir diese letzte Operation irgendwie eliminieren, könnten wir den Stapel wiederverwenden. Lassen Sie uns einen Akkumulator Variable einzuführen, die Antwort wird für uns berechnen:

int fact_helper(int n, int acc) 
{ 
    if (n == 1) return acc; 
    return fact_helper(n-1, n*acc); 
} 

int fact_acc(int n) 
{ 
    return fact_helper(n, 1); 
} 

Die Funktion fact_helper die Arbeit macht, während fact_acc nur eine Komfortfunktion ist der Akkumulator Variable zu initialisieren.

Beachten Sie, wie die letzte Sache fact_helper ist, sich selbst zu nennen. Dieser CALL kann in einen JMP konvertiert werden, indem der vorhandene Stapel für die Variablen wiederverwendet wird.

Mit GCC, können Sie überprüfen, ob es an der generierten Assembly, indem man auf einen Sprung optimiert, zum Beispiel :

... 
    37     L12: 
    38 0040 0FAFC2    imull %edx, %eax 
    39 0043 83EA01    subl $1, %edx 
    40 0046 83FA01    cmpl $1, %edx 
    41 0049 75F5     jne  L12 
    ... 

Einige Programmiersprachen wie Scheme wird, dass tatsächlich garantieren, richtige Implementierungen führe solche Optimierungen durch. Sie werden es sogar für nicht-rekursive Tail-Calls tun.