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

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 algorytmy rekurencyjne
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

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: http://coffeeghost.net.