Рекурсия

Рекурсивный метод решает задачу через вызов себя для меньшей подзадачи. Корректная рекурсия имеет условие завершения и на каждом шаге приближается к нему.

Две обязательные части

static long factorial(int n) {
    if (n < 0) throw new IllegalArgumentException("negative");
    if (n <= 1) return 1;          // базовый случай
    return n * factorial(n - 1);   // переход к меньшей задаче
}

Для factorial(n) время O(n), дополнительная память O(n) из-за frames вызовов. Результат переполняет long уже на сравнительно небольшом n, поэтому пример показывает механику, а не универсальный расчёт факториала.

Что происходит в стеке

Каждый незавершённый вызов хранит параметры, локальные значения и точку возврата. Слишком большая глубина приводит к StackOverflowError. HotSpot не гарантирует tail-call optimization, поэтому хвостовая запись не превращает рекурсию автоматически в цикл.

factorial(4)
  4 * factorial(3)
      3 * factorial(2)
          2 * factorial(1)
          2 * 1
      3 * 2
  4 * 6

Устройство frames: Стек и куча в Java.

Когда рекурсия естественна

обход дерева;
divide and conquer: merge sort, quicksort;
backtracking: варианты маршрута или расстановки;
разбор вложенной структуры;
обход графа с контролем посещённых вершин.

static int sum(Node node) {
    if (node == null) return 0;
    return node.value + sum(node.left) + sum(node.right);
}

У рекурсии по графу без visited возможен бесконечный цикл. У дерева без балансировки глубина может стать O(n), даже если ожидается O(log n).