Wie wirkt sich die Rangfolge auf eine rekursive Methode aus?

Question

Ich bin interessiert zu lernen, wie die folgende rekursive Methode behandelt, ist die Rückgabeanweisung. Mit dem Debugger scheint das Methodenargument auf den Stack geschoben zu werden. Bei der Rückkehr wird die Gleichung ausgewertet. Wie werden im Aufrufbaum unten die Werte 1, 2, 6 und 24 generiert?

factorial(5) 
    factorial(4) 
     factorial(3) 
     factorial(2) 
      factorial(1) 
       return 1 
      return 2*1 = 2 
     return 3*2 = 6 
     return 4*6 = 24 
    return 5*24 = 120 

    private static int factorial(int x) 
    { 
     if (x == 1) 
      return 1; 
     return x * factorial(x - 1); 
    } 

Answer 1

Soweit C# kümmert, als ob Sie eine andere Methode aufgerufen haben. Es gibt keine spezifischen Optimierungen für die Rekursion in C#.

Die Reihenfolge der Vorgänge ist in C# definiert, sodass Sie immer wissen, was wann ausgewertet wird. In diesem Fall spielt es jedoch keine Rolle - Sie rufen nur eine Funktion mit einem Argument auf und geben den Wert multipliziert zurück. Keine Magie involviert.

Lassen Sie sich nicht zu sehr von den internen Details des Geschehens ablenken. Argumente werden meistens nicht wirklich durch den Stack geleitet, besonders bei 64-Bit. Es ist auch möglich, dass eine Tail-Call-Optimierung durchgeführt wird (nicht etwas, was der C# -Compiler jetzt tut, aber auch nicht unmöglich), was bedeutet, dass keine Argumente übergeben werden wirklich - Sie verwenden den gleichen Datenstandort für die Daten immer wieder, ähnlich dem Umschreiben der Rekursion, um stattdessen eine Imperativ-Schleife zu verwenden.

Der Debugger versucht, den Code leicht zu debuggen. Dies macht es auch verschiedene aus Code außerhalb des Debuggers ausgeführt. Zum Beispiel wird sich die Lebensdauer von Locals im Debugger auf den gesamten Blockumfang erstrecken, während sie außerhalb des Debuggers nicht mehr garantiert sind, sobald Sie sie das letzte Mal aufrufen. Der Code wird auch neu angeordnet, um die gleichen Singlethread-Operationen beizubehalten und gleichzeitig die Leistung zu verbessern.

Wenn Sie sehen möchten, dass der eigentliche x86-Code ausgeführt wird, können Sie die Anwendung außerhalb des Debuggers ausführen und sie mit Debugger.Launch/Debugger.Break aufrufen - damit können Sie die Debugger-Vereinfachungen umgehen.

In meinem speziellen Fall sieht der entsprechende Code wie folgt aus:

000007FE956204D0 push  rsi 
000007FE956204D1 sub   rsp,20h 
000007FE956204D5 mov   esi,ecx ; store x 
000007FE956204EA lea   ecx,[rsi-1] ; pass x - 1 ... 
000007FE956204ED call  000007FE95620080 ; ... to factorial 
000007FE956204F2 imul  eax,esi ; multiply the return value with stored x 
000007FE956204F5 add   rsp,20h 
000007FE956204F9 pop   rsi 
000007FE956204FA ret 

Wie Sie sehen können, nichts von dem Stapel übergeben. Stattdessen wird der alte Wert von rsi/esi auf dem Stapel beibehalten. Mit tail-call-optimierter Rekursion kann sogar das vermieden werden.