Хвостовая рекурсия в C ++ с несколькими рекурсивными вызовами функций

Question

Я читал этот пост о хвостовой рекурсии.

Я скопирую опубликованное решение:

unsigned int f( unsigned int a ) {
   if ( a == 0 ) {
      return a;
   }
   return f( a - 1 );   // tail recursion
}

Мне было интересно, а что, если результат зависит от нескольких рекурсивных вызовов функций?Например:

unsigned int f( unsigned int a ) {
    if ( a == 0 ) {
          return a;
       }
    return f(a -1) + f( a - 1 );   
}

Будет ли приведенный выше код оптимизирован компилятором?

Answer 1

Как есть, рекурсия хвоста не применяется.Но если вы посмотрите в конце второго ответа на вопрос, с которым вы связаны, вы увидите, как правильно переписать функцию.Начиная с

unsigned int f( unsigned int a ) {
    if ( a == 0 ) {
          return a;
    }
    return f(a-1) + f(a-1);   
}

, перепишите его следующим образом:

unsigned int f( unsigned int a ) {
    if ( a == 0 ) {
          return a;
    }
    return 2 * f(a-1);  
}

Даже сейчас хвостовая рекурсия по-прежнему не применяется напрямую.Мы должны убедиться, что возврат строго в форме return f(....).Перепишите функцию еще раз:

unsigned int f( unsigned int a, unsigned int multiplicative_accumulator = 1 ) {
    if ( a == 0 ) {
          return multiplicative_accumulator * a;
    }
    return f(a-1, multiplicative_accumulator * 2 );   
}

Теперь применима хвостовая рекурсия.При этом используется значение по умолчанию для multiplicative_accumulator (спасибо @Pubby), чтобы первый вызов f мог просто быть f(x), в противном случае вам нужно было бы написать что-то f(x,1).

Парапоследние примечания благодаря @SteveJessop:

• Можно было безопасно изменить f(a+1)+f(a+1) на 2*f(a+1), потому что f не имеет побочных эффектов (печать, изменение кучи, и тому подобное).Если бы f имел побочные эффекты, это переписывание было бы недействительным.
• Оригинал был эквивалентен (2*(2*(2*a)) (или, точнее, (((a+a)+(a+a))+((a+a)+(a+a)))), тогда как текущая версия больше похожа на (((2*2)*2)*a).Это хорошо, особенно для целых, потому что умножение является ассоциативным и распределительным.Но это не будет точным эквивалентом для float, где вы, вероятно, получите небольшие расхождения при округлении.С арифметикой с плавающей точкой иногда a*b*c может немного отличаться от c*b*a.

Answer 2

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

unsigned int f_helper(unsigned int a, unsigned int acc)
{
   if (a == 0) {
      return acc;
   }
   return f_helper(a-1, f(a-1)+acc);
}

unsigned int f(unsigned int a) {
    if (a == 0) {
          return a;
    }
    return f_helper(a-1, f(a-1));
}

который вы можете преобразовать в цикл

unsigned int f_helper(unsigned int a, unsigned int acc)
{
   while (a != 0) {
      acc += f(a-1);
      a = a-1;
   }
   return acc;
}

unsigned int f(unsigned int a) {
    if (a == 0) {
       return a;
    }
    return f_helper(a-1, f(a-1));
}

затем положите его обратно в f

unsigned int f( unsigned int a ) {
  if (a == 0) {
      return a;
   }
   unsigned acc = f(a-1);
   a = a-1;
   while (a != 0) {
      acc += f(a-1);
      a = a-1;
   }
   return acc;
}

Answer 3

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

Answer 4

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

Для хорошего объяснения использования C ++ вы можете посмотреть на http://marknelson.us/2007/08/01/memoization/.

В вашем примере последний вызов может быть заменен на

return 2 * f(a - 1);

и это можно было бы оптимизировать.

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