Что такое хвостовая рекурсия и чем она хороша

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

Знаете ли вы определение и, главное, понимаете ли, что выгода от хвостовой рекурсии появляется только тогда, когда её реализует компилятор или среда исполнения. Для Java это ключевой момент: правильный ответ здесь противоречит заученному из общих статей.

Как отвечать

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

Классический приём приведения к хвостовому виду это аккумулятор:

// не хвостовая: после вызова остаётся умножение
static long fact(int n) {
    return n == 0 ? 1 : n * fact(n - 1);
}

// хвостовая по форме
static long fact(int n, long acc) {
    return n == 0 ? acc : fact(n - 1, n * acc);
}

И сразу главное: виртуальная машина Java такой оптимизации не делает, компилятор языка тоже. Кадры нужны для трассировки и обхода стека вызовов, и замену их циклом в язык не завезли. Поэтому в Java хвостовая форма сама по себе не спасает от переполнения стека, и глубокую рекурсию переписывают циклом либо явным стеком в куче. Если упомянуть соседей по платформе, компилятор Kotlin разворачивает самовызов, помеченный tailrec, в цикл, а в Scala похожую роль играет аннотация проверки хвостовой формы.

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

Уверенно обещают, что хвостовая рекурсия снимает переполнение стека в Java. Не снимает: глубина по-прежнему ограничена размером стека потока, и обход большой структуры падает точно так же.

Называют хвостовым вызов, после которого остаётся работа. Умножение результата, конкатенация, обёртка в try или в синхронизированный блок делают вызов не хвостовым, потому что кадр нужен для продолжения.

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