Rekurencja Java

Rekurencja Java

Rekurencja to technika wykonywania samego wywołania funkcji. Ta technika umożliwia rozbicie skomplikowanych problemów na proste, które są łatwiejsze do rozwiązania.

Rekurencja może być nieco trudna do zrozumienia. Najlepszym sposobem, aby dowiedzieć się, jak to działa, jest eksperymentowanie z nim.

Przykład rekurencji

Dodanie dwóch liczb razem jest łatwe, ale dodanie zakresu liczb jest bardziej skomplikowane. W poniższym przykładzie rekursja służy do dodawania zakresu liczb razem, dzieląc go na proste zadanie dodawania dwóch liczb:

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

Przykład wyjaśniony

Gdy sum()funkcja jest wywoływana, dodaje parametr kdo sumy wszystkich liczb mniejszych niż ki zwraca wynik. Gdy k staje się 0, funkcja po prostu zwraca 0. Podczas działania program wykonuje następujące kroki:

Ponieważ funkcja nie wywołuje samej siebie, gdy kma wartość 0, program zatrzymuje się w tym miejscu i zwraca wynik.

Stan zatrzymania

Tak jak pętle mogą napotkać problem nieskończonej pętli, tak funkcje rekurencyjne mogą napotkać problem nieskończonej rekurencji. Nieskończona rekurencja ma miejsce, gdy funkcja nigdy nie przestaje się wywoływać. Każda funkcja rekurencyjna powinna mieć warunek zatrzymania, czyli warunek, w którym funkcja przestaje się wywoływać. W poprzednim przykładzie warunek zatrzymania występuje, gdy parametr kwynosi 0.

Pomocne jest zapoznanie się z różnymi przykładami, aby lepiej zrozumieć tę koncepcję. W tym przykładzie funkcja dodaje zakres liczb między początkiem a końcem. Warunkiem zatrzymania dla tej funkcji rekurencyjnej jest sytuacja, gdy end nie jest większe niż 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;
    }
  }
}