Artikulo
Magsimula
Simulan ang pag-aaral
JavaRush /Java Blog /Random-TL /Рекурсия в Java
Алексей Дмитревский
Antas
Москва

Рекурсия в Java

Nai-publish sa grupo
Whatбы понять, что такое рекурсия, нужно понять, что такое рекурсия. На самом деле, в понимании таких функций нет ничего сложного, нужно только один раз хорошо в этом разобраться. И попрактиковаться, если речь идёт о программировании. Рекурсия в Java - 1Рекурсия встречается не только в программировании, но и в реальной жизни. Возьми в руки зеркало и встань напротив другого зеркала. Отражение отражения отразится в отражении и так далее. Ты увидишь бесконечное количество отражений, уходящих в бесконечность. Больше о “реальной” рекурсии ты можешь найти в статье “Дню Сурка посвящается…” Возвратимся из реального мира к будням программиста. Простое определение: рекурсивные функции в java – это функции, которые вызывают сами себя. Приведу очень простой и очень вредный пример: 

public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}
Чем же он вреден? Предлагаю проверить самостоятельно! Если решишься на эту авантюру (а ты, скорее всего, решишься, тыжпрограммист!), напиши в комментарии, Howую ошибку выдаст JVM =) И этот пример, и множество других, демонстрируют, что к применению рекурсии в Java нужно подходить осторожно. Нужно понимать, где, когда и почему оправдан такой подход к решению задачи, и следить за тем, чтобы твоя функция не превратила выполнение программы в «День Сурка». Есть еще два важных для понимания рекурсии определения:
  • Базис рекурсии – condition выхода из блока рекурсивных вызовов – базисное решение задачи, при условиях, когда нет необходимости вызывать рекурсию.
  • Шаг рекурсии – вызов функцией самой себя при изменении параметров.
Java-университет
Классический пример применения рекурсивной функции – вычисление факториала от числа. Если вдруг забыл, напомню: факториал положительного целого числа N (обозначается How N!) — это произведение чисел от 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. Кстати, факториал нуля по определению equals 1. Так что факториал можно найти для любого целого положительного числа и нуля (на языке математики — для множества неотрицательных целых чисел or же для множества натуральных чисел и нуля). Думаю, ты понимаешь, что запрограммировать факториал можно с помощью циклов. Собственно, вот нерекурсивный метод решения этой задачи: 

private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}
Добавим проверку того, что число положительное и целое, и отдельно проверку для нуля. 

private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}
Теперь приведу code метода для рекурсивного решения этой задачи: 

private int factorial(int n) {
    int 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 int factorial(int n) {
    int 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! В данном случае применение рекурсивной функции оправдано и безопасно. Мы четко обозначor condition выхода из рекурсивного блока, и мы уверены в том, что он достижим: мы вводим целое неотрицательное число, в случае, если число равно нулю or единице - возвращаем результат, если же число больше — умножаем результат на функцию от числа 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 null;
}
И все будет хорошо. В чем преимущество одного метода перед другим? Кажется, что большой разницы нет, но на самом деле множество рекурсивных вызовов негативно скажется на производительности и потребляемой памяти: стек вызовов – практически неконтролируемый ресурс и при разных условиях вызова одной и той же рекурсивной функции, мы можем получить or не получить проблемы, связанные с этим ресурсом. Практически все задачи, решаемые с помощью итераций (циклов типа for-each), можно решить и рекурсивно. Преимущество рекурсии в читаемости и простоте написания, о недостатках мы говорor выше: возможность «выстрелить себе в ногу» неиллюзорна. Еще более осторожным надо быть при использовании так называемой «сложной рекурсии»: Функция A() вызовет функцию B(), вызывающую функцию A().Для решения таких задач необходимо полное понимание того, How работает рекурсия. Пример такой задачи: вычисление значения x^n/(n!). Факториал, How мы обсуждали выше, определен на множестве неотрицательных целых чисел. Напоследок приведу code решения. Сложная рекурсия будет состоять из двух методов: 

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. Базис рекурсии мы обозначor в методе power: 

if (n == 1) return x;
Там же определен и шаг рекурсии: 

return x * calculate(x, n - 1);
Осталось добавить проверку валидности входных данных:
  • Любое число, кроме нуля, в нулевой степени равно 1. Если n = 0, то n! = 1. Нужно вернуть 1.
  • Нуль в любой степени equals нулю.
  • Неопределенность типа 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;
    }

    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());
}
Mga komento
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION