Autor Zpráva
nemesix
Profil
#1 · Zasláno: 4. 12. 2005, 00:40:50
Odpovědět Citovat
vedeli by ste mi povedat co su rekurziva? //alebo kopnut sem dajaky odkaz
dikec
bohumil
Profil *
#2 · Zasláno: 4. 12. 2005, 01:46:25
Odpovědět Citovat
rekurzivu neznam, ale zato znam kurzivu (typ pisma). Ale spis asi myslis rekurzi, coz je funkce, ktera vola sama sebe.
nemesix
Profil
#3 · Zasláno: 4. 12. 2005, 14:55:25
Odpovědět Citovat
jj
ale rad by som vedel ako to funguje
,podla toho co si povedal tak ta funkcia bude volat sama seba donekonecna nie?
thingwath
Profil
#4 · Zasláno: 4. 12. 2005, 15:46:09
Odpovědět Citovat 

public class Factorial {

        public static void main (String args[]) {

                int cislo = 4;

                System.out.println (fact (cislo));

        }



        public static int fact (int num) {

                if (num > 1) {

                        return fact (num - 1) * num;

                } else {

                        return num;

                }

        }

}


Malá ukázka, výpočet faktoriálu přes rekurzi.
Časová prodleva: 2 roky
MadSpyder
Profil *
#5 · Zasláno: 7. 12. 2007, 10:42:03
Odpovědět Citovat
Rekurziva ... specialny sposob kedy sa podprogram (procedura alebo funkcia) zawola sama seba zo swojho wnutra
Timy
Profil
#6 · Zasláno: 7. 12. 2007, 11:28:14 · Upravil/a: Timy
Odpovědět Citovat
Dobře, třeba ta odpověď i po dvou letech pro někoho bude užitečná:

Rekurzivní funkce je funkce, která ve svém těle volá sama sebe. Dále každá smysluplná rekurzivní funkce musí mít limitní podmínku, která rekurzi ukoční (funguje to stejně jako cyklus). Přitom ještě (alespoň u nás na katedře ;-)) rozlišujeme rekurzivní funkci a iterativní rekurzivní funkci. Rekurzivní funkce je třeba normální faktoriál: 

function fac($n)
{
	if($n<=1)
	{
		return 1;
	}
	else
	{
		return ($n*fac($n-1));
	}
}


Což nám udělá asi něco takového (fáze navíjení): 
fac(5):
(5 * (fac(4)))
(5 * (4 *(fac(3)))))
(5 * (4 * (3 *(fac(2)))))
(5 * (4 * (3 * (2 *(fac(1)))))
(5 * (4 * (3 * (2 * (1)))))

V tuto chvíli je dosaženo limitní podmínky a funkce se začne odvíjet: 
(5 * (4 * (3 * (2 * (1)))))
(5 * (4 * (3 * (2))))
(5 * (4 * (6)))
(5 * (24))
(120)


Iterativně bychom to provedli bez fáze odvíjení. Výpočet si totiž budeme předávat v argumetnu funkce: 
function fac_iter($n, $i)
{
	if($n<=1)
	{
		return $i;
	}
	else
	{
		return(fac_iter($n-1, $n*$i));
	}
}

Když potom zavoláme fac_iter(5, 1), dostáváme: 
fac_iter(5 ,1)
fac_iter(4, 5)
fac_iter(3, 20)
fac_iter(2, 60)
fac_iter(1, 120)
(120)


Už i tady je vidět, že je to jednodušší. Ale lépe se to demonstruje na výpočtu Fibonacciho posloupnosti. 

function fib($n)
{
	if($n==0)
	{
		return 0;
	}
	elseif($n==1)
	{
		return 1;
	}
	else
	{
		return fib($n-2)+fib($n-1);
	}
}


Tohle je rekurzivní funkce na výpočet n-tého členu Fibonacciho posloupnosti. Teď si opět uděláme diagram, jak bude postupovat najívení a odvíjení:



Myslím, že je docela vidět, že to není příliš efektivní. A to počítáme pouze pátý prvek, zkuste si třeba padesátý, patrně se nedopočítáte. Kdybychom to napsali iterativně, je výpočtní proces mnohem jednodušší: 

function fib_iter($a, $b, $n)
{
	if($n<=0)
	{
		return $a;
	}
	else
	{
		return(fib_iter($b, $a + $b, $n-1));
	}
}


Navíjení by vypadalo takto: 

(fib_iter(0, 1, 5))
(fib_iter(1, 1, 4))
(fib_iter(1, 2, 3))
(fib_iter(2, 3, 2))
(fib_iter(3, 5, 1))
(fib_iter(5, 8, 0))
(5)
HeWeR
Profil
#7 · Zasláno: 7. 12. 2007, 11:36:29
Odpovědět Citovat
nemesix
Rekurze znamená sebeopakování. Používá se velmi často v matematice a informatice. Viz rekurze.
Časová prodleva: 18 let
Toto téma je uzamčeno. Odpověď nelze zaslat.

0