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:
- http://www.algorytm.edu.pl/algorytmy-maturalne/algorytm-eulkidesa.html
- http://www.algorytm.edu.pl/algorytmy-maturalne/ciag-fibonacciego.html
* 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/
