Wprowadzenie w rekurencje (skrypt) Gliwice

W Wydawnictwie SGGW w lipcu ukazała się książka "Wprowadzenie w Rekurencje" (autorzy: W.Kwasowiec, W.Karwowski). Książka ta szczegółowo pokazuje, w jaki sposób można zwięźle i elegancko wyrazić informatyczne rozwiązania różnych problemów (matematycznych oraz wziętych z życia) dotąd pisanych klasycznie-nierekurencyjnie. SPIS TREŚCI Wstęp ... 5 Rozdział 1. Definicja rekurencji ... 7 1.1. Czy bezsens rekurencji? ... 7 1.2. Pojęcie rekurencji w matematyce ... 8 1.3. Ciągi rekurencyjne ... 11 1.4. Określenie rekurencji w informatyce ... 13 1.5. Rekurencyjna definicja typu ... 16 1.6. Rekurencyjne odwołania do modułów ... 21 Rozdział 2. Zagadnienia proste ... 23 2.1. Wstęp ... 23 2.2. Kolejność instrukcji w rekurencji ... 23 2.3. Sumowanie, mnożenie i potęgowanie ... 25 2.4. Cyfry liczb naturalnych ... 28 2.5. Liczby pierwsze ... 30 2.6. Liczby nazwane ... 32 2.7. Rekurencyjna zgadywanka ... 38 2.8. Wypłata pieniędzy ... 42 2.9. Odwracanie słów ... 49 2.10. Obliczanie NWD ... 53 Rozdział 3. Problemy matematyczne ... 57 3.1. Wstęp ... 57 3.2. Ciąg Fibonacciego ... 57 3.3. Funkcja Ackermanna ... 60 3.4. Reprezentacja liczb naturalnych ... 68 3.5. Wykrywanie fałszywej monety ... 75 3.6. Schemat Hornera ... 79 3.7. Pierwiastkowanie ... 89 Rozdział 4. Tablice ... 95 4.1. Wstęp do tablic ... 95 4.2. Sumowanie ... 95 4.3. Porządkowanie – sortowanie ... 100 4.4. Sortowanie tablic przez selekcję ... 107 4.5. Układy równań liniowych ... 111 4.6. Wyznacznik ... 117 4.7. Permutacje elementów tablicy ... 121 Rozdział 5. Problem wież z Hanoi ... 125 5.1. Specyfikacja problemu wież z Hanoi ... 125 5.2. Rekurencyjne rozwiązanie problemu wież z Hanoi ... 126 5.3. Uproszczona implementacja procedury WiezeHanoi ... 132 5.4. Animacja wież z Hanoi ... 134 5.5. Dynamiczna implementacja procedury WiezeHanoi ... 142 5.6. Wieże Hanoi z ograniczeniami ... 153 5.7. Uogólnione wieże z Hanoi ... 158 Literatura ... 180