Рекурсия хвоста в C++ с многократными рекурсивными вызовами функций

Question

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

я скопирую отправили решение:

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

Поскольку это означает, рекурсия хвоста не применяется. Но если вы посмотрите на конец second answer на вопрос, с которым вы связались, вы можете увидеть, как правильно переписать функцию. Начиная с

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); 
} 

Теперь применяется рекурсия хвоста. Это использует значение по умолчанию для multipicative_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). Это прекрасно, особенно для ints, потому что умножение является ассоциативным и дистрибутивным. Но это не будет точным эквивалентом для float, где вы, вероятно, получите небольшие округлые расхождения. С арифметикой с плавающей запятой иногда a*b*c может немного отличаться от c*b*a.

Answer 2

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

Answer 3

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

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)); 
} 

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

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 4

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

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

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

return 2 * f(a - 1); 

и что бы оптимизируемыми.

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