Рекурсия в Java

Рекурсия

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

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

Используйте рекурсию, чтобы добавить все числа до 10:

public class MyClass {
  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. При запуске программа выполняет следующие шаги:

10 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0

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

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

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

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

Используйте рекурсию, чтобы сложить все числа от 5 до 10.

public class MyClass {
  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;
    }
  }
}