Поля и методы в Java: рекурсия и стек вызовов метода

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

Например, предположим, что необходимо написать метод по вычислению факториала - числа, равного произведению всех целых положительных чисел от 1 и до конкретного целого числа включительно. ! - это математический символ факториала, то есть 4! равняется 4x3x2x1, или 24. Первый подход к написанию данного метода может состоять из кода, представленного ниже:

static int fac(int n)
{
int x = 1;
for (int i = 2; i <= n; i++)
x *= i;
return x;
}

И хотя этот код выполняет свою задачу с помощью итерации, fac() с помощью рекурсивного стиля может быть записан более компактно:

static int fac(int n)
{
if (n == 1)
return 1; // базовая проблема
else
return n * fac(n - 1);
}

Рекурсивный подход решает проблему в более простом выражении - с помощью вызова самого себя. Согласно этому примеру, самая простая проблема, которая также известна как базовая проблема, это 1! Когда аргумент больше 1 передается fac(), этот метод разбивает задачу на более простую проблему, вызывающую себя со следующим меньшим значением аргумента. В итоге, базовая проблема решается. Например, вызов fac(4) приводит к следующему сток выражений:

4 * fac(3)
3 * fac(2)
2 * fac(1)

Это последнее выражение находится в вершине стека. Когда fac(1) возвращает 1, эти выражения вычисляются в следующем порядке:

1. 2 * fac(1) теперь становится 2*1 (2)
2. 3 * fac(2) теперь становится 3*2 (6)
3. 4 * fac(3) теперь становится 4*6 (24)

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

Неограниченная рекурсия и стек нехватки пространства

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

Стек вызовов метода

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