Rekurze - Historie editací

Tomiksed: /* Příklady */

2017-06-07T08:32:04Z

Příklady

← Starší verze		Verze z 7. 6. 2017, 08:32
Řádka 64:		Řádka 64:

	Fibonacciho posloupnost:		Fibonacciho posloupnost:
		+
		+	Pozor na tento příklad. Fibonacciho posloupnost je jeden z nejhorších příkladů rekurze. Použitím rekurze u fibonacciho posloupnosti se dostáváte na velmi vysokou exponenciální složitost algoritmu, vedoucí k miliardám volání pro počáteční prvky posloupnosti. 50. prvek posloupnosti, skoro 16 miliard volání funkce fibonacci. Tento příklad nepatří do materiálů, natož ke státnicím!!! (pokud tedy není uváděn jako špatný příklad pro použití rekurze)

	int fibonacci(int n) {		int fibonacci(int n) {

Acolade: kategorizace

2014-02-20T06:34:29Z

kategorizace

← Starší verze		Verze z 20. 2. 2014, 06:34
Řádka 73:		Řádka 73:

	{{fav-kiv-bzinf}}		{{fav-kiv-bzinf}}
		+	[[Kategorie:fav-kiv-bzinf]]

81.201.60.162: /* Příklady */

2011-08-25T22:26:57Z

Příklady

← Starší verze		Verze z 25. 8. 2011, 22:26
Řádka 71:		Řádka 71:
	return fibonacci(n - 1) + fibonacci(n - 2);		return fibonacci(n - 1) + fibonacci(n - 2);
	}		}
		+
		+	{{fav-kiv-bzinf}}

Tester: /* Typy rekurze */

2011-08-07T15:38:26Z

Typy rekurze

Tester: /* Příklady */

2011-08-05T11:53:00Z

Příklady

← Starší verze		Verze z 5. 8. 2011, 11:53
Řádka 63:		Řádka 63:
	}		}

−	~~Fibbonacciho~~ posloupnost:	+	Fibonacciho posloupnost:

	int fibonacci(int n) {		int fibonacci(int n) {

Tester: /* Příklady */

2011-08-05T11:52:41Z

Příklady

← Starší verze		Verze z 5. 8. 2011, 11:52
Řádka 69:		Řádka 69:
	return 1;		return 1;
	else		else
−	return fibonacci(n - 1) + fibonacci(n - 2)	+	return fibonacci(n - 1) + fibonacci(n - 2);
	}		}

Tester: /* Příklady */

2011-08-05T11:52:25Z

Příklady

← Starší verze		Verze z 5. 8. 2011, 11:52
Řádka 66:		Řádka 66:

	int fibonacci(int n) {		int fibonacci(int n) {
−	if n <= 2 ~~then~~	+	if (n <= 2)
	return 1;		return 1;
	else		else
	return fibonacci(n - 1) + fibonacci(n - 2)		return fibonacci(n - 1) + fibonacci(n - 2)
	}		}

Tester: /* Typy rekurze */

2011-08-05T11:51:45Z

Typy rekurze

← Starší verze		Verze z 5. 8. 2011, 11:51
Řádka 14:		Řádka 14:


−	* '''Lineární''' - metoda volá pouze jednu svoji kopii (~~Fibonacci,~~ faktorial)	+	* '''Lineární''' - metoda volá pouze jednu svoji kopii (faktorial)
−	* '''Stromová''' - metoda volá více svých kopií (~~Průchod~~ adresářovou strukturou, často Divide & Conquer algoritmy)	+	* '''Stromová''' - metoda volá více svých kopií (Fibonacci, průchod adresářovou strukturou, často Divide & Conquer algoritmy)

	Rekurze však často umožňuje zjednodušení kódu a ušetření času při programování. Často lze rekurzivní problémy řešit také čistě iteračním algoritmem, nebo použitím zásobníku.		Rekurze však často umožňuje zjednodušení kódu a ušetření času při programování. Často lze rekurzivní problémy řešit také čistě iteračním algoritmem, nebo použitím zásobníku.
Řádka 51:		Řádka 51:

	// http://www.abclinuxu.cz/clanky/ruzne/komiks-xkcd-244-stolni-rpg pro ty, to ví co je Dungeons & Dragons		// http://www.abclinuxu.cz/clanky/ruzne/komiks-xkcd-244-stolni-rpg pro ty, to ví co je Dungeons & Dragons
−

	== Příklady ==		== Příklady ==

Tester: /* Příklady */

2011-08-05T11:41:53Z

Příklady

← Starší verze		Verze z 5. 8. 2011, 11:41
Řádka 55:		Řádka 55:
	== Příklady ==		== Příklady ==

−	Výpočet faktoriálu	+	Výpočet faktoriálu:

	int faktorial(int f) {		int faktorial(int f) {
Řádka 64:		Řádka 64:
	}		}

−	Fibbonacciho posloupnost	+	Fibbonacciho posloupnost:

	int fibonacci(int n) {		int fibonacci(int n) {

Tester: /* Příklady */

2011-08-05T11:41:28Z

Příklady

← Starší verze		Verze z 5. 8. 2011, 11:41
Řádka 54:		Řádka 54:

	== Příklady ==		== Příklady ==
		+
		+	Výpočet faktoriálu
		+
		+	int faktorial(int f) {
		+	if (f <= 1)
		+	return 1;
		+	else
		+	return f * faktorial(f - 1);
		+	}
		+
		+	Fibbonacciho posloupnost
		+
		+	int fibonacci(int n) {
		+	if n <= 2 then
		+	return 1;
		+	else
		+	return fibonacci(n - 1) + fibonacci(n - 2)
		+	}

← Starší verze		Verze z 7. 8. 2011, 15:38
Řádka 24:		Řádka 24:
	Iteračně (nesmysl?):		Iteračně (nesmysl?):

−	1) Vytvoříme ukazatel na položku adresářové struktury ukazující "před?" výchozí adresář a uložíme tuto hodnotu do vedlejší proměnné	+	# Vytvoříme ukazatel na položku adresářové struktury ukazující "před?" výchozí adresář a uložíme tuto hodnotu do vedlejší proměnné
−	2) Posuneme ukazatel na další položku adresáře	+	# Posuneme ukazatel na další položku adresáře
−	3) Je-li pod ukazatelem označená položka, nebo prázdno, vrátíme se na předchozí položku a zpět na 2, nebo ukončíme, pokud jsme na uložené položce "před?"	+	# Je-li pod ukazatelem označená položka, nebo prázdno, vrátíme se na předchozí položku a zpět na 2, nebo ukončíme, pokud jsme na uložené položce "před?"
−	5) Je-li pod ukazatelem adresář, označíme jej jako zpracovaný (i když je otázka jak) a posuneme ukazatel na jeho první položku	+	# Je-li pod ukazatelem adresář, označíme jej jako zpracovaný (i když je otázka jak) a posuneme ukazatel na jeho první položku
−	6) Je-li pod ukazatelem soubor, [otevře, vypíše název, zpracuje, přidá do vlastní datové struktury,...], a označíme soubor jako zpracovaný	+	# Je-li pod ukazatelem soubor, [otevře, vypíše název, zpracuje, přidá do vlastní datové struktury,...], a označíme soubor jako zpracovaný
−	7) Zpět na bod 2	+	# Zpět na bod 2

	Zásobníkem:		Zásobníkem:

−	1) Načte obsah adresáře 'cesta' do zásobníku	+	# Načte obsah adresáře 'cesta' do zásobníku
−	2) Prochází položky zásobníku:	+	# Prochází položky zásobníku:
−	i) Je - li položka soubor, [otevře, vypíše název, zpracuje, přidá do vlastní datové struktury,...]	+	## Je - li položka soubor, [otevře, vypíše název, zpracuje, přidá do vlastní datové struktury,...]
−	~~ii)~~ Je - li položka adresář, načte jeho obsah do zásobníku	+	## Je - li položka adresář, načte jeho obsah do zásobníku
−	3) Opakuje body 2 a 3 dokud není zásobník prázdný	+	# Opakuje body 2 a 3 dokud není zásobník prázdný

	Rekurzivně:		Rekurzivně:

−	1) Načíst obsah adresáře 'cesta' a prochází jednotlivé položky	+	# Načíst obsah adresáře 'cesta' a prochází jednotlivé položky
−	2) Narazí - li na soubor, [otevře, vypíše název, zpracuje, přidá do vlastní datové struktury,...]	+	# Narazí - li na soubor, [otevře, vypíše název, zpracuje, přidá do vlastní datové struktury,...]
−	3) Narazí - li na adresář, volá sama sebe na jeho cestu	+	# Narazí - li na adresář, volá sama sebe na jeho cestu

	Vidíme, že pro rekurzi neimplementujeme vlastní zásobník (viz však níže), a kód je přehlednější (Rekurze cca 5 řádek, iteračně mnohem více)		Vidíme, že pro rekurzi neimplementujeme vlastní zásobník (viz však níže), a kód je přehlednější (Rekurze cca 5 řádek, iteračně mnohem více)