В этой статье описывается рекурсия и её виды с примерами на языке Java.
Начинаем с простого:
Рекурсия в Java - это процесс, когда метод вызывает сам себя. Это может быть полезно для решения задач, которые могут быть разбиты на более мелкие подзадачи.
Пример:
```
public class RecursionExample {
public static void main(String[] args) {
int result = factorial(5);
System.out.println(result);
}
public static int factorial(int n) {
if (n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
}
```
В этом примере мы используем рекурсивную функцию для вычисления факториала числа. Если n равно 1, функция возвращает 1. Если n больше 1, функция вызывает саму себя с аргументом n-1 и умножает результат на n.
Рекурсия может быть опасна, если не ограничить глубину рекурсии. Если глубина рекурсии слишком большая, это может привести к переполнению стека и ошибке StackOverflowError. Поэтому важно ограничивать глубину рекурсии и использовать рекурсию только там, где это действительно необходимо.
Однако на ряду с классической рекурсией можно выделить: множественную, анонимную и косвенную рекурсию.
1) множественная рекурсия.
Множественная рекурсия - это когда функция вызывает саму себя несколько раз в своем теле. Это может происходить как в базовом, так и в рекурсивном случае.
Например, рассмотрим следующую функцию, которая находит числа Фибоначчи:
```
public static int fibonacci(int n) {
if (n == 0) { // базовый случай
return 0; // возвращаем результат
} else if (n == 1) { // базовый случай
return 1; // возвращаем результат
} else { // рекурсивный случай
return fibonacci(n-1) + fibonacci(n-2); // вызываем функцию дважды и складываем результаты
}
}
```
В этой функции мы используем множественную рекурсию, так как при вычислении числа Фибоначчи для n мы вызываем функцию fibonacci дважды - для n-1 и n-2. Когда n достигает базового случая (0 или 1), рекурсия останавливается и функция возвращает соответствующее значение.
Пример вызова функции fibonacci:
```
int result = fibonacci(6);
System.out.println(result); // выводит 8
```
В этом примере мы вызываем функцию fibonacci для числа 6 и получаем результат, равный 8.
2) Анонимная рекурсия
Анонимная рекурсия - это когда функция вызывает саму себя без имени, используя лямбда-выражения или анонимные функции. Такой подход позволяет создавать рекурсивные функции без необходимости определения имени функции.
Например, рассмотрим следующее лямбда-выражение, которое находит факториал числа:
```
Function<Integer, Integer> factorial = n -> n == 0 ? 1 : n * factorial.apply(n-1);
```
В этом выражении мы используем анонимную рекурсию, так как функция вызывает саму себя без имени - вместо этого мы используем ключевое слово "factorial", которое ссылается на текущее лямбда-выражение. Когда n достигает базового случая (0), рекурсия останавливается и функция возвращает 1. В противном случае, функция продолжает вызывать саму себя, уменьшая значение аргумента на 1 и умножая результат на n.
Пример использования лямбда-выражения для вычисления факториала:
```
int result = factorial.apply(5);
System.out.println(result); // выводит 120
```
В этом примере мы используем лямбда-выражение "factorial" для вычисления факториала числа 5 и получаем результат, равный 120.
3) Косвенная рекурсия
Косвенная рекурсия - это когда две или более функции вызывают друг друга в цепочке. Это означает, что одна функция вызывает другую, которая затем может вызвать первую функцию или другую функцию в цепочке.
Например, рассмотрим следующий пример кода на языке Java:
```
public void functionA() {
System.out.println("Function A");
functionB();
}
public void functionB() {
System.out.println("Function B");
functionC();
}
public void functionC() {
System.out.println("Function C");
functionA();
}
```
В этом примере три функции - functionA, functionB и functionC - вызывают друг друга в циклическом порядке. Когда функция A вызывается, она выводит сообщение "Function A" и затем вызывает функцию B. Функция B выводит сообщение "Function B" и затем вызывает функцию C. Функция C выводит сообщение "Function C" и затем вызывает функцию A, завершая цикл.
Пример использования косвенной рекурсии:
```
functionA(); // вызываем первую функцию
```
При вызове функции A будет выполнена вся цепочка функций - A, B и C - в циклическом порядке, пока не будет достигнуто ограничение стека или не будет явно остановлено выполнение программы.
Вообще, как было сказано выше, рекурсия достаточно "дорогое" удовольствие, поэтому не стоит ее использовать повсеместно, да и я не припомню, чтобы на продажу где-то видел такую реализацию.