Algorytmy #1: rekurencja/rekursja

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/

Stay in the Loop

Get the daily email from CryptoNews that makes reading the news actually enjoyable. Join our mailing list to stay in the loop to stay informed, for free.

Ostatnio dodane

- Advertisement - spot_img

Powiązane wpisy