Может ли частично функция хвостовой рекурсии по-прежнему получать преимущества оптимизации полностью хвостовой рекурсивной функции?

Question

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

---

Возможно ли, чтобы функция была частично хвостовой рекурсивной и по-прежнему получила какое-либо преимущество в том, что вы получите хвост-рекурсив?

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

Если у вас есть функция, как это:

def example(arg): 
    if arg == 0: 
     return 0 # base case 

    if arg % 2 == 0: 
     return example(arg - 1) # should be tail recursive 

    return 3 + example(arg - 1) # isn't tail recursive because 3 is added to the result 

Когда Оптимизатор встречает что-то подобное (где функция является хвостовой рекурсией в некоторых случаях и не в других) он будет превратить один в jump а другой - в call, или будет какой-то факт оптимизационной реальности (если бы я знал, что я не прошу), заставить его превратить все в call и потерять всю эффективность, которую вы могли бы иметь, рекурсивная?

Answer 1

В схеме, первом языке, который приходит на ум, когда я думаю о хвостах, второй случай гарантированно является хвостовым вызовом по спецификации языка. (Примечание по терминологии: предпочтительнее ссылаться на такие вызовы функций, как «хвостовые вызовы».)

Спецификация Схемы точно определяет, какие хвостовые вызовы находятся в Схеме и мандаты, которые компиляторы поддерживают их специально. Вы можете увидеть определение в 11.20. Хвост и контекст хвоста R RS (source).

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

Пример, в C:

Возьмите версию C вашего примера.

int example(int arg) 
{ 
    if (arg == 0) 
     return 0; 
    if ((arg % 2) == 0) 
     return example(arg - 1); 
    return 3 + example(arg - 1); 
} 

Собирать с помощью обычных параметров оптимизации ССЗ (-O2) для i386:

_example: 
    pushl %ebp 
    xorl %eax, %eax 
    movl %esp, %ebp 
    movl 8(%ebp), %edx 
    testl %edx, %edx 
    jne L5 
    jmp L15 
    .align 4,0x90 
L14: 
    decl %edx 
    testl %edx, %edx 
    je L7 
L5: 
    testb $1, %dl 
    je L14 
    decl %edx 
    addl $3, %eax 
    testl %edx, %edx 
    jne L5 
L7: 
    leave 
    ret 
L15: 
    leave 
    xorl %eax, %eax 
    ret 

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

Answer 2

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

И вы могли бы оптимизировать вашу функцию, перемещая добавление 3 внутри вызова:

def example(arg, add=0): 
    arg += add 
    .... 
    return example(arg - 1, 3) # tail now too 

Другой метод должен был бы создать вторую функцию и оба называют друг друга.

Я не знаю, могут ли обработчики python или C++ справиться с этим, но вы можете проверить вывод сборки для C++. Странно, я думаю, что проверка вывода байт-кода для python может быть сложнее.