Java -рекурсия

Java-рекурсия

Рекурсия — это метод создания самого вызова функции. Этот метод позволяет разбить сложные проблемы на простые, которые легче решить.

Рекурсию может быть немного сложно понять. Лучший способ понять, как это работает, — это поэкспериментировать.

Пример рекурсии

Сложить два числа легко, но сложить диапазон чисел сложнее. В следующем примере рекурсия используется для сложения диапазона чисел, разбивая его на простую задачу сложения двух чисел:

public class Main {
  public static void main(String[] args) {
    int result = sum(10);
    System.out.println(result);
  }
  public static int sum(int k) {
    if (k > 0) {
      return k + sum(k - 1);
    } else {
      return 0;
    }
  }
}

Объяснение примера

Когда sum()функция вызывается, она добавляет параметр kк сумме всех чисел меньше чем kи возвращает результат. Когда k становится равным 0, функция просто возвращает 0. При запуске программа выполняет следующие шаги:

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

Состояние остановки

Точно так же, как циклы могут столкнуться с проблемой бесконечного зацикливания, рекурсивные функции могут столкнуться с проблемой бесконечной рекурсии. Бесконечная рекурсия — это когда функция никогда не перестает вызывать себя. Каждая рекурсивная функция должна иметь условие остановки, то есть условие, при котором функция прекращает вызывать себя. В предыдущем примере условие остановки возникает, когда параметр kстановится равным 0.

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

public class Main {
  public static void main(String[] args) {
    int result = sum(5, 10);
    System.out.println(result);
  }
  public static int sum(int start, int end) {
    if (end > start) {
      return end + sum(start, end - 1);
    } else {
      return end;
    }
  }
}