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;
}
}
}