Выполнение хвостовой рекурсии в С++

Ответ 1

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

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

Я рекомендую переписать его таким образом, чтобы он ясно дал понять читателю, что происходит, но не полагается на оптимизацию хвостов для компилятора. Несмотря на ненависть, инструкция goto может быть очень полезна для этого.

Возьмите простую функцию рекурсивного подсчета бит:

int bitcount(unsigned int n, int acc = 0) {
  if (n == 0)
    return acc;

  return bitcount(n >> 1, acc + (n & 1));
}

Его можно тривиально переписать как

int bitcount(unsigned int n, int acc = 0) {
tail_recurse:
  if (n == 0)
    return acc;

  // tail return bitcount(n >> 1, acc + (n & 1));
  acc += n & 1;
  n = n >> 1;
  goto tail_recurse;
}

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

Ответ 2

С помощью GCC вы можете добавить проверку времени выполнения с помощью функции backtrace():

#include <cassert>
#include <iostream>
#include <execinfo.h>

size_t start;

size_t stack_frames()
{
  void *array[16];
  size_t size = backtrace(array, 16);

  // std::cout << "Obtained " << size << " stack frames.\n";
  return size;
}

bool missing_tail()
{
  return stack_frames() > start + 2;
}

int bitcount(unsigned int n, int acc = 0)
{
  assert(!missing_tail());

  if (n == 0)
    return acc;

  return bitcount(n >> 1, acc + (n & 1));
}

int main()
{
  start = stack_frames();

  std::cout << bitcount(10) << '\n';

  return 0;
}

При компиляции с уровнем оптимизации ниже -O2 (без оптимизации хвостовой рекурсии) вы получаете отказ от утверждения.