Vývojové diagramy – rekurze – 15. díl
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama

Vývojové diagramy – rekurze – 15. dílVývojové diagramy – rekurze – 15. díl

 
Hledat
Moderní platforma pro vytvoření vašeho nového webu – Wix.com.
Nyní už můžete mít web zdarma.
Vybavení pro Laser Game
Spuštěn Filmový magazín
Laser Game Brno
Laser Game Ostrava

Vývojové diagramy – rekurze – 15. díl

Google       Google       7. 10. 2011       14 015×

Možná někoho z vás napadne, zdali je možné, aby podprogram volal sám sebe. Odpověď je ano, je to možné. A takovému volání se říká rekurzivní volání. Rekurze je trochu kontroverzní téma. Někdo na ni nedá dopustit, někdo se ji vyhýbá jako čert kříži.

Reklama
Reklama

Podprogramy, jak již bylo řečeno, je možné volat jak z hlavního programu, tak i z podprogramů a říkáme tomu rekurzivní volání. Rekurzi si je možné představit i "v reálu". Pokud máte kameru, tak ji připojte k TV a nechte na ni zobrazovat to, co kamera snímá. Následně kamerou zaberte obrazovku TV, výsledkem je rekurze.

Rekurze je trochu kontroverzní téma. Někdo na ni nedá dopustit, někdo se ji vyhýbá jako čert kříži. Problém rekurze je v tom, že je to mocný nástroj, který se snadno může stát noční můrou programátora. Obecně se doporučuje rekurzi se vyhnnout, vždy se dá zapsat algoritmus tak, že nepoužijeme rekurzi, i když se nabízí. Řešení ovšem nebývá tak elegantní.

A proč se rekurze nedoporučuje? Máte podprogram z něhož voláme opět tento podprogram - to je princip rekurze. Pokud bychom měli volání jen tak, bez nějakého dalšího omezení, tak dostáváme nekonečný program. První důležitá věc, která musí být při použití rekurze jasně definována, je podmínka pro zastavení. Jak již bylo řečeno, pokud tato podmínka chybí nebo je "jenom" nepřesná nebo neúplná, tak dostaneme v lepší případě vždy nekonečný program, v horším případě jenom někdy (což se hledá a odstraňuje o poznání hůře).

Druhou věc, která je u rekurze velmi problematická, je spotřeba zdrojů poskytovaných počítačem. Až si ukážeme datové typy, tak uvidíte, že každá proměnná zabírá v paměti místo. Rekurzivní volání vlastně vytváří nové a nové instance podprogramu, s ní vytváří i nové instance jeho proměnných a postupně zaplňuje paměť. A stejně tak je někde potřeba mít zaznamenáno, jak se podprogramy volaly. To se opět ukládá do paměti, která samozřejmě není neomezená. V případě nevhodného použití lze tuto paměť vyčerpat a výsledný program se opět stává nestabilní.

Fibonacciho posloupnost (rekurzivní řešení)

Rekurzi si ukážeme na jednoduchém příkladu - Fibonacciho posloupnosti. Tato posloupnost je definována jako funkce F(n), pro kterou platí, že pro n=0 je výsledek 0, pro n=1 je výsledek 1 a pro n > 1 je výsledek F(n-1) + F(n-2), nebo-li součet předchozích 2 členů.

Zadáním by tedy bylo vytvoření algoritmu pro výpočet Fibonacciho posloupnosti. Na vstupu od uživatele bude číslo N, pro které se má spočítat F(N). Na výstupu bude výsledné číslo z Fibonacciho posloupnosti.

Jelikož je posloupnost zadána rekurzivně (F(n) = F(n-2) + F(n-1)), tak řešení pomocí rekurze se nabízí. Hlavní program bude opět jednoduchý - zadání čísla uživatelem, zavolání podprogramu na výpočet a vypsání výsledku. Výsledek si můžete prohlédnout na obrázku.

Tělo podprogramu je dáno definicí posloupnosti. Pokud je N = 0, tak je výsledek 0 - což bude první podmínka. Druhá podmínka bude na hodnotu N = 1, v tomto případě je výsledek 1. Pro vyšší hodnoty než je 1 je výsledek součtem předchozích 2 hodnot, nebo-li zavoláme výpočet podprogramu znovu pro předchozí 2 hodnoty.

Elegantně jsme přenesli definici posloupnosti do vývojového diagramu. Výsledek, který si můžete prohlédnout na obrázku, je jednoduše čitelný, přehledný a přesně odpovídá definici. Tak proč tedy rekurzi zatracovat? Vývojový diagram je sice pěkný, co se týká je délky a přehlednosti, ale jeho činnost už tak příznivá není. Celé si to demonstrujeme na výpisu průchodu pro zadané N.

Průchod kódem si znázorníme v textovém podání. Každé odsazení je po volání podprogramu. Ukázku provedeme pro N=5

Začátek
N <- 5
F(5)
	X=5
	A=0
	X není 0
	A=1
	X není 1
	B=F(4)
		X=4
		A=0
		X není 0
		A=1
		X není 1
		B=F(3)
			X=3
			A=0
			X není 0
			A=1
			X není 1
			B=F(2)
				X=2
				A=0
				X není 0
				A=1
				X není 1
				B=F(1)
					X=1
					A=0
					X není 0
					A=1
					X je 1
					Návrat(1)
				B=1
				C=F(0)
					X=1
					A=0
					X je 0
					Návrat(0)
				C=0
				A=1+0=1
				Návrat(1)
			B=1
			C=F(1)
				X=1
				A=0
				X není 0
				A=1
				X je 1
				Návrat(1)
			C=1
			A=1+1=2
			Návrat(2)
		B=2
		C=F(2)
			X=2
			A=0
			X není 0
			A=1
			X není 1
			B=F(1)
				X=1
				A=0
				X není 0
				A=1
				X je 1
				Návrat(1)
			B=1
			C=F(0)
				X=1
				A=0
				X je 0
				Návrat(0)
			C=0
			A=1+0=1
			Návrat(1)
		C=1
		A=2+1=3
		Návrat(3)
	B=3
	C=F(3)
		X=3
		A=0
		X není 0
		A=1
		X není 1
		B=F(2)
			X=2
			A=0
			X není 0
			A=1
			X není 1
			B=F(1)
				X=1
				A=0
				X není 0
				A=1
				X je 1
				Návrat(1)
			B=1
			C=F(0)
				X=1
				A=0
				X je 0
				Návrat(0)
			C=0
			A=1+0=1
			Návrat(1)
		B=1
		C=F(1)
			X=1
			A=0
			X není 0
			A=1
			X je 1
			Návrat(1)
		C=1
		A=1+1=2
		Návrat(2)
	C=2
	A=3+2=5
	Návrat(5)
V=5
Vypiš 5
Konec

Z výpisu je patrná slabina použití rekurze. Některé hodnoty (např. F(2)) jsme počítali opakovaně. Zápis algoritmu pomocí rekurze se sice nabízel a je opravdu jednoduchý, ale pro vysoká N by výpočet trval neúměrně dlouho a zbytečně by zatěžoval systémové prostředky počítače. Rekurzi tedy odstraníme resp. vyřešíme úlohu nerekurzivně.

Fibonacciho posloupnost (nerekurzivní řešení)

Při řešení nerekurzivním způsobem využijeme toho, že si můžeme pamatovat předchozí výsledky, a protože se k výpočtu dalšího prvku používají předchozí 2 prvky, tak si budeme pamatovat právě tyto 2 předchozí prvky.

Nejprve ovšem musíme, stejně jako v rekurzivním způsobu řešení, ošetřit výsledné hodnoty pro N=0 a N=1. Program tedy začne 2 podmínkami, ve kterých se bude s těmito hodnotami počítat a může se rovnou přejít k vypsání výsledku.

Nyní můžeme přistoupit k výpočtu dalších členů posloupnosti. Máme zadaný počet (N), do kterého máme posloupnost počítat, takže použijeme cyklus s daným počtem opakování. Pro první 2 hodnoty (0 a 1) jsme udělali na začátku programu podmínky, takže výpočet bude pro hodnoty 2 a vyšší, tj. rozmezí cyklu bude od 2 do N.

Jak již bylo řečeno, další prvek posloupnosti je součtem předchozích dvou. Hodnota F(2) = F(1) + F(0), hodnota F(3) = F(2) + F(1), hodnota F(4) = F(3) + F(2) atd. Z tohoto krátkého zápisu je vidět, že hodnota F(x) je dána součtem řekněme A a B. Pro další prvek posloupnosti F(x+1) se hodnotou B stává předchozí hodnota A a hodnotu A se stává předchozí vypočtená hodnota F(x) - hodnoty se "posouvají". Stejně tak i my je budeme posouvat.

Na začátku budeme mít nějaké F1 a F2, což jsou předchozí 2 hodnoty. Pro další výpočet se musí provést posunutí těchto hodnot, a to tak, že do F2 se přesune hodnota z F1 a do F1 se je přesune naposledy vypočtená hodnota prvku. Zbývá nám pouze určit počáteční hodnoty F1 a F2. Ty jsou dány předpisem Fibbonaciho posloupnosti a jsou 1 resp. 0.

Výsledný vývojový diagram si můžete prohlédnout na obrázku. Výsledek není tak přehledný jako v případě rekurzivního způsobu, ale eliminovali jsme všechny negativní vlastnosti, které rekurzivní způsob řešení sebou nesl. Každý prvek posloupnosti se počítá pouze jednou a nedochází k opakovanému vnořenému volání. Máme pouze 3 pomocné proměnné navíc.

Tímto dílem zakončíme nejenom rekurzi, ale i podprogramy. V dalších dílech budeme podprogramy dále využívat, ale nejprve si projdeme datové typy, abychom se mohli dostat k praktickým úlohám.

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

Hlasování bylo ukončeno    
3 hlasy
Google
Autor se věnuje programování za peníze :)

Nové články

Obrázek ke článku Lepší hosting chrání i vaše data

Lepší hosting chrání i vaše data

Kybernetických útoků na webové stránky rok od roku přibývá, jsou čím dál důmyslnější a páchají stále větší škody. Možná si říkáte, že vás se to netýká, opak je ale pravdou. Jeden z nejčastějších typů útoku využívá zranitelnosti samotných webových stránek a spočívá v umístění škodlivé části programového kódu (tzv. malware) přímo do jejich těla. 

Reklama
Reklama
Obrázek ke článku Spotřebitelé důvěřují novým technologiím při péči o seniory, ale správu financí by jim nesvěřili

Spotřebitelé důvěřují novým technologiím při péči o seniory, ale správu financí by jim nesvěřili

 71 % vítá nové technologie ke sledování zdravotního stavu postarších příbuzných, které jim umožňují žít déle doma

 Pouhých 7 % by svěřilo správu svých financí umělé inteligenci, i kdyby to znamenalo rychleji naspořit prostředky na pořízení bydlení

 64 % respondentů nemá dojem, že firmy a stát dostatečně informují o tom, jaké technologie a jak užívají

Obrázek ke článku Mobilní operátoři využívají digitální modely terénů a kvůli stavebnímu boomu i 3D modely budov

Mobilní operátoři využívají digitální modely terénů a kvůli stavebnímu boomu i 3D modely budov

Mít pokrytí co nejširšího území Česka a nabízet svým zákazníkům co nejlepší signál je společným cílem všech mobilních operátorů. Při plánování sítí proto využívají aktualizovaných digitálních modelů terénu, jež jim umožňují přesně si vypočítat pokrytí a šíření signálu. V hustě zastavěných oblastech a s ohledem na stavební boom jim pak pomáhají také 3D modely budov, které by jim při nesprávném umístění vysílače mohly signál blokovat.

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032019 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý