Wie die Rekursion arbeitet in C

Ich bin neu in C und bin ich beim Lesen über Rekursion, aber ich bin Total verwirrt.

Den wichtigsten Teil, wo ich bin immer verwirrt, ist, wie die Dinge sich entspannen, wenn die exit-Bedingung erreicht ist. Ich würde gerne wissen, wie während der Rekursion die Werte bekam, schob und zog aus dem Stapel.

Also kann jemand bitte geben Sie mir eine grafische Ansicht der Rekursion?

Dank...

InformationsquelleAutor der Frage Amit Singh Tomar | 2011-04-12

  1. 19

    Vermuten lässt, eine Funktion:

    int MyFunc(int counter) {
    //check this functions counter value from the stack (most recent push)

    //if counter is 0, we've reached the terminating condition, return it
    if(counter == 0) {
        return counter;
    }
    else {
        //terminating condition not reached, push (counter-1) onto stack and recurse
        int valueToPrint = MyFunc(counter - 1);

        //print out the value returned by the recursive call 
        printf("%d", valueToPrint);

        //return the value that was supplied to use 
        //(usually done via a register I think)
        return counter;
    }
}

int main() {
    //Push 9 onto the stack, we don't care about the return value...
    MyFunc(9);
}

    Ausgabe: 0123456789

    Ersten mal durch MyFunc, Anzahl ist 9. Scheitert es bei der Kündigung prüfen (es ist nicht 0), so dass der rekursive Aufruf ist aufgerufen, mit (Zähler -1), 8.

    Dies wiederholt, Dekrementieren der Wert auf dem Stapel jedes mal, bis Zähler == 0 ist. An diesem Punkt, der Abbruch-Klausel ausgelöst, und die Funktion gibt einfach den Wert des Zählers (0), in der Regel in einem register.

    Den nächsten Anruf in den stack verwendet den Rückgabewert zu drucken (0), dann kehrt der Wert, der geliefert wurde, wenn es aufgerufen wurde (1). Dies wiederholt sich:

    Den nächsten Anruf in den stack verwendet den Rückgabewert zu drucken (1), liefert dann den Wert, der geliefert wurde, wenn es aufgerufen wurde (2). usw., bis Sie die Spitze.

    So, wenn MyFunc aufgerufen wurde mit 3, die Sie bekommen würde, das entspricht (ohne Berücksichtigung der return-Adressen etc. aus dem stack):

    Call MyFunc(3) Stack: [3]
Call MyFunc(2) Stack: [2,3]
Call MyFunc(1) Stack: [1,2,3]
Call MyFunc(0) Stack: [0,1,2,3]
Termination fires (top of stack == 0), return top of stack(0).
//Flow returns to:
MyFunc(1) Stack: [1,2,3]
Print returned value (0)
return current top of stack (1)

//Flow returns to:
MyFunc(2) Stack: [2,3]
Print returned value (1)
return current top of stack (2)

//Flow returns to:
MyFunc(3) Stack: [3]
Print returned value (2)
return current top of stack (3)

//and you're done...

    InformationsquelleAutor der Antwort forsvarir

  2. 6

    Wie die Dinge entspannen, wenn die exit-Bedingung erreicht ist?

    Erste, paar Worte über Rekursion: eine Teile und herrsche-Methode für komplexe Aufgaben, die allmählich zersetzt und reduziert auf eine einfache Instanzen von der ursprünglichen Aufgabe, bis eine form(base-case -)ermöglicht den direkten Berechnung erreicht ist. Es ist eine Vorstellung, die eng mit mathematische Induktion.

    Genauer gesagt, eine rekursive Funktion ruft sich selbst direkt oder indirekt. In der direkten Rekursion-Funktion foo()macht einen anderen Anruf zu sich selbst. Bei der indirekten Rekursion, Funktion foo() macht ein Aufruf der Funktion moo()die wiederum ruft die Funktion foo() werden, bis der basisfall erreicht ist, und dann das endgültige Ergebnis wird sich in der genau umgekehrten Reihenfolge der ersten rekursiven Aufruf der Funktion.

    Beispiel:

    Fakultät ngekennzeichnet n!ist das Produkt der positiven ganzen zahlen von 1 zu n. Die Fakultät kann formal wie folgt definiert:
    factorial(0)=1(base-case -)
    factorial(n)= n * factorial(n-1)für n > 0. (rekursiven Aufruf)

    Rekursion zeigt sich in dieser definition wie definieren wir factrorial(n) in Bezug auf factorial(n-1).

    Jeder Rekursion-Funktion sollte Abbruchbedingung zu Ende der Rekursion. In diesem Beispiel, wenn n=0die Rekursion Stoppt. Die oben genannten Funktion, ausgedrückt in C ist:

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

    Diesem Beispiel ist ein Beispiel für direkte Rekursion.

    Wie wird diese umgesetzt? Auf der Ebene der software, Ihre Implementierung unterscheidet sich nicht von der Umsetzung anderer Funktionen(Prozeduren). Sobald Sie verstehen, dass jeder procedure call Beispiel unterscheidet sich von den anderen, die Tatsache, dass eine rekursive Funktion ruft sich selbst macht keinen großen Unterschied.

    Jede aktive Verfahren unterhält eine Aktivierungs-recorddie auf dem stack gespeichert werden. Die Aktivierung Datensatz besteht aus der ArgumenteAbsender-Adresse (der Anrufer)und lokale Variablen.

    Den Aktivierungs-Eintrag kommt zustande, wenn eine Prozedur aufgerufen wird, und verschwindet, nachdem die Prozedur beendet und das Ergebnis wird an den Aufrufer zurückgegeben. So, für jedes Verfahren, das nicht terminiert ist, wird ein Aktivierungs-record enthält, den Status der Prozedur gespeichert ist. Die Anzahl der activation records, und damit die Menge der stack-Platz benötigt, um das Programm auszuführen, hängt von der Tiefe der Rekursion.

    Auch kann jemand bitte geben Sie mir eine grafische Ansicht der Rekursion?

    Nächste Abbildung zeigt der Aktivierungsstatus für fakultaet(3):

    Wie die Rekursion arbeitet in C

    Wie Sie der Abbildung entnehmen können, wird jeder Aufruf an die Fakultät erstellt eine Aktivierung aufnehmen, bis der basisfall erreicht ist und ab dort sammeln wir das Ergebnis in form von Produkt.

    InformationsquelleAutor der Antwort Ziezi

  3. 5

    C-Rekursion ist wie normale Funktionsaufrufe.

    1. Wenn eine Funktion aufgerufen wird, die Argumente, die Rückkehr-Adresse und frame-pointer (ich habe vergessen die Reihenfolge) auf den stack geschoben.
    2. In der aufgerufenen Funktion, wird zuerst der Speicherplatz für die lokalen Variablen werden per "PUSH" auf dem stack.
    3. wenn die Funktion etwas zurückgibt, legen Sie Sie in einem bestimmten register (abhängig von der Architektur, AFAIK)
    4. undo-Schritt 2.
    5. undo-Schritt 1.

    So, mit Rekursion die Schritte 1 und 2 sind durchgeführt, ein paar mal, dann vielleicht 3 (vielleicht nur einmal) und schließlich 4 und 5 sind fertig (wie oft, wie 1 und 2).

    InformationsquelleAutor der Antwort subsub

  4. 3

    Alternative Antwort ist, dass Sie in der Regel nicht kennen. C als Sprache hat keine stack-heap. Dein compiler verwendet einen Speicherbereich namens stack, store-control-flow-Informationen wie stack-frames, return-Adressen und-Register, aber es gibt nichts in C verbietet dem compiler, der zum speichern dieser Informationen an anderer Stelle. Für die praktischen Aspekte der vorherigen Antworten sind korrekt. Dies ist, wie der C-Compiler arbeiten heute.

    InformationsquelleAutor der Antwort Nikos

  5. 1

    Diese Frage wurde vielfach beantwortet. Erlauben Sie mir bitte auch eine zusätzliche Antwort mit einem stärker pädagogischen Ansatz.

    Können Sie denken, Funktion Rekursion als ein Stapel von Blasen mit zwei Phasen unterscheiden: die betätigung der Bühne und platzen der Bühne.

    A) SCHIEBEN BÜHNE (oder "Schieben Sie den Stapel" wie OP nennen),

    0) Der Start Bubble #0 ist die MAIN-Funktion. Es wird geblasen bis mit diesen Informationen:

    • Lokalen Variablen.
    • Der Anruf an die nächste Blase #1 (der erste Aufruf der rekursiven
      Funktion MYFUNC).

    1) Bubble #1 die Luft gesprengt wird, auf die wiederum mit diesen Informationen:

    • Parameter aus der vorherigen Blase #0.
    • Lokalen Variablen wenn notwendig.
    • Eine Rückkehr-Adresse.
    • Beendigung mit einem Rückgabewert (zB: if (counter == 0) {return 1}).
    • Ein Aufruf an die nächste Blase #2.

    Denken Sie daran, dass diese Blase, als die andere Blasen, ist die rekursive Funktion MYFUNC.

    2) Blase #2 die Luft gesprengt wird, mit den gleichen Informationen wie Bubble #1, von den letzteren die erforderlichen Eingaben (Parameter). Nach diesem Zeitpunkt können Sie stapeln Sie so viele Blasen wie Sie wollen, das aufblasen der Daten entsprechend der aufgeführten Elemente in Bubble #1.

    i), So erhalten Sie so viele Blasen wie Sie will: Blasen - #3, Bubble #4..., Bubble #ich. Die Letzte Blase hat einen NAGEL in der Kündigung prüfen. Sich bewusst sein!

    B) PLATZEN der BÜHNE (oder "Knallen stack" wie OP nennen),

    Dieser Phase passiert, wenn Sie erreichen die positiven Abbruch zu überprüfen und die Letzte Blase mit dem Nagel ist geplatzt.

    Sagen wir, dieser Bühne passiert, in Bubble #3. Die positive Beendigung check erreicht ist und die Blase #3 ist geplatzt. Dann den NAGEL aus dieser Blase zu befreien. Der Nagel fällt auf, dass die Unterseite Blase #2 und brach es. Dies geschieht nach den Nagel folgt seinen fall, bis er burst Bubble #1. Das gleiche passiert, Bubble #0. Es ist wichtig zu bemerken, dass der Nagel folgt die Rückkehr-Adresse in die Blase, dass es zu platzen im moment: die Adresse sagt, der Nagel, der Richtung zu Folgen, während fallen.

    Am Ende dieses Prozesses, die Antwort erhalten wird, und geliefert an die MAIN-Funktion (oder die Sprechblase #0, was natürlich nicht platzen).

    C) GRAPHISCH (als OP gefragt)

    Dies ist die grafische Erklärung. Es entwickelt sich von unten, Blase, #0 nach oben, Blase #3.

    /*Bubble #3 (MYFUNC recursive function): Parameters from Bubble #2,
local variables, returning address, terminating check (NAIL),
call (not used here, as terminating check is positive).*/

    Drücken bis die Blase über ↑ ----------------------------------------------------- ? Nagel fällt, Blase #2

    /*Bubble #2 (MYFUNC recursive function): Parameters from Bubble #1,
local variables, returning address, terminating check (not used),
call to Bubble #3.*/

    Drücken bis die Blase über ↑ ----------------------------------------------------- ? Nagel fällt zu Bubble #1

    /*Bubble #1 (MYFUNC recursive function): Parameters from Bubble #0,
local variables, returning address, terminating check (not used),
call to Bubble #2.*/

    Drücken bis die Blase über ↑ ----------------------------------------------------- ? Nagel fällt zu Bubble #0

    /*Bubble #0 (MAIN function): local variables, the first call to Bubble #1.*/

    Hoffe, dieser Ansatz hilft jemand. Lassen Sie mich wissen, ob eine Klarstellung erforderlich ist.

    InformationsquelleAutor der Antwort Carlos W. Mercado

Schreibe einen Kommentar