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

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       17 999×

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.

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 Stavebnice umělé inteligence 1

Stavebnice umělé inteligence 1

Článek popisuje první část stavebnice umělé inteligence. Obsahuje lineární a plošnou optimalizaci.  Demo verzi je možné použít pro výuku i zájmovou činnost. Profesionální verze je určena pro vývojáře, kteří chtějí integrovat popsané moduly do svých systémů.

Obrázek ke článku Hybridní inteligentní systémy 2

Hybridní inteligentní systémy 2

V technické praxi využíváme často kombinaci různých disciplín umělé inteligence a klasických výpočtů. Takovým systémům říkáme hybridní systémy. V tomto článku se zmíním o určitém typu hybridního systému, který je užitečný ve velmi složitých výrobních procesech.

Obrázek ke článku Jak vést kvalitně tým v IT oboru: Naprogramujte si ty správné manažerské kvality

Jak vést kvalitně tým v IT oboru: Naprogramujte si ty správné manažerské kvality

Vedení týmu v oboru informačních technologií se nijak zvlášť neliší od jiných oborů. Přesto však IT manažeři čelí výzvě v podobě velmi rychlého rozvoje a tím i rostoucími nároky na své lidi. Udržet pozornost, motivaci a efektivitu týmu vyžaduje opravdu pevné manažerské základy a zároveň otevřenost a flexibilitu pro stále nové výzvy.

Obrázek ke článku Síla týmů se na home office může vytrácet. Odborníci radí, jak z pracovních omezení vytěžit maximum

Síla týmů se na home office může vytrácet. Odborníci radí, jak z pracovních omezení vytěžit maximum

Za poslední rok se podoba práce zaměstnanců změnila k nepoznání. Především plošné zavedení home office, které mělo být zpočátku jen dočasným opatřením, je pro mnohé už více než rok každodenní realitou. Co ale dělat, když se při práci z domova ztrácí motivace, zaměstnanci přestávají komunikovat a dříve fungující tým se rozpadá na skupinu solitérů? Odborníci na personalistiku dali dohromady několik rad, jak udržet tým v chodu, i když pracovní podmínky nejsou ideální.

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