Рекурсия в Java

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

Кратко

• Рекурсивный метод это метод, который вызывает сам себя. Внутри у него всегда две части: базис (условие выхода) и шаг (вызов себя с измененными параметрами).
• Без достижимого базиса рекурсия не остановится, и программа упадет с переполнением стека вызовов.
• Классический пример это факториал: factorial(n) = n * factorial(n - 1), а базис это n == 0 или n == 1.
• Почти любую задачу с циклом можно переписать рекурсией и наоборот. Рекурсия выигрывает в читаемости, цикл в памяти и скорости.
• Каждый вызов занимает кадр в стеке потока, поэтому глубина рекурсии ограничена размером этого стека, а он зависит от платформы.
• Сложная (взаимная) рекурсия это когда метод A вызывает метод B, а тот снова вызывает A. Базис такой паре нужен точно так же, просто искать его сложнее.

Чтобы понять, что такое рекурсия, нужно понять, что такое рекурсия. На самом деле, в понимании таких функций нет ничего сложного, нужно только один раз хорошо в этом разобраться. И попрактиковаться, если речь идет о программировании. Рекурсия встречается не только в программировании, но и в реальной жизни. Возьми в руки зеркало и встань напротив другого зеркала. Отражение отражения отразится в отражении и так далее. Ты увидишь бесконечное количество отражений, уходящих в бесконечность. Больше о “реальной” рекурсии ты можешь найти в статье “Дню Сурка посвящается…”

Что такое рекурсия в Java

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

public void recursionFunc() {
    System.out.println("Привет, JavaRush!");
    recursionFunc();
}

Чем же он вреден? Предлагаю проверить самостоятельно! Если решишься на эту авантюру (а ты, скорее всего, решишься, тыжпрограммист!), напиши в комментарии, какую ошибку выдаст JVM =) И этот пример, и множество других, демонстрируют, что к применению рекурсии в Java нужно подходить осторожно. Нужно понимать, где, когда и почему оправдан такой подход к решению задачи, и следить за тем, чтобы твоя функция не превратила выполнение программы в «День Сурка».

Базис и шаг рекурсии

Есть еще два важных для понимания рекурсии определения:

• Базис рекурсии это условие выхода из блока рекурсивных вызовов, базисное решение задачи при условиях, когда нет необходимости вызывать рекурсию.
• Шаг рекурсии это вызов функцией самой себя при изменении параметров.

Факториал: классический пример рекурсии

Классический пример применения рекурсивной функции это вычисление факториала от числа. Если вдруг забыл, напомню: факториал положительного целого числа N (обозначается как N!) это произведение чисел от 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. Кстати, факториал нуля по определению равен 1. Так что факториал можно найти для любого целого положительного числа и нуля (на языке математики, для множества неотрицательных целых чисел или же для множества натуральных чисел и нуля).

Факториал через цикл

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

private long fact(int n) {
    long result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Добавим проверку того, что число положительное и целое, и отдельно проверку для нуля.

private long fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
        return -1;
    }
    long result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Факториал через рекурсию

Теперь приведу код метода для рекурсивного решения этой задачи:

private long factorial(int n) {
    long result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}

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

System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));

Получим ожидаемые значения:

1
1
2
6
24
120
720

Добавим красивый вывод и вычислим факториал для числа побольше:

private long factorial(int n) {
    long result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");

Получим: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! Обрати внимание на тип результата: он long, а не int. Факториалы растут очень быстро, и в int помещается только до 12! включительно, это 479 001 600. Начиная с 13! значение молча переполняется, никакой ошибки не будет, метод просто вернет мусор: для 15! получилось бы 2 004 310 016 вместо правильного ответа. long выручает до 20!, а для чисел побольше нужен уже BigInteger. В данном случае применение рекурсивной функции оправдано и безопасно. Мы четко обозначили условие выхода из рекурсивного блока, и мы уверены в том, что он достижим: мы вводим целое неотрицательное число, в случае, если число равно нулю или единице - возвращаем результат, если же число больше, умножаем результат на функцию от числа n-1.

Как разворачивается рекурсивный вызов

На примере факториала от трех:

factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)
		
		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1

Что будет, если передать отрицательное число

По поводу осторожности применения: в чем уязвимость этой функции? Если дать методу в качестве параметра отрицательное число, то проверка

    if (n == 1 || n == 0) {
        return result;
    }

не имеет смысла и мы уйдем в бесконечный цикл вызовов методом самого себя. Стоит добавить проверку на неотрицательность:

if (n < 0) {
	System.out.println("Зачем тебе факториал отрицательного числа?");
	return -1;
}

И все будет хорошо.

Рекурсия или цикл: что выбрать

В чем преимущество одного метода перед другим? Кажется, что большой разницы нет, но на самом деле множество рекурсивных вызовов негативно скажется на производительности и потребляемой памяти: стек вызовов это практически неконтролируемый ресурс и при разных условиях вызова одной и той же рекурсивной функции, мы можем получить или не получить проблемы, связанные с этим ресурсом. Практически все задачи, решаемые с помощью итераций (циклов for, while, for-each), можно решить и рекурсивно. Преимущество рекурсии в читаемости и простоте написания, о недостатках мы говорили выше: возможность «выстрелить себе в ногу» неиллюзорна. Если совсем коротко, выбор выглядит так:

Сложная рекурсия: когда методы вызывают друг друга

Еще более осторожным надо быть при использовании так называемой «сложной рекурсии»: Функция A() вызовет функцию B(), вызывающую функцию A(). Для решения таких задач необходимо полное понимание того, как работает рекурсия. Пример такой задачи: вычисление значения x^n/(n!). Факториал, как мы обсуждали выше, определен на множестве неотрицательных целых чисел. Напоследок приведу код решения. Сложная рекурсия будет состоять из двух методов:

private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Для входа в рекурсию используется метод calculate, вызывающий метод power, в свою очередь вызывающий метод calculate. Базис рекурсии мы обозначили в методе power:

if (n == 1) return x;

Там же определен и шаг рекурсии:

return x * calculate(x, n - 1);

Осталось добавить проверку валидности входных данных:

• Любое число, кроме нуля, в нулевой степени равно 1. Если n = 0, то n! = 1. Нужно вернуть 1.
• Нуль в любой степени равен нулю.
• Неопределенность типа 0^0 рассматривать не будем и примем такие входные данные за невалидные.

Со всеми проверками методы будут выглядеть так:

private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

    if (n == 0) {
        return 1;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Ну, и при вызове функции нужно не забыть поймать ошибку:

try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}

Про то, откуда берется ошибка переполнения стека, коротко сказано в документации StackOverflowError, а про то, от чего зависит доступная глубина, в описании конструктора Thread с параметром stackSize.

Вопросы и ответы

Из чего состоит любой рекурсивный метод?

Из двух частей. Базис это условие, при котором метод возвращает готовый ответ и себя больше не вызывает. Шаг это вызов самого себя с измененными параметрами, который постепенно подводит задачу к базису. Если убрать базис, рекурсия не остановится. Если шаг не приближает к базису, тоже не остановится, хотя базис формально и есть.

Почему рекурсивный метод падает с StackOverflowError?

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

Какая максимальная глубина рекурсии в Java?

Фиксированного числа нет. Глубина упирается в размер стека потока, а он зависит от платформы и настроек виртуальной машины. Документация конструктора Thread с параметром stackSize прямо говорит, что связь между размером стека и максимальной глубиной рекурсии платформозависима, а на некоторых платформах этот параметр вообще ни на что не влияет. На практике речь идет о тысячах вызовов, а увеличить запас можно ключом -Xss.

Что быстрее и экономнее: рекурсия или цикл?

Цикл. Вызов метода стоит дороже одной итерации, а каждый незавершенный вызов еще и занимает память в стеке. Цикл же обходится одной переменной-накопителем. Рекурсию выбирают не ради скорости, а ради читаемости: там, где задача сама по себе вложенная, рекурсивный код короче и понятнее.

Как переписать рекурсию циклом?

Если рекурсивный вызов один и он последний в методе, замена почти механическая: заводится переменная-накопитель, а рекурсия превращается в обычный for или while. Именно так в статье написан нерекурсивный вариант факториала. Если вызовов несколько, как при обходе дерева, простого цикла мало: понадобится собственная структура-стек или очередь, куда складываются еще не обработанные ветки.

Что такое взаимная (сложная) рекурсия?

Это когда метод A вызывает метод B, а метод B снова вызывает A. Прямого самовызова нет ни у одного из них, но цикл вызовов все равно замкнут. Правила те же: где-то в этой паре должен быть достижимый базис, иначе стек переполнится. Отлаживать такую рекурсию сложнее, потому что условие выхода и шаг живут в разных методах.

Читайте также

• Дню Сурка посвящается: рекурсия в реальной жизни
• Методы, их параметры, взаимодействие и перегрузка
• Циклы Java
• Быстрая сортировка QuickSort в Java
• Примитивные типы Java