Vývojové diagramy – rekurze – 15. díl
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
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       10 825×

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 Nový IT hráč na českém trhu

Nový IT hráč na českém trhu

V roce 2015 otevřela v Praze na Pankráci v budově City Tower své kanceláře společnost EPAM Systems (NYSE:EPAM), jejíž centrála se nachází v USA. Společnost byla založená v roce 1993 a od té doby prošla velkým vývojem a stále roste.

Reklama
Reklama
Obrázek ke článku České Radiokomunikace opět hledají nejlepší nápady pro internet věcí

České Radiokomunikace opět hledají nejlepší nápady pro internet věcí

České Radiokomunikace (CRA) pořádají druhý ročník CRA IoT Hackathonů. Zájemci z řad vývojářů a fanoušků moderních technologií mohou změřit své síly a během jediného dne sestrojit co nejzajímavější funkční prototyp zařízení, které bude komunikovat prostřednictvím sítě LoRa. CRA IoT Hackathony se letos uskuteční ve dvou fázích, na jaře a na podzim, v různých městech České republiky. Jarní běh se odstartuje 31. března v Brně a 7. dubna v Praze.

Obrázek ke článku Cloud computing je využíván stále intenzivněji

Cloud computing je využíván stále intenzivněji

Využívání cloud computingu nabývá na intenzitě. Jen v letošním roce vzroste podle analytiků trh se službami veřejného cloudu o 18 %, přičemž o téměř 37 % vzrostou služby typu IaaS. Růst o více než pětinu pak čeká služby poskytování softwaru formou služby, tedy SaaS. Aktuálním trendům v oblasti využívání cloudu se bude věnovat konference Cloud computing v praxi, která se koná 23. března. 2017 v pražském Kongresovém centru Vavruška na Karlově náměstí 5.

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ý