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

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

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

Спецификация Scheme точно определяет, какие хвостовые вызовы есть в Scheme, и указывает, что компиляторы поддерживают их специально. Вы можете увидеть определение в 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);
}

Скомпилируйте его, используя обычные настройки оптимизации gcc (-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 может быть сложнее.