Какие компиляторы C++ выполняют оптимизацию хвостовой рекурсии, если таковые имеются?

Все текущие основные компиляторы выполняют оптимизацию хвостового вызова довольно хорошо (и работает уже более десяти лет), даже для взаимно рекурсивных вызовов, например:

int bar(int, int);

int foo(int n, int acc) {
    return (n == 0) ? acc : bar(n - 1, acc + 2);
}

int bar(int n, int acc) {
    return (n == 0) ? acc : foo(n - 1, acc + 1);
}

Позволить компилятору выполнить оптимизацию просто: просто включите оптимизацию для скорости:

• Для MSVC используйте /O2 или /Ox.
• Для GCC, Clang и ICC используйте -O3.

Простой способ проверить, выполнил ли компилятор оптимизацию, - это выполнить вызов, который в противном случае привел бы к переполнению стека, или посмотреть на вывод сборки.

В качестве интересного исторического примечания, оптимизация хвостового вызова для C была добавлена ​​в GCC в ходе дипломная работа Марком Пробстом. В дипломной работе описаны некоторые интересные нюансы при реализации. Это стоит прочитать.

Большинство компиляторов не оптимизируют отладочную сборку.

Если вы используете VC, попробуйте сборку релиза с включенной информацией PDB - это позволит вам проследить через оптимизированное приложение, и вы, надеюсь, тогда увидите то, что хотите. Обратите внимание, однако, что отладка и отслеживание оптимизированной сборки заставят вас повсюду прыгать, и часто вы не можете напрямую проверять переменные, поскольку они только попадают в регистры или полностью оптимизируются. Это «интересный» опыт ...

Как упоминает Грег, компиляторы не будут делать этого в режиме отладки. Это нормально, если отладочная сборка будет медленнее, чем производственная сборка, но они не должны падать чаще: и если вы зависите от оптимизации хвостового вызова, они могут делать именно это. Из-за этого часто лучше переписать хвостовой вызов как обычный цикл. :-(

gcc 4.3.2 полностью встраивает эту функцию (дрянная / тривиальная реализация atoi()) в main(). Уровень оптимизации - -O1. Я замечаю, что если я поиграюсь с ним (даже меняя его с static на extern, хвостовая рекурсия уходит довольно быстро, так что я бы не стал зависеть от этого для правильности программы.

#include <stdio.h>
static int atoi(const char *str, int n)
{
    if (str == 0 || *str == 0)
        return n;
    return atoi(str+1, n*10 + *str-'0');
}
int main(int argc, char **argv)
{
    for (int i = 1; i != argc; ++i)
        printf("%s -> %d\n", argv[i], atoi(argv[i], 0));
    return 0;
}

Помимо очевидного (компиляторы не выполняют такого рода оптимизацию, если вы этого не попросите), существует сложность оптимизации хвостового вызова в C++: деструкторы.

Учитывая что-то вроде:

   int fn(int j, int i)
   {
      if (i <= 0) return j;
      Funky cls(j,i);
      return fn(j, i-1);
   }

Компилятор не может (как правило) оптимизировать этот хвостовой вызов, потому что ему нужно для вызова деструктора clsпосле рекурсивный вызов возвращается.

Иногда компилятор видит, что деструктор не имеет видимых извне побочных эффектов (поэтому это можно сделать на ранней стадии), но часто это не так.

Особенно распространенная форма этого - когда Funky на самом деле является std::vector или аналогичным.