Рекурсия — это приём, когда метод вызывает сам себя для решения задачи. Каждый рекурсивный метод должен содержать:
- Базовый случай — условие завершения, при котором метод возвращает результат без рекурсивного вызова
- Рекурсивный случай — вызов метода с изменёнными параметрами, приближающими к базовому случаю
Классические примеры: вычисление факториала n! = n * (n-1)!, числа Фибоначчи, возведение в степень. Без правильного базового случая возникнет бесконечная рекурсия и ошибка StackOverflowError.
Практические задания помогут понять механизм рекурсивных вызовов и научат писать рекурсивные методы.
- Модуль 1: Первая программа и структура
- Модуль 2: Переменные и типы данных
- Объявление и инициализация переменных.
- Примитивы: целые числа (int, long, byte, short).
- Примитивы: дробные числа (double, float).
- Примитивы: логический тип (boolean).
- Примитивы: символьный тип (char).
- String — основы работы со строками.
- Приведение типов (Casting): расширение и сужение.
- Область видимости переменных (Scope).
- Модуль 3: Операторы
- Модуль 4: Управляющие конструкции
- Модуль 5: Массивы и Строки (Advanced)
- Создание и заполнение массива.
- Доступ к элементам по индексу.
- Свойство length и перебор массива.
- Цикл for-each для массивов.
- Многомерные массивы.
- Методы String: length, charAt, isEmpty.
- Манипуляции: substring, concat, replace.
- Сравнение строк: equals vs ==.
- Разделение строк (split) и trim.
- StringBuilder (изменяемые строки).
- Модуль 6: Методы
- Модуль 7: Классы и Объекты (ООП Часть 1)
- Модуль 8: Капсуляция и Модификаторы
- Модуль 9: Наследование и Полиморфизм (ООП Часть 2)
- Модуль 10: Обработка исключений
- Модуль 11: Коллекции и Дженерики
- Модуль 12: Функциональный стиль (Java 8+)
- Модуль 13: Полезные стандарты
1. Результат факториала
Проанализируйте рекурсивный метод вычисления факториала и вызов этого метода с аргументом 5. Определите, какое число будет выведено на экран в результате выполнения программы. Выберите правильный вариант из предложенных.
public class FactorialExample {
public static int factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
public static void main(String[] args) {
int result = factorial(5);
System.out.println(result);
}
}2. Базовый случай
В этом задании вам предстоит дополнить рекурсивный метод вычисления факториала числа. В коде пропущены ключевые элементы базового случая рекурсии: условие завершения и возвращаемое значение. Ваша задача — вставить корректные выражения так, чтобы метод factorial(int n) корректно вычислял факториал для неотрицательных целых чисел. После заполнения пропусков программа должна выводить результат вычисления факториала числа 5.
public class Factorial {
public static int factorial(int n) {
if (input1S) {
return input2S;
}
return n * factorial(n - 1);
}
public static void main(String[] args) {
System.out.println(factorial(5));
}
}3. Собери метод факториала
Из предложенных строк соберите корректный рекурсивный метод `factorial` на Java, который вычисляет факториал числа n. Метод должен иметь сигнатуру `public static int factorial(int n)`, содержать базовый случай для n <= 1 и рекурсивный вызов с уменьшением аргумента. Одна из строк является лишней и не должна входить в итоговое решение. Обратите внимание на правильный порядок открывающих и закрывающих фигурных скобок.
public static int factorial(int n) { if (n <= 1) { return 1; } else { return n * factorial(n - 1); return n + factorial(n); }}4. Рекурсивная степень
Проанализируйте приведённый ниже код на Java. В нём определён рекурсивный метод power, который возводит число base в степень exp. В методе main этот метод вызывается с конкретными аргументами. Определите, какое число будет выведено на экран в результате выполнения программы. Введите это число в поле ответа.
public class Main {
public static int power(int base, int exp) {
if (exp == 0) {
return 1;
} else {
return base * power(base, exp - 1);
}
}
public static void main(String[] args) {
int result = power(2, 3);
System.out.println(result);
}
}5. Бесконечная рекурсия
В данном фрагменте кода представлен рекурсивный метод, который должен выводить числа от заданного значения до 1. Однако в коде допущена ошибка, приводящая к бесконечной рекурсии и, как следствие, к переполнению стека. Найдите строку с ошибкой и исправьте её, чтобы метод работал корректно.
public class Main { public static void main(String[] args) { printNumbers(5); } static void printNumbers(int n) { if (n == 0) { return; } System.out.println(n); printNumbers(n); }}6. Порядок вызовов
Перед вами перемешанные шаги, описывающие последовательность вызовов и возвратов при вычислении факториала числа 4 с помощью рекурсии. Расставьте эти шаги в правильном порядке, отражающем реальный процесс выполнения рекурсивной функции factorial(4). Правильная последовательность покажет, как рекурсия углубляется до базового случая, а затем возвращает значения обратно.
7. Части рекурсии
Перед вами фрагменты кода и описания, связанные с рекурсивными методами в Java. Разнесите их по двум категориям: «Базовый случай» и «Рекурсивный случай». Базовый случай — это условие, при котором рекурсия завершается, и метод возвращает конкретное значение без дальнейших вызовов. Рекурсивный случай — это часть метода, где происходит вызов самого метода с изменёнными параметрами. Обратите внимание, что в рекурсивном случае метод вызывает сам себя, а в базовом — нет. Каждый элемент должен оказаться ровно в одной категории.
if (n == 0) return 1;return n * factorial(n - 1);if (index >= array.length) return;return fibonacci(n - 1) + fibonacci(n - 2);return 0;process(array, index + 1);8. Числа Фибоначчи
Проанализируйте рекурсивный метод вычисления числа Фибоначчи и определите, какое значение будет выведено в консоль при вызове этого метода с аргументом 5. Обратите внимание на базовые случаи и рекурсивные вызовы.
public class FibonacciExample {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args) {
int result = fibonacci(5);
System.out.println(result);
}
}