Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-03-10

1 Рекурсия- известное и распространённое явление, которое встречается как в математике, так и в повседневной жизни. Рекурсивным называют объект, который частично состоит или определяется с помощью самого же себя. Например, если вы включите веб-камеру и наведёте её на экран компьютера, она будет записывать экран компьютера, выводя изображение на тот же самый экран компьютера. То есть мы увидим что-то наподобие замкнутого цикла.

2 Пример бесконечной рекурсии в литературе - докучные сказки типа "У попа была собака", где конец подменяется началом и всё продолжается снова и снова. А вот ещё примеры рекурсии:

3 <h2>О рекурсии в программировании</h2>

4 Что касается программирования, то здесь рекурсия связана с функциями, то есть понятие рекурсивной функции известно любому программисту. В данном случае рекурсия - это определение части метода или функции через саму себя. Можно сказать, что это функция, вызывающая саму себя в своём теле (непосредственно) либо через другую функцию (косвенно).

5 Впрочем, о рекурсии сказано много, поэтому вы без труда найдёте нужную информацию на просторах сети. Мы же поговорим о рекурсии с точки зрения решения задач. Именно задачи и их решение являются наиболее эффективным средством для понимания рекурсии, как таковой.

6 <h2>Как решают задачи на на рекурсию?</h2>

7 Во-первых, нужно уяснить, что рекурсия - это, по сути, перебор. Да и вообще, то, что можно решить итеративно, можно решить и рекурсивно, используя рекурсивную функцию. То есть практически любой алгоритм, который реализован в рекурсивной форме, можно переписать в итерационной форме и наоборот. Вопрос лишь в том, зачем это нужно и насколько эффективно.

8 Идём дальше. Так же, как и у цикла (перебора), рекурсия должна иметьусловие остановки, называемоебазовым случаем. Иначе и цикл, и рекурсия будут работать бесконечно. Условие остановки определяетшаг рекурсии. Рекурсивная функция вызывается, пока не произойдёт остановка рекурсии (не сработает базовое условие и не произойдёт возврат к последнему вызову функции). Именно поэтому решение задачи на рекурсию сводится к решению базового случая.

9 Если мы решаем сложную задачу (небазового случая), мы выполняем несколько рекурсивных вызовов либо шагов, т. к. наша цель - упростить задачу. И делать это до тех пор, пока не придём к базовому решению.

10 Ещё раз. Рекурсивная функция включает в себя: -базовый случай, он же условие остановки; -шаг рекурсии, он же условие продолжения.

11 Давайте рассмотрим это, изучив пример нахождения факториала:

12 public class Solution { public static int recursion(int n) { // условие выхода // Базовый случай // когда остановиться/повторять рекурсию ? if (n == 1) { return 1; } // Шаг рекурсии/рекурсивное условие return recursion(n - 1) * n; } public static void main(String[] args) { System.out.println(recursion(5)); // вызов рекурсивной функции } }Здесь базовое условие - когда n=1. Раз мы знаем что 1!=1, для вычисления 1! нам ничего не надо. И чтобы определить 2! Можно использовать 1!, то есть 2!=1!2. А чтобы вычислить 3! потребуется 2!3… Для вычисления n! нужно (n-1)!*n. Вот это и есть шаг рекурсии. Другими словами, чтоб нам получить значение факториала от числа n, нам достаточно умножить на n значение факториала от предыдущего числа.

13 Давайте рассмотрим ещё парочку задач о рекурсии разного уровня сложности. Не спешите сразу смотреть решение, а попробуйте выполнить расчёты самостоятельно.

14 <h2>Задача о рекурсии № 1: От 1 до n</h2>

15 У вас есть натуральное число n. Необходимо вывести все числа от 1 до n.

16 Решение:

17 public class Solution { public static String recursion(int n) { // Базовый случай if (n == 1) { return "1"; } // Шаг рекурсии/рекурсивное условие return recursion(n - 1) + " " + n; } public static void main(String[] args) { System.out.println(recursion(10)); // вызов рекурсивной функции } }<h2>Задача о рекурсии № 2. От А до В</h2>

18 Имеются 2 целых числа A и В (каждое из них в отдельной строке). Необходимо вывести все числа от A до B включительно. Если A < B, числа выводятся по возрастанию, в обратном случае - по убыванию.

19 Решение:

20 public class Solution { public static String recursion(int a, int b) { // основное условие задачи if (a > b) { // Базовый случай if (a == b) { return Integer.toString(a); } // Шаг рекурсии/рекурсивное условие return a + " " + recursion(a - 1, b); } else { // Базовый случай if (a == b) { return Integer.toString(a); } // Шаг рекурсии/рекурсивное условие return a + " " + recursion(a + 1, b); } } public static void main(String[] args) { System.out.println(recursion(20, 15)); // вызов рекурсивной функции System.out.println(recursion(10, 15)); // вызов рекурсивной функции } }<h2>Задача о рекурсии № 3. Функция Аккермана</h2>

21 Функция Аккермана A(m,n), играет важную роль в теории вычислимости. Она определена следующим образом:

22 Условие задачи: есть 2 целых неотрицательных числа m и n, каждое из них находится в отдельной строке. Необходимо вывести A(m,n).

23 Решение:

24 public class Solution { public static int recursion(int m, int n) { // Базовый случай if (m == 0) { return n + 1; } // Шаг рекурсии/рекурсивное условие else if (n == 0 && m > 0) { return recursion(m - 1, 1); } // Шаг рекурсии/рекурсивное условие else { return recursion(m - 1, recursion(m, n - 1)); } } public static void main(String[] args) { System.out.println(recursion(3, 2)); // вызов рекурсивной функции } }