Rekurencyjna książka o rekurencji Ozorków

Rekurencja jest świetna ... co więcej, dla Ciebie może oznaczać udaną rozmowę kwalifikacyjną! To metoda pomocna w rozwiązywaniu trudnych zagadnień: sprowadza złożone problemy do znacznie łatwiejszych. Myślenie rekurencyjne przydaje się często podczas projektowania oprogramowania, nawet jeśli nie stosuje się w nim wprost rekurencji. Wielu twórców oprogramowania jej unika, uważa ją bowiem za trudną i niezrozumiałą. Przekonaj się, że jest inaczej! Dzięki tej książce zrozumiesz, że w rekurencji nie kryje się żadna magia. Dowiesz się, na czym polega jej działanie i kiedy warto zastosować algorytm rekursywny, a kiedy lepiej tego nie robić. Poznasz szereg klasycznych i mniej znanych algorytmów rekurencyjnych. Pracę z zawartym tu materiałem ułatwią Ci liczne przykłady programów napisanych w Pythonie i JavaScripcie, pokazujące, jak rozwiązywać przeróżne problemy związane z przechodzeniem przez drzewa, kombinatoryką i innymi trudnymi zagadnieniami. Nauczysz się także skutecznie poprawiać wydajność kodu i algorytmów rekurencyjnych. Sprawdź i zrozum: czym jest rekurencja i jak działają klasyczne algorytmy rekurencyjne w jaki sposób funkcje rekurencyjne wykorzystują stos wywołań jak rekurencja ogonowa upraszcza pisanie funkcji rekurencyjnych dlaczego rekurencja ułatwia rozwiązywanie niestandardowych problemów w jaki sposób optymalizacja i memoizacja zwiększają wydajność algorytmów rekurencyjnych Przygotuj swój mózg na niezłą gimnastykę! David Beazley, legenda Pythona, dwukrotny laureat IEEE Gordon Bell Priz Zanim zastosujesz rekurencję, musisz najpierw... zrozumieć rekurencję! Spis treści: Przedmowa Podziękowania Wprowadzenie Część I. Zrozumieć rekurencję 1. Czym jest rekurencja? Definicja rekurencji Czym są funkcje? Czym są stosy? Czym jest stos wywołań? Czym są funkcje rekurencyjne i przepełnienie stosu? Przypadki bazowe i rekurencyjne Kod przed wywołaniem rekurencyjnym i po wywołaniu rekurencyjnym Podsumowanie Materiały dodatkowe Pytania praktyczne 2. Rekurencja a iteracja Obliczanie silni Iteracyjny algorytm obliczania silni Rekurencyjny algorytm obliczania silni Dlaczego rekurencyjny algorytm obliczania silni jest szalenie nieefektywny? Znajdowanie wyrazów ciągu Fibonacciego Iteracyjny algorytm wyznaczania n-tego wyrazu ciągu Fibonacciego Rekurencyjny algorytm wyznaczania n-tego wyrazu ciągu Fibonacciego Dlaczego rekurencyjny algorytm wyznaczania n-tego wyrazu ciągu Fibonacciego jest mocno nieefektywny? Zamiana algorytmu rekurencyjnego na iteracyjny Zamiana algorytmu iteracyjnego na rekurencyjny Studium przypadku: obliczanie potęg Rekurencyjna funkcja potęgująca Iteracyjne obliczanie potęgi na podstawie wniosków z algorytmu rekurencyjnego Kiedy powinno się korzystać z rekurencji? Tworzenie algorytmów rekurencyjnych Podsumowanie Materiały dodatkowe Pytania praktyczne Zadania 3. Klasyczne algorytmyrekurencyjne Dodawanie liczb zapisanych w tablicy Odwracanie łańcucha znaków Wykrywanie palindromów Wieże Hanoi Algorytm flood fill Funkcja Ackermanna Podsumowanie Materiały dodatkowe Pytania praktyczne Zadania 4. Algorytmy z nawrotami i algorytmy przechodzenia przez drzewa Algorytmy przechodzenia przez drzewo Drzewa w Pythonie i JavaScripcie Przechodzenie przez drzewo Przechodzenie przez drzewo w porządku preorder Przechodzenie przez drzewo w porządku postorder Przechodzenie przez drzewo w porządku inorder Znajdowanie ośmioliterowych słów w drzewie Ustalanie maksymalnej głębokości drzewa Szukanie wyjścia z labiryntu Podsumowanie Materiały dodatkowe Pytania praktyczne Zadania 5. Algorytmy typu "dziel i zwyciężaj" Wyszukiwanie binarne - znajdowanie książki na półce z ułożonymi alfabetycznie pozycjami Sortowanie szybkie - dzielenie nieposortowanej sterty książek na posortowane stosy Sortowanie przez scalanie - łączenie małych stosów kart do gry w większe posortowane stosy Sumowanie liczb zapisanych w tablicy Algorytm mnożenia Karacuby Matematyka kryjąca się za algorytmem Karacuby Podsumowanie Materiały dodatkowe Pytania praktyczne Zadania 6. Permutacje i kombinacje Podstawy teorii mnogości Znajdowanie permutacji bez powtórzeń - usadzanie gości przy weselnym stole Znajdowanie permutacji za pomocą zagnieżdżonych pętli - podejście dalekie od ideału Permutacje z powtórzeniami - narzędzie do łamania haseł Znajdowanie k-elementowych kombinacji za pomocą rekurencji Znajdowanie wszystkich kombinacji zawierających poprawne nawiasowanie Zbiór potęgowy - znajdowanie wszystkich podzbiorów zbioru Podsumowanie Materiały dodatkowe Pytania praktyczne Zadania 7. Memoizacja i programowanie dynamiczne Memoizacja Programowanie dynamiczne z zastosowaniem strategii top-down Memoizacja w programowaniu funkcyjnym Memoizacja w rekurencyjnym algorytmie wyznaczania elementów ciągu Fibonacciego Moduł functools Pythona Co się stanie, gdy przeprowadzimy memoizację "nieczystej" funkcji? Podsumowanie Materiały dodatkowe Pytania praktyczne 8. Optymalizacja rekurencji ogonowej Jak działa rekurencja ogonowa i na czym polega jej optymalizacja? Akumulatory w rekurencji ogonowej Ograniczenia rekurencji ogonowej Rekurencja ogonowa - studium przypadku Rekurencja ogonowa - odwracanie łańcuchów znaków Rekurencja ogonowa - znajdowanie podłańcuchów Rekurencja ogonowa - potęgowanie Rekurencja ogonowa - parzysty/nieparzysty Podsumowanie Materiały dodatkowe Pytania praktyczne 9. Rysowanie fraktali Grafika żółwia Podstawowe funkcje modułu turtle Trójkąt Sierpińskiego Dywan Sierpińskiego Drzewa fraktalne Jak długie jest wybrzeże Wielkiej Brytanii? Krzywa i płatek śniegu Kocha Krzywa Hilberta Podsumowanie Materiały dodatkowe Pytania praktyczne Zadania Część II. Projekty 10. Wyszukiwarka plików Program do wyszukiwania plików Funkcje dopasowujące Znajdowanie plików, których rozmiar w bajtach jest parzysty Znajdowanie plików, których nazwy zawierają każdą z pięciu samogłosek Rekurencyjna funkcja walk() Wywoływanie funkcji walk() Funkcje biblioteki standardowej Pythona przydatne w pracy z plikami Ustalanie nazwy pliku Wyszukiwanie informacji o znacznikach czasowych pliku Modyfikowanie plików Podsumowanie Materiały dodatkowe 11. Generator labiryntów Kod generatora labiryntów Stałe w generatorze labiryntu Tworzenie struktury danych labiryntu Wyświetlanie struktury danych labiryntu Korzystanie z rekurencyjnego algorytmu z nawrotami Rozpoczynanie łańcucha wywołań rekurencyjnych Podsumowanie Materiały dodatkowe 12. Układanie "piętnastki" Rekurencyjny algorytm układania "piętnastki" Kod programu do układania "piętnastki" Stałe w programie Reprezentacja układanki w danych Wyświetlanie układanki Tworzenie nowej układanki Znajdowanie współrzędnych pustego pola Wykonywanie ruchu Cofanie ruchu Tworzenie nowej układanki Rekurencyjne rozwiązywanie piętnastki Funkcja solve() Funkcja attemptMove() Uruchamianie solvera Podsumowanie Materiały dodatkowe 13. Program do rysowania fraktali Fraktale dostępne w programie Algorytm zastosowany w programie Kod programu Fractal Art Maker Stałe w programie i konfiguracja modułu turtle Praca z funkcjami rysującymi kształty Funkcja drawFilledSquare() Funkcja drawTriangleOutline() Funkcja drawFractal() Początek funkcji Obsługa słownika specyfikacji Wykorzystywanie specyfikacji Tworzenie przykładowych fraktali Cztery rogi Spirala kwadratów Podwójna spirala kwadratów Spirala trójkątów Glider z "gry w życie" Conwaya Trójkąt Sierpińskiego Fala Róg Płatek śniegu Rysowanie pojedynczego kwadratu lub trójkąta Tworzenie własnych fraktali Podsumowanie Materiały dodatkowe 14. Efekt Droste Instalowanie biblioteki Pillow Przygotowanie obrazka Kod programu Droste Maker Początek implementacji Znajdowanie obszaru w kolorze magenty Zmiana rozmiaru obrazka Rekurencyjne umieszczanie obrazu w obrazie Podsumowanie Materiały dodatkowe O autorze: Albert Sweigart — programista, projektant oprogramowania i nauczyciel kodowania. Autor licznych książek o Pythonie dla początkujących. Sweigart urodził się w Houston, w stanie Teksas, a obecnie mieszka w San Francisco. Prowadzi blog dostępny pod adresem: https://coffeeghost.net .