Rekurencja, czyli jeden z kanonów programowania. I nie tylko! Witam Cię w szóstym już wpisie na moim blogu i pozwól, że dziś — w tym krótkim wpisie zagłębię się w temat jakże ciekawy. Jest nim rekurencja. Wiele osób zarówno od strony matematycznej, jak i programistycznej boi się tego tematu i zupełnie nie rozumie, z czym to się je.
Ja dziś postaram się odpowiedzieć na następujące pytania:
- Czym jest rekurencja?
- Gdzie można jej używać?
- Jak ją zaimplementować?
- Czym jest i jak ma się do rekurencji ciąg Fibonacciego?
- Jakie możemy napotkać problemy związane z rekurencją?
Nie ma w zasadzie w tym strachu nic dziwnego, rekurencja ma to do siebie, że jest totalnie niezrozumiała dla człowieka. Jej przewagą natomiast jest to, że jest bardzo intuicyjna i przyjazna dla komputera.
Zatrzymaj się!
Książki to obowiązkowa pozycja dla każdego zainteresowanego programowaniem!
Jest to zdecydowanie jedno z najlepszych źródeł do nauki programowania! Zyskasz przewagę w branży IT i osiągniesz dużo jako deweloper.
Rekurencja — wprowadzenie
Temat rekurencji, zwanej też rekursją jest jednym z tych zagadnień, które zwłaszcza w początkowej fazie nauki programowania sprawia problemy. Sama zasada rekurencji wydaje się prosta. Mamy funkcję, która w ciele zawiera wywołanie samej siebie. Powoduje to zapętlenie, często zobrazować można to jako węża, który zjada swój ogon. Celem takiego działania jest rozwiązanie pewnego problemu, który w sposób iteracyjny byłby skomplikowany lub nieefektywny pod kątem wydajności i szybkości działania.
Żeby zrozumieć rekurencję, trzeba zrozumieć rekurencję.
Przy rekurencji od razu zapala się lampka — przecież wywołanie funkcji samej przez siebie powoduje nieskończoną pętlę. Oczywiście tak może się stać w momencie, gdy nie obsłużymy poprawnie miejsca wyjścia z funkcji. W akapicie poniżej zgłębię dwa przypadki poprawnej implementacji rekurencji.
Zastosowania
Jak już wyżej wspomniałem, rekurencyjnie można rozwiązać wiele problemów, które za pomocą na przykład pętli for są nie do wykonania lub ich wykonanie nie będzie możliwe do realizacji w skończonym czasie. Jednym ze sztandarowych przykładów jest wyszukiwarka tekstu, której implementacja może zostać wykonana bardzo wydajnie za pomocą wywołań rekurencyjnych, gdzie funkcja przyjmuje szukany fragment teksu na wejściu i przesuwa się o określoną ilość znaków, porównując szukany fragment do wyciętego fragmentu całości. Pochodną tego typu wyszukiwania są wyszukiwania w głąb oraz binarne, ale na temat szukania w tekście i zbiorach danych postaram się w niedalekiej przyszłości napisać osobny artykuł.
Listy wiązane
Kolejnym przykładem zastosowania rekurencji to tak zwane listy wiązane. Często zdarza się, że mamy jakieś zbiory danych, które referują same do siebie. Wtedy powstaje pewnego rodzaju struktura drzewiasta, gdzie od root schodzimy niżej aż do ostatnich powiązanych elementów. Wyobraź sobie tabelę z kilkoma kolumnami, gdzie mamy dwie bardzo ważne elementy, główne ID oraz ReferID, gdzie przechowujemy powiązanie z innym elementem tej samej tabeli. Na podstawie takiej tabeli możemy zbudować listy produktów z podziałem na kategorie, które to kategorie mają podkategorie i tak dalej w dół. Podobnie można zastosować rekurencje i listy wiązanej jako elementy menu, które składają się na poziomy.
Rekurencja w programowaniu
Czas najwyższy zmierzyć się z tematem i napisać coś rekurencyjnego. Mam dwie propozycje, pierwszą trywialną — prezentacja rekurencji oraz iteracji w dwóch różnych metodach. Metody nie będą robiły nic więcej poza odliczeniem od 10000 do 0. Następnie prawdziwy kanon, jeżeli chodzi o kod rekurencyjny, a mianowicie ciąg Fibonacciego. O tym, czym ten ciąg jest, napiszę podczas omawiania drugiego przykładu.
Implementacja pierwsza
Na początku omówię kod pierwszy, który zawiera prosty program konsolowy, którego zadaniem jest odliczenie do zera. Na start dałem wartość 10000, ale może być to dowolna liczba (oczywiście z rozsądkiem, bo nasz sprzęt się zapracuje przy zbyt dużych liczbach).
W metodzie Main w liniach 9 oraz 10 uruchamiane są metody. Odpowiednio Iteration, a następnie Recursion. Jedna i druga metoda jest typu void i przyjmuje na start liczbę typu int. W przypadku metody Iteration nie dzieje się nic ciekawego poza zwykłą pętlą for z warunkiem powodującym to, że pętla z każdym obrotem maleje o 1. W pętli mamy prosty warunek, który sprawdza, czy nasz iterator „i” osiągnął już wartość 1. Gdy to się stanie, wypisywana jest na konsolę informacja o zakończeniu działania.
Druga metoda jest równie prosta, ale dzieje się tam coś mało dla nas intuicyjnego i zarazem bardzo niebezpiecznego, o czym później. Jak widzimy, na wejście również dostajemy wartość liczbową, następuje warunek sprawdzający, czy to, co na wejściu jest równe 1. Jeżeli tak to nasza metoda kończy działanie, wypisuje na ekran komunikat o zakończeniu działania. Jeżeli wartość jest inna, to funkcja przechodzi niżej i uruchamia siebie samą z numerem mniejszym o jeden. Wpada w elegancką pętlę, ale pętla tego typu może spowodować „zjedzenie” całej naszej dostępnej pamięci. Możesz skopiować kod i zmieniając parametry wejściowe sprawdzić, kiedy u Ciebie się to wydarzy!
Może mało elegancki kod, ale pokazuję ideę działania.
using System;
namespace Recursion
{
class Program
{
static void Main(string[] args)
{
Iteration(10000);
Recursion(10000);
Console.ReadKey();
}
public static void Iteration(int number)
{
for (int i = number; 0 < i; i--)
{
if(i == 1)
{
Console.WriteLine("Zakończyłem iteracyjne działanie programu!");
return;
}
}
}
public static void Recursion(int number)
{
if (number == 1)
{
Console.WriteLine("Zakończyłem rekurencyjne działanie programu!");
return;
}
else
Recursion(number - 1);
}
}
}
Implementacja druga
Czas na ciekawsze zastosowanie rekurencji w programowaniu. Poniżej przedstawiam kod do obliczenia wybranego elementu ciągu Fibonacciego. Ciąg ten jest specyficznym ciągiem, bo każda liczba ciągu jest sumą dwóch poprzednich. Poniżej tabela z 10 pierwszymi liczbami ciągu.
Tak naprawdę elementów jest 11, ponieważ liczenie zaczynamy od elementu 0. Zobaczmy na 8 element, który możemy obliczyć, dodając element 7 oraz 6 (13 + 8 = 21). Aby to zrobić, musimy obliczyć sekwencyjnie wszystkie pozostałe elementy aż do elementu 2. Idealnie w programowaniu nadaje się do tego rekurencja. Zobacz poniżej.
W aplikacji konsolowej program prosi o podanie numeru elementu, którego wartość chcemy uzyskać. Następnie po wczytaniu z klawiatury liczby do zmiennej fibNumber następuje wywołanie funkcji Fib, która to funkcja na wejście przyjmuje numer elementu, który potrzebujemy obliczyć.
Fib jest podobną funkcją jak opisywana powyżej w przykładzie. Na początku następuje sprawdzenie, czy numer podany na wejście jest mniejszy od 3, wtedy zgodnie z tabelą powyżej dla 2 oraz 1 elementu w tablicy wartością jest zwracana jedynka. Gdy natomiast wartość podana na wejście jest większa od dwójki, wtedy następuje dwukrotne uruchomienie samej siebie z liczbami o jeden i dwa mniejszymi. Sekwencyjnie program zagłębia się coraz niżej, aż dojdzie do pierwszego i drugiego elementu ciągu. Następuje wtedy sumowanie wszystkich elementów w górę. Powoduje to utworzenie pewnego rodzaju drzewa, który od korzenia schodzi i sumuje wszystkie liczby aż do samego końca drzewa.
Na koniec dodam jeszcze, że w przypadku ciągu Fibonacciego rekurencję jest łatwo pokazać, ale nie warto jej stosować do tego typu zadań. Chodzi przede wszystkim o tragiczną wydajność dla większej ilości elementów ciągu.
using System;
namespace CiagFibonacciego
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Podaj, który numer ciągu chcesz obliczyć: ");
int fibNumber = int.Parse(Console.ReadLine());
Console.WriteLine("Numer " + fibNumber.ToString() + " równy jest " + Fib(fibNumber));
Console.ReadKey();
}
public static int Fib(int number)
{
if (number < 3)
return 1;
return Fib(number - 2) + Fib(number - 1);
}
}
}
Czy wiesz, że…
Wyżej zaimplementowałem kod obliczający n-tą wartość ciągu Fibonacciego. Sam ciąg ma niemal magiczne właściwości. Chodzi mianowicie o to, że dwie kolejne liczby ciągu po podzieleniu dają wartość w przybliżeniu równą 1,618. Na przykład podzielmy wartość elementu 13 przez wartość elementu 12:
233 / 144 = 1,618055555555556
Teraz element 19 i 18:
4181 / 2584 = 1,618034055727554
Nie byłoby nic w tym dziwnego, gdyby nie to, że liczba 1,618 jest obecna w wielu elementach naszego świata. Taką proporcję można spotkać w DNA czy w układzie roślin takich jak słonecznik (ułożenie pestek słonecznika), lilia, dzika róża czy stokrotka (ułożenie i budowa liści). Nazywana jest przez to boską cząstką lub złotym podziałem i oznacza grecką literą φ (czytaj „fi”).
Rekurencja — podsumowanie
Rekurencja jest jedną z podstaw programowania. Używa się jej świadomie mniej lub bardziej w wielu miejscach. Przed zbudowaniem algorytmu rekurencyjnego musimy jasno określić zasady zakończenia, tak by nie stworzyć niekończącej się pętli.
Chciałem, by ten artykuł był jak najkrótszy i bazował na kilku małych przykładach. Celowo nie poruszałem tematów matematycznych, ponieważ wzory są zazwyczaj czymś, co odstrasza. Sam artykuł ma być tylko wprowadzeniem dla początkujących oraz odświeżeniem wiedzy dla osób znających zagadnienie rekursji. Nie ukrywam, że w przyszłości rekurencję będę chciał przedstawić w sposób bardziej zaawansowany, jednak na ten moment nie czas na to.
Daj znać w komentarzu, co myślisz o takich krótkich formach przekazywania wiedzy!
W następnym wpisie poruszę temat złożoności obliczeniowej.
Źródła
https://plato.stanford.edu/entries/self-reference/ https://pl.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/recursion http://www.cs.put.poznan.pl/ksiek/fp/recurrency.html https://www.issi.uz.zgora.pl/pl/didactic/cichy/aisd_07.pdf http://www.ujk.edu.pl/~stefanek/zfj/AiSD_Wyklad4_dzienne.pdf http://www.algorytm.edu.pl/rekurencja.html https://pracownik.kul.pl/files/12883/public/wdi/Rekurencja.pdf https://mattomatti.com/pl/a0002 https://strefainzyniera.pl/artykul/1062/rekurencja http://developforperformance.com/MatchingWildcards_AnImprovedAlgorithmForBigData.html https://eduinf.waw.pl/inf/utils/010_2010/0215.php https://www.refactoring.com/catalog/replaceRecursionWithIteration.html https://www.techiedelight.com/depth-first-search/ http://home.agh.edu.pl/~pkleczek/dokuwiki/doku.php?id=dydaktyka:aisd:2016:recursion https://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and https://mathspace.pl/matematyka/rekurencja-posrednia-czyli-zabawy-z-rekurencja-czesc-4/ https://javastart.pl/baza-wiedzy/java-zaawansowane/rekurencja-rekursja http://users.uj.edu.pl/~ufkapano/algorytmy/lekcja04/rekurencja.html http://lambda-the-ultimate.org/node/1014 http://blog.moertel.com/posts/2013-05-14-recursive-to-iterative-2.html http://www.ccs.neu.edu/home/shivers/papers/loop.pdf http://mathspace.pl/tag/rekurencja/
Newsletter
Nie przegap i dołącz już dziś do 842 osób będących w tym Newsletter! Otrzymuj co niedzielę o godzinie 20 listę kilku ciekawych tematów, które miałem okazję obserwować w mijającym tygodniu.
Tematy będą głównie techniczne, ale czasami pojawi się coś, co może wprowadzi Cię w stan zadumy i zmusi do dyskusji w szerszym gronie. Zero spamu!
5 komentarzy
Wczoraj akurat przypominałem sobie kwestie związane zarówno z rekurencją jak i złożonością a dziś przy kawie powtórka.
Dla mnie tego typu krótkie materiał to fajna sprawa pod warunkiem, że nie zrezygnujesz z dłuższych.
Pozdrawiam
Cześć Arku, dzięki za komentarz!
Staram się przeplatać dłuższe wpisy – takie, chociażby jak temat Blockchain czy Matura z informatyki z wpisami mniej rozbudowanymi, jak właśnie rekurencja. Planuje nawet jeszcze częściej niż raz w tygodniu wydawać posty, więc będzie to bardziej tendencja wzrostowa.
Pozdrawiam, Mateusz.
Ciekawy przykład rekurencji był w książce Davida Harel-a „Rzecz O Istocie Informatyki – Algorytmika”, na przykładzie wież Hanoi. Też można rozwiązanie tego problemu przedstawić na podstawie rekurencji, o czym wcześniej nie wiedziałem.
Ja mam problem ze zrozumieniem jak rekurencja powraca ze swoich wywołań, bo jak zaczyna się wywoływać to jakoś jeszcze ogarniam.
Fajnie się czytało ten artykuł. Nie wiedziałem że 1,618 to boska cząstka. Taka dawka informacji jest ok.
Pozdrawiam.
Ok ale druga funkcja nie wywołuje samej siebie tylko przechodzi do dalszego wykonywania pętli for. Na tam nie widzę nazwy funkcji wewnątrz funkcji dzięki
Bardzo dobra uwaga, kolejność została poprawiona!
Pozdrawiam, Mateusz.