Java Recursion
Оновлено: 22.05.2023
Рекурсія Java
Рекурсія - це техніка здійснення виклику самої функції. Ця техніка дозволяє розбити складні проблеми на простіші, які легше вирішити.
Рекурсію може бути трохи складно зрозуміти. Найкращий спосіб зрозуміти, як вона працює - це поекспериментувати з нею.
Приклад рекурсії
Додавання двох чисел є простим, але додавання діапазону чисел є більш складним завданням. У наступному прикладі рекурсія використовується для додавання діапазону чисел, розбиваючи його на просту задачу додавання двох чисел:
Використовуйте рекурсію, щоб додати всі числа до 10.
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.
Для кращого розуміння концепції корисно переглянути різні приклади. У цьому прикладі функція додає діапазон чисел між початком і кінцем. Умовою зупинки цієї рекурсивної функції є те, що кінець не більший за початок:
Використовуйте рекурсію, щоб додати всі числа від 5 до 10.
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;
}
}
}