Site icon Java blog

Algorytmy #1: rekurencja/rekursja

developeronthego
algorithms

Czym jest Algorytm?

Za pewne zastanawiasz się co to jest algorytm i po co są one tak istotne dla programistów. Najprostsza definicja brzmi: algorytm to sposób rozwiązywania problemu. Jest ona jak najbardziej poprawna, ale aby ją trochę rozszerzyć wyobraź sobie następującą sytuację.

Przed Tobą bardzo pracowity dzień i aby wykonać wszystkie czynności jakie sobie zaplanowałeś/aś, musisz ułożyć listę zadań. Lista ta powinna być ułożona logicznie (tzn. jeśli chcesz ugotować obiad, to najpierw powinieneś zrobić zakupy), być zgodna z Twoimi priorytetami (np. najpierw idziesz do banku, bo później będzie zamknięty), a także zgodna z czasem (nie będziesz przecież gotować obiadu rano albo w nocy). Taka lista to właśnie algorytm. Jedyna różnica, jest taka, że w przypadku programowania, do jego wyrażania nie używasz języka naturalnego tylko języka programowania.*

Rekurencja

Jednym z najczęściej stosowanych mechanizmów pisania algorytmów jest rekurencja. Aby ją poznać należy przypomnieć sobie podejście iteracyjne, które stosowałem w poprzednich lekcjach.

Przykład programu liczącego silnie, napisanego iteracyjnie.

private static int countFactorialIterative(int number) {
  int result = 1;
  
  for(int i = 1; i <= number; i++) {
    result = result* i;
  }

  return result;
}

Jak widzisz, metoda jest bardzo prosta w interpretacji. Po prostu korzystając z pętli for mnożymy każdy z indeksów przez siebie aż do momentu, kiedy pętla osiągnie wartość, z której miała zostać obliczona silnia.

W przypadku gdy będzie ona równa zero to metoda zwróci domyślnie liczbę jeden. Nie ma tu niczego co mogłoby Cię zaskoczyć.

Ten sam algorytm silni i użyta rekurencja.

private static int countFactorialRecursive(int number) {
  if (number == 0) {
    return 1;
  } else {
    return countFactorialRecursive(number - 1) * number;
  }
}

Tutaj dzieje się coś ciekawego, bowiem metoda wywołuje siebie samą ale z indeksem od największego do zera. Tak jak podpowiada Ci intuicja, w przeciwieństwie do pierwszego rozwiązania tutaj obliczenia wykonywane są, tak jakby od tyłu. Nie ma tu też żadnej pętli, a warunek stopu reguluje instrukcja warunkowa. To rozwiązanie jest trudniejsze do przeanalizowania, ale przyznasz, że za to jest dużo bardziej eleganckie.

Jak widzisz rekurencja nie jest niczym skomplikowanym. Jeśli chciałbyś/chciałabyś dowiedzieć się czegoś więcej, to polecam tutaj kilka linków:

*  To nie jest do końca prawda. Do projektowania algorytmów stosuje się różnego rodzaju zapisy umowne (podobnie jak w matematyce do zapisywania wzorów), jak np. : schemat blokowy czy lista kroków.

Polecam też kurs Java od podstaw: https://developeronthego.pl/category/programowanie/java-podstawy/

Exit mobile version