Рекурсия в Java

Рекурсия - это способность метода вызывать самого себя. Такой прием позволяет сократить количество строк кода и увеличить читаемость метода. Проще всего будет разобраться на примере вычисления факториала.

public int factorial(int n) {
   if (n < 2) {
       return 1;
   }
   return factorial(n - 1) * n;
}

Факториал - это произведение всех натуральных чисел от 1 до n включительно и записывается как n!. Пример: 4! = 1 * 2 * 3 * 4 = 24.

В начале метода есть условие if, оно необходимо чтобы завершить нашу цепочку наших рекурсивных вызовов. В любом рекурсивном методе должно быть подобное условие, оно называется точка возврата.
Точка возврата - условие при котором завершается рекурсивный вызов метода. При рекурсивном походе, мы каждый раз передаем новые локальные переменные в метод, которые сохраняются в стек и удаляются из него при вызове return. Если точка возврата будет отсутствовать, то наш метод будет вызывать самого себя бесконечно. В результате это приведет к переполнению стека и исключению StackOverflowError.

Вызовем приведенный выше метод с параметром 4 (factorial(4)) по шагам. 

Стоить отметить, что в нем вычисление факториала происходит в обратном порядке: 4! = 4 * 3 * 2 * 1 = 24.

1. n = 4. Текущая формула факториала: 4! = factorial(4). 4 не меньше чем 2, условие не верно. Возвращаем  factorial(3) * 4;
2. n = 3. Текущая формула факториала: 4! = factorial(3) * 4. 3 не меньше чем 2, условие не верно. Возвращаем factorial(2) * 3;
3. n = 2. Текущая формула факториала 4! = factorial(2) * 3 * 4. 2 не меньше чем 2, условие не верно. Возвращаем factorial(1) * 2;
4. n = 1. Текущая формула факториала 4! = factorial(1) * 2 * 3 * 4. 1 меньше чем 2, условие верно. Возвращаем 1;
5. Итоге 4! = 1 * 2 * 3 * 4 = 24.