Рекурсия в Java

В программировании есть такое понятие, как рекурсия - это когда метод вызывает сам себя. Давайте посмотрим на примере. Выведем с помощью рекурсии числа от 1 до 10.

Номер шага передадим параметром. Глобальной переменной здесь нет: каждый следующий вызов получает свое число:

public class Main {
	static void func(int i) {
		System.out.println(i);

		if (i < 10) {
			func(i + 1); // здесь метод вызывает сам себя
		}
	}

	public static void main(String[] args) {
		func(1);
	}
}

Давайте обсудим, как работает этот код.

Метод func выводит параметр i. Если i меньше 10, метод вызывается снова и передает число на единицу больше. Так вызовы идут, пока i не достигнет 10.

Учтите, что в нашем случае нельзя убрать условие. Если это сделать, получится бесконечный вызов методов.

Тот же прием считает факториал. Метод возвращает 1 для единицы и произведение числа на факториал предыдущего:

public class Main {
	static int fact(int num) {
		if (num == 1) {
			return 1;
		}

		return num * fact(num - 1);
	}

	public static void main(String[] args) {
		System.out.println(fact(5)); // выведет 120
	}
}

Давайте с помощью рекурсии последовательно выведем элементы массива. Индекс тоже передается параметром. Пока индекс меньше длины, печатаем элемент и вызываем метод для следующего индекса:

public class Main {
	static void show(int[] arr, int i) {
		if (i < arr.length) {
			System.out.println(arr[i]);
			show(arr, i + 1);
		}
	}

	public static void main(String[] args) {
		int[] arr = {1, 2, 3};
		show(arr, 0);
	}
}

Проще всего перебрать элементы массива циклом. Приведенный пример показывает работу рекурсии на простом случае. У рекурсии обязательно есть условие остановки, иначе вызовы не закончатся.

Создайте рекурсивный метод, который считает сумму чисел от 1 до переданного числа.

Дан массив:

int[] arr = {1, 2, 3, 4, 5};

С помощью рекурсии выведите элементы этого массива на экран.