Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Wprowadzenie
9
samej.Wielealgorytmówmacharakterrekurencyjny.Rozważmynaprzykład
instrukcjesłużącedowyszukiwaniasłowawsłownikuzawierającymjednąpo-
zycjęnastronie:HOtwórzsłownik.Jeśliwidziszsłowo,któregoszukasz,przerwij.
Wprzeciwnymrazieposzukajsłowawczęścisłownikaznajdującejsięprzed
lubpobieżącejstronie”.Zauważmy,żewostatnimzdaniuinstrukcjawyszuki-
waniastanowirekurencyjneodniesieniedocałegoprocesu,którewiedzienas
napoczątekwszystkichinstrukcji.Niemapotrzebydodawaniadoopisuczegoś
wrodzajuHpowtarzajtęczynność,ażznajdzieszsłowo”.
Wrozdziale12omawiamrekurencję,któramożebyćstrukturąsterującą,
alewykorzystywanajestrównieżdodefiniowaniasposobóworganizacjidanych.
Wrozdziale13pokazuję,jakróżniemożnarozumiećrekurencję.
Wrozdziałach12i13omawiam:
•ideęrekurencji,
•jakodróżnićposzczególneformyrekurencji,
•dwieróżnemetodyrozszyfrowywaniadefinicjirekurencyjnychinada-
waniaimsensu,
•wjakisposóbmetodytepomagająwzrozumieniurekurencjiizwiązku
międzyjejróżnymiformami.
Dlaczegotojestważne?
RekurencyjnadefinicjaHspróbujidopraw”jestnastępująca:HSpróbujpotrawy.
Jeślismakujedobrze,przerwij.Wprzeciwnymraziedodajszczyptęprzyprawy,
anastępniespróbujidopraw”.Każdepowtarzalnedziałaniemożezostaćopi-
sanerekurencyjniezapomocąpowtarzanegodziałania(tuHspróbujidopraw”)
orazjakiegośwarunkuprzerywającego.
Rekurencjajestkluczowązasadąpozwalającąuzyskaćskończonyopispo-
tencjalnienieskończonychdanychiprzetworzeń.Rekurencjawgramatyce
językaułatwiauzyskanienieskończonegozbioruzdań,aalgorytmrekurencyj-
nypozwalanaprzetworzeniedanychwejściowychodowolnymrozmiarze.
Wzwiązkuztym,żerekurencjajestogólnąinstrukcjąsterującąorazmecha-
nizmemsłużącymdoorganizacjidanych,stanowionaczęśćwielusystemów
oprogramowania.Istniejerównieżkilkabezpośrednichzastosowańrekurencji.
NaprzykładefektDroste,wktórymobrazekzawieramniejsząwersjęsamego
siebie,możnauzyskaćjakorezultatsprzężeniazwrotnegomiędzysygnałem
(obrazek)aodbiornikiem(kamerą).Sprzężeniezwrotnestanowirekurencyjny
opispowtarzalnegoefektu.Fraktaletozkoleinapołypodobnedosiebiewzory
geometryczne,któremogązostaćopisaneprzezrównaniarekurencyjne.Możnaje
spotkaćwnaturze,naprzykładwpłatkachśniegulubkryształach.Wykorzystuje
