Как работает рекурсия под капотом?

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

Понимаете ли вы, что каждый рекурсивный вызов стоит кадра на стеке потока, и откуда берётся StackOverflowError. Следом обычно просят переписать рекурсию итеративно или спрашивают, оптимизирует ли Java хвостовые вызовы.

Как отвечать

У каждого потока JVM свой стек. Вызов метода (invokestatic, invokevirtual) кладёт на него кадр (frame), в котором лежат:

• массив локальных переменных: параметры и локальные переменные, у нестатического метода в нулевой ячейке this;
• стек операндов: промежуточные значения вычислений байт-кода;
• служебные данные: ссылка на пул констант класса и сведения о том, куда вернуться.

При рекурсии кадры копятся, по одному на незавершённый вызов. Когда срабатывает базовый случай, метод возвращает значение, его кадр снимается, и вызывающий продолжает вычисление, например умножает n на результат. Вся «память» рекурсии это эти кадры: объекты лежат в куче, а в кадре только ссылки и примитивы.

Размер стека задаёт флаг -Xss, на 64-битном Linux по умолчанию обычно 1 МБ, отдельному потоку размер можно передать в конструктор Thread. Точную предельную глубину назвать нельзя: она зависит от размера кадров и от того, скомпилировал ли JIT метод. Когда место кончается, летит StackOverflowError. Это Error, а не Exception, и ловить его как штатную ситуацию не принято.

Хвостовые вызовы JVM не оптимизирует. В Kotlin функцию с tailrec компилятор сам превращает в цикл, в Scala так же разворачивается хвостовой самовызов, а @tailrec проверяет, что это удалось. В Java это делают руками: цикл с аккумулятором или явный стек на ArrayDeque для обхода деревьев и графов.

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

Говорят, что Java оптимизирует хвостовую рекурсию. Этого не делают ни javac, ни HotSpot.

Не проверяют некорректный вход: factorial(-1) с базовым случаем n == 0 уходит в бесконечную рекурсию и падает.

Не замечают переполнения типа. Факториал в int ломается уже на 13, в long на 21, стек тут ни при чём.