• Напоминание про стек вызовов

Определение

Хвостовая рекурсия — это специфичная форма рекурсии, в которой (каждый) вызов рекурсивной функции находится в “хвостовой позиции”, что означает, что вызов происходит перед возвратом функции (после возврата не нужно выполнять дополнительных вычислений)

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

Преимущества использования хвостовой рекурсии

• улучшенная производительность

  Поскольку компилятор может оптимизировать вызов функции при помощи цикла, хвостовые рекурсии могут быть намного более эффективными, чем обычные

• уменьшение использования стека

• хвостовая рекурсия может быть преобразована в итерацию с помощью CPS (из фп2022, не понял почему это преимущество, но вдруг кто-то знает)

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

Некоторый рецепт по преобразованию рекурсивной функции в хвостовую

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