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

 

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

Google       Google       7. 10. 2011       11 082×

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 Blockchain & Bitcoin konference

Blockchain & Bitcoin konference

V pátek 19. 5. 2017 se v pražském konferenčním centru Andel’s konala Blockchain & Bitcoin konference. Řada odborníků a podnikatelů v oboru blockchainu a kryptoměn představila možnosti budoucího směřování tohoto oboru. Speakeři většinou rusky mluvící provenience prezentovali řešení svých firem založená na technologii blockchainu.

Reklama
Reklama
Obrázek ke článku Malware KONNI se úspěšně skrýval 3 roky. Odhalil ho bezpečnostní tým Cisco Talos

Malware KONNI se úspěšně skrýval 3 roky. Odhalil ho bezpečnostní tým Cisco Talos

Bezpečnostní tým Cisco Talos odhalil celkem 4 kampaně dosud neobjeveného malwaru, který dostal jméno KONNI. Ten se dokázal úspěšně maskovat od roku 2014. Zpočátku se malware zaměřoval pouze na krádeže citlivých dat. Za 3 roky se ale několikrát vyvinul, přičemž jeho současná verze umožňuje útočníkovi z infikovaného počítače nejenom krást data, ale i mapovat stisky na klávesnici, pořizovat screenshoty obrazovky či v zařízení spustit libovolný kód. Pro odvedení pozornosti oběti zasílali útočníci v příloze také obrázek, zprávu a výhružkách severokorejského režimu či kontakty na členy mezinárodních organizací.

Obrázek ke článku Pouze jedna z deseti lokálních firem ví o pokutách plynoucích z GDPR

Pouze jedna z deseti lokálních firem ví o pokutách plynoucích z GDPR

Trend Micro, celosvětový lídr v oblasti bezpečnostních řešení a VMware, přední světový dodavatel cloudové infrastruktury a řešení pro podnikovou mobilitu, oznámily výsledky výzkumu mezi českými a slovenskými manažery zodpovědnými za ochranu osobních údajů, který zjišťoval, jak jsou připraveni na nové nařízení o ochraně osobních údajů (GDPR). Většina firem v České republice a na Slovensku nad 100 zaměstnanců je již s novým nařízením GDPR obeznámena. Výzkum provedený ve spolupráci s agenturou Ipsos ukázal, že téměř 8 firem z 10 o nařízení ví, přičemž jeho znalost je o něco vyšší na Slovensku (89 %) než v České republice (69 %).

Obrázek ke článku Vyděračský software Locky se vrací, tváří se jako potvrzení platby, odhalil tým Cisco Talos

Vyděračský software Locky se vrací, tváří se jako potvrzení platby, odhalil tým Cisco Talos

Jeden z nejznámějších ransomwarů, Locky, se vrací. Po většinu roku 2016 patřil mezi nejrozšířenější vyděračské softwary. Ke svému šíření využíval emailové kampaně s infikovanými přílohami. Ransomware Locky byl rozesílán prostřednictvím botnetu (internetový robot zasílající spamy) Necurs. Jeho aktivita na konci roku 2016 téměř upadla a spolu s ní i šíření ransomwaru Locky. Před několika týdny se Necurs opět probudil a začal posílat spamy nabízející výhodný nákup akcií. Dne 21. dubna zaznamenal bezpečnostní tým Cisco Talos první velkou kampaň ransomwaru Locky prostřednictvím botnetu Necurs za posledních několik měsíců.

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032017 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý