Rekurencyjna książka o rekurencji. Zostań mistrzem rozmów kwalifikacyjnych poświęconych językom Python i JavaScript - ebook

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ę!

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