rekurencja

Każdy, kto na matematyce dotarł do kombinatoryki, trafił na dziwną operację matematyczną, gdzie w nawiasie zapisywało się dwie liczby jedna pod drugą bez kreski ułamkowej. Jest to symbol Newtona, znany też jako współczynnik dwumianowy Newtona. Tutaj jednak nie chcę się skupiać na jego zastosowaniu w matematyce, tylko na tym, jak go obliczać. Przejdziemy krok po kroku przez różne podejścia, tym samym eksplorując na konkretnym przykładzie, w jaki sposób można optymalizować algorytmy. A na dokładkę opowiemy sobie o powiązanym z symbolem Newtona trójkącie Pascala, którego tworzenie jest popularnym ćwiczeniem dla początkujących programistów.

Świat matematyki bogaty jest w różne funkcje, definicje, odkrycia, które mogą wydawać się na pierwszy rzut oka całkowicie zbędne. I nie mam tutaj na myśli słynnych wzorów skróconego mnożenia, gdzie ludzie odmierzają sobie dni, kiedy ich nie użyli, tylko nieco bardziej zaawansowane koncepcje. W artykule chcę pochylić się nad jedną taką rzeczą — funkcją Ackermanna. Powstała, aby udowodnić, że można zrobić tak skomplikowaną i jednocześnie obliczalną funkcję. Zaś co może być ciekawe dla informatyków, w naszej niszy też znalazła pewne specyficzne zastosowanie. Poznajmy ją bliżej.

Patrząc na tekst, jesteśmy wzrokowo w stanie powiedzieć, czy dwa słowa są do siebie podobne: czy to znaczeniowo, czy pod kątem różnic w liczbie liter, czy jakkolwiek tylko przyjdzie nam do głowy. Tylko jak taką metrykę zdefiniować formalnie, a następnie w jaki sposób ją zapisać algorytmicznie? Idąc dalej tymi pytaniami — skąd wyszukiwarka internetowa wie, że jeśli wpisałeś(-aś) „dwistak”, to tak naprawdę miałeś(-aś) na myśli „świstak”? Poznajmy odpowiedzi na te pytania.

Potęgowanie to dość podstawowa, a jednocześnie przydatna operacja w matematyce. Jednak wykonując je według definicji, możemy nie dać rady zrobić tego szybko, szczególnie gdy podnosimy liczby do wysokich potęg. Mimo to jest na to sposób, jak można potęgi obliczać szybko, i to na tyle prostym algorytmem, że jest zwykle jednym z pierwszych, które poznajemy przy nauce programowania. Opowiedzmy sobie o nim, przetestujmy, a także sprawdźmy, czy naprawdę jest taki szybki.

Iteracja to według słownika PWN-u metoda polegająca na wielokrotnym stosowaniu tej samej procedury. Nawet nieskończenie, niczym Syzyf wtaczający głaz na szczyt góry (jak na okładce). W zasadzie na tym mógłbym zamknąć ten artykuł, bo właśnie odpowiedziałem na pytanie z tytułu. Jednak mimo to wejdźmy w temat głębiej: jakie mamy rodzaje iteracji, do czego się ostatecznie sprowadzają, co mają wspólnego z rekurencją, a także czym są iteratory.

Obliczanie największego wspólnego dzielnika dwóch liczb to prawdopodobnie jeden z pierwszych algorytmów, które poznajemy podczas swojej edukacji. Zarazem jest to też bardzo proste do zapamiętania. Omówmy sobie to klasyczne podejście, a także różne inne podejścia.

Wieże Hanoi to dla większości ludzi na świecie prosta, drewniana zabawka dla dzieci. Natomiast dla studentów informatyki to nie raz jedno z najgorszych wspomnień z pierwszych lat studiów i nauki programowania. Jak to możliwe? Co jest w nich takiego strasznego? Przekonajmy się na własną rękę.

Gry komputerowe nie raz skrywają w sobie wiele ciekawej algorytmiki, która albo jest zaskakująca, albo nietypowa, albo na tyle ciekawa, że warto się z nią zapoznać. Są też takie, które mają pod sobą wręcz bardzo „szkolne” algorytmy, ale nie oznacza to, że nie są ciekawe. Jedną z takich gier jest klasyczny saper, którego wielu zapewne kojarzy z gier wbudowanych w system Windows. Stoją za nim bardzo proste, lecz ciekawe w implementacji algorytmy. Napiszmy razem prosty klon tej gry.

Z mojego poprzedniego artykułu wiemy już czym jest rekurencja, rekursja ogonowa oraz jak je stosujemy. Jednak temat rekurencji jest dość rozległy i warto opowiedzieć sobie o tym, jak rekurencji możemy się najzwyczajniej w świecie… pozbyć. Proces ten nazywamy derekursywacją i możemy podejść do tego na różne sposoby, których część tutaj opiszę.

Rekurencja — co to jest?