Funkce a zobecňování

Abstrakce je schopnost odhlížet od detailů, které nejsou důležité pro řešení zkoumaného problému. Soustředíme se na společné prvky a vlastnosti, pomocí kterých nacházíme obecnější řešení.

Příklad z běžného života: Alík, Ben a Rex jsou tři konkrétní domácí zvířata. Můžeme je označit abstraktním pojmem „pes“ – tím zanedbáváme řadu jejich vlastností (např. stáří, barvu srsti či rasu) a soustředíme se jen na to, co mají společné. Kdybychom měli doma ještě kocoura Mourka, tak bychom mohli pro jejich společné označení použít třeba kategorii „savec“.

Příklad z programování: Při vykreslování obrázků můžeme vytvořit funkci squareA(), která vykreslí modrý čtverec o velikosti 100, a squareB(), která vykreslí žlutý čtverec o velikosti 200. Lepší je ale vytvořit abstraktnější funkci square(length, color), která vykreslí čtverec libovolné velikosti a barvy (podle zadaných parametrů). Případně můžeme v abstrakci pokračovat dál a vytvořit funkci, která vykreslí libovolný mnohoúhelník (se zadaným počtem vrcholů).

Funkce jsou základním stavebním blokem, pomocí kterého vytváříme programy. Představují konkrétní realizaci obecného principu rozklad na části.

Zjednodušeně řečeno, funkce je kouzlo, kterému něco předložíme (vstup) a ono nám vykouzlí něco jiného (výstup).

• Pohádkový příklad: Zvětšovací kouzelná hůlka, kterou poťukáme zeleninu a ona ji zvětší na dvakrát větší velikost.
• Matematický příklad: Funkce odmocnina, která dáme na vstup číslo a ona nám vrátí jiné číslo (např. pro vstup 25, vrátí výsledek 5).
• Programátorský příklad: Funkce polygon(sides, length), které dáme na vstup dvě čísla (počet stran a délku strany) a ona vykreslí obrázek mnohoúhelníku.

Programy lze často zobecnit (abstrahovat) nahrazením konkrétní hodnoty za obecnou proměnnou. To umožňuje tvořit programy, které řeší obecnější problémy. Například místo několika různých programů pro výpis čísla obklopeného jedničkami stačí jediný:

Při zobecňování je někdy potřeba kromě proměnné zavést také podmíněný příkaz nebo cyklus. Příklad:

Kromě vytváření obecnějších řešení můžeme pomocí zobecňování upravovat programy tak, aby byly přehlednější. Když si v progamu všimneme opakujícího se vzoru (např. opakované výpisy čísla obklopeného jedničkami), můžeme tyto kousky kódu po vhodném zobecnění nahradit společnou funkcí (parametrizovanou proměnnými zavedenými při zobecňování).

Složitý program lze zpřehlednit tím, že ho rozdělíme na několik částí, které vyčleníme do samostatných funkcí. V takovém programu se navíc snáze hledají a opravují chyby, protože můžeme testovat jednotlivé funkce zvlášť.

Příklad: V následujícím programu je výpis posloupnosti 11–14 podobný výpisu posloupnosti 31–34. V obou případech jde o výpis 4 čísel od n+1 do n+4. Můžeme proto tyto výpisy nahradit voláním nové funkce s parametrem n, která bude vypisovat n+1 až n+4.

Program rozdělujeme tak, aby nově zavedené funkce měly jasný význam. Často pomůže všimnout si částí programu, které si jsou hodně podobné (hledání vzorů). Tyto části zobecníme tak, aby je vykonával stejný kód a ten zapíšeme do nové funkce (jejími parametry jsou proměnné potřebné ke společnému zobecnění kódů). Původní kódy pak nahradíme voláním této nové funkce.

Rekurze je využití sebe sama. Příkladem je použití pojmu při jeho vlastní definici nebo obrázek obsahující svoji zmenšenou kopii. Rekurzivní funkce je taková funkce, která pro výpočet využívá sebe sama (s jinými hodnotami parametrů). Využití rekurze často vede k elegantnímu řešení problému. Některé programovací jazyky využívají rekurzi jako základní prostředek pro opakování příkazů (místo cyklů).

Návrh rekurzivních algoritmů

Nejprve určíme podproblémy, které potřebujeme k vyřešení našeho problému (např. pro výpočet faktoriálu n potřebujeme znát faktoriál n - 1). Tyto podproblémy vyřešíme rekurzivně (tedy voláním funkce s jinými parametry) a z výsledků poskládáme výsledné řešení. Dále je nutné určit bázový případ a jeho řešení (např. faktoriál 0 je 1). Bázový případ musí být takový, aby se k němu všechny větve výpočtu časem dostaly, jinak by výpočet nikdy neskončil.

Sebe-reference

Rekurze je příkladem obecnějšího jevu odkazování na sebe sama, tzv. sebe-reference. Sebe-reference se vyskytuje v jazyce (Třeba tato věta mluví sama o sobě.), knihách, divadle, filmu i matematice. Sebe-reference je dokonce hlavní ingrediencí snad nejslavnějších důkazů matematiky (Gödelovy věty o neúplnosti) a také informatiky (existence problémů, pro které neexistuje algoritmus, který by je řešil – např. úloha určit, zda daný program někdy zastaví).

Fraktály

Vedle rekurze jsou nejtypičtějším zástupcem sebe-reference fraktály – obrázky, které jsou soběpodobné, tedy jejich části připomínají obrázek jako celek. Fraktály lze často vidět v přírodě (např. větve stromů, kapradina). Fraktály a rekurze nejsou dva nezávislí reprezentanti sebe-reference, i mezi nimi je silná souvislost. Rekurze je totiž velmi elegantní způsob, jak různé fraktály definovat. Díky tomu často můžeme složité fraktály vykreslit pomocí jednoduchých rekurzivních funkcí.