Поля и методы в 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 работает этой посудомоечной машиной - выталкивает следующий чистый поднос только тогда, когда забрали предыдущий.
Автор этого материала - я - Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML - то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.

тегистатьи IT, java, поля и методы




Отправляя сообщение я подтверждаю, что ознакомлен и согласен с политикой конфиденциальности данного сайта.




800 человек в сутки на сайте
Демонстрация движения предмета, брошенного под углом к горизонту
Программа шутка "Не меняй!"