Algorytmy dla początkujących #1: rekurencja

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, że 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.*

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ć.

 

Silnia w wersji rekurencyjnej.

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.

To tyle, jeśli chodzi o podstawy rekurencji. 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.

2 myśli na temat “Algorytmy dla początkujących #1: rekurencja

  1. Co jaki czas masz w planie wrzucać taki poradnik? Bo fajnie jakby było wrzucane systematycznie i był plan np na następne 5 tematów 🙂 Bo mam w planie uczyć się razem tym co będziesz wrzucał.

Dodaj komentarz