Окончательный вопрос о рекурсии хвоста

Question

После участия в дискуссии в this fiasco question я хотел бы задать вопрос перед всем сообществом.

В каких сценариях оптимизация хвостового вызова применяется к .Net-коду?

Пожалуйста, поддержите свои ответы с помощью надежных, современных источников или воспроизводимых экспериментов.

Answer 1

Согласно «Эксперту F #», написанному доном Симом и др., F # делает оптимизацию хвостовых вызовов. Кажется, я помню, как читал блог Эрика Липперта, что компилятор C# (любая версия) этого не делает. Поправьте меня, если я ошибаюсь, Эрик. Во всех случаях оптимизации хвостового вызова могут выполняться, когда последняя команда должна вызывать метод. Это часто будет рекурсивным вызовом самого метода, но не обязательно. Оптимизация может быть выполнена, поскольку гарантируется, что текущий стек стека больше не нужен. Однако, если после выполнения просто выполнить операцию, оптимизация не может быть выполнена.

int Fib(int n) 
{ 
    if(n < 2) 
    return 1; 

    return Fib(n-1) + Fib(n-2); 
} 

Это не может быть хвост вызов оптимизирован, потому что + не может быть оценена до последнего вызова Fib возвращается. (На самом деле я думаю, что это пример, используемый в Expert F #, как хорошо, но не уверен в том, что один.)

int Fib(int n, int a, int b) 
{ 
    if(n == 0) 
    return a+b; 
    return Fib(n-1,a+b,a); 
} 

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