Что такое tail recursion

Что проверяют

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

Как отвечать

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

На виртуальной машине Java хвостовых вызовов нет, поэтому в Kotlin оптимизацию включает модификатор tailrec:

tailrec fun factorial(n: Int, acc: Long = 1): Long =
    if (n <= 1) acc else factorial(n - 1, acc * n)

Без tailrec тот же код останется обычной рекурсией. Признак нехвостовой формы простой: результат вызова участвует в выражении, как в return n * factorial(n - 1), где умножение выполняется уже после возврата. Хвостовую форму получают переносом промежуточного результата в параметр-накопитель.

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

Где спотыкаются

Пишут хвостовую по форме функцию без tailrec и считают, что среда всё сделает сама. Не сделает: получится обычная рекурсия со своим кадром на каждый уровень.

Ставят tailrec и не читают предупреждение компилятора о том, что вызов не в хвостовой позиции. Модификатор стоит, переполнение остаётся, и его ищут в данных.

Ждут от хвостовой формы ускорения. Она про память, а не про скорость: наивный подсчёт чисел Фибоначчи от неё быстрее не станет, потому что там повторные вычисления, а лечатся они запоминанием результатов или пересчётом в цикле.