Как порядок приоритета влияет на рекурсивный метод?

Question

Мне интересно узнать, как следующий рекурсивный метод обрабатывает оператор return. С помощью отладчика кажется, что аргумент метода попадает в стек. Затем по возвращении вычисляется уравнение. В дереве вызовов ниже, как генерируются значения 1, 2, 6 и 24?

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

Насколько C# заботится, как если бы вы вызвали какой-либо другой метод. Оптимизаций для рекурсии в C# нет.

Порядок операций определен на C#, поэтому вы всегда знаете, что оценивалось, когда. В этом случае, однако, это не имеет большого значения - вы просто вызываете функцию с аргументом и возвращаете значение, умноженное. Никакой магии не было.

Не углубляйтесь в внутренние детали происходящего. Аргументы на самом деле не проходят через стек большую часть времени, особенно на 64-битных. Также возможно выполнение оптимизации хвостового вызова (не то, что сейчас делает компилятор C#, но не невозможно), что означает отсутствие аргументов действительно - вы повторно используете одно и то же местоположение данных для данных снова и снова, аналогично переписыванию рекурсии вместо использования императивного цикла.

Отладчик делает все возможное, чтобы код был легко отлаживаться. Это также делает разными из кода, запускаемого за пределами отладчика. Например, время жизни локалей в отладчике распространяется на всю область их блоков, а за пределами отладчика их больше не гарантируют существование, как только вы обращаетесь к ним в последний раз. Код также переупорядочен для сохранения одних и тех же однопоточных операций при одновременном повышении производительности.

Если вы хотите увидеть фактическое выполнение кода x86, вы можете запустить приложение вне отладчика и вызвать его с помощью Debugger.Launch/Debugger.Break - это позволит вам обойти упрощения отладчика.

В моем конкретном случае соответствующий код выглядит следующим образом:

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 

Как вы можете видеть, ничего не передается в стек. Вместо этого старое значение rsi/esi сохраняется в стеке. С оптимизированной рекурсией с хвостовым вызовом даже этого можно избежать.