Rekurze

Vzhledem k tomu, ze jsem utahany, tak se v linuxu prestavam hrabat a jdu psat clanek o programovani. A vzhledem k tomu, ze v linuxu jsem totalni lama (zatim), tak mam jen anglickou klavesnici, takze dnes bez diakritiky ;) .

Rekneme si neco o rekurzi. Co to je? K cemu to je? Kdy to je? atd.

Obecna definice rekurze je volani objektu sama sebe. V programovani z toho plyne, ze funkce vola sama sebe, tzn. hovorime a rekurzivni funkci. Prakticky to vypada tak, ze funkce vola sama sebe dokud plati nejaka podminka. Az platit prestane, volani funkce se ukonci (pokud ne, tak dojde k nekonecne smycce) a vypise vysledek.

Takze faktorial z peti je 5x4x3x2x1 tudiz 120. Jak je videt, tento algoritmus si o volani rekurzi primo rika. Ukazky budu psat v pascalu nebot to je vyukovy jazyk, ale ve smes je to jedno pokud jde aspon priblizne o podobny jazyk (C, Java, Php, Ruby, JavaScript, ...) Takze funkce rekurze bude vypadat takto:

	function fak(input:integer):integer;

            begin
		if not(input<2) then begin
			fak:=input*fak(input-1);
		end else begin
                        	fak:=1;
		end;
	end;

Procedura nacte cislo a to vynasobi cislem o jedno mensim. To se opakuje, dokud cislo neni mensi nez dva (coz je jednicka), pote se zavola else vetev podminky if a funkce konci. Aby to bylo uplne jasne, zahrajeme si jeste na prekladac Borland Pascalu a ukazeme si to zive ;) .

Do nasi procedury vlozime napriklad cislo 5 a vypiseme vysledek.

	writeln(fak(5));

Procedura vezme petku a udela nasledujici kroky:

	    fak:=5*fak(5-1) -> 
	-> fak:=5*fak(4) ->
	-> fak:=5*4*fak(4-1) -> a tak dal az do :

        procedure odcitani1(input:integer);
        begin
             if not(input<1) then begin
                write(input:2);
                odcitani1(input-1);
             end;
        end;

  
        procedure odcitani2(input:integer);
        begin
             if not(input<1) then begin
               odcitani2(input-1);
               write(input:2);
             end;
        end;

Tak co, cim se to lisi? Ano jsou tam prehozeny dva radky a to "write" a volani funkce "odcitani". Myslite si, ze se to ve vysledku nezmeni? OK, tak si to zkusime.

odcitani1(5) se rovna:

A ted druhy priklad, zavolame odcitani2(5) :

Komu to stale neni jasne, mrknete dal. Uvadim jeste jednou ten samy vypocet avsak trosku jinak. Zavolame znovu odcitani2(5).

 1  	zavola odcitani2(5),
 2  	|   	zavola odcitani2(4),
 3  	|       |	zavola odcitani2(3),
 4  	|       |	|	zavola odcitani2(2),
 5  	|       |	|	|	zavola odcitani2(1),
 6  	|       |	|	|	|	zavola odcitani2(0) 
 7  	|	|	|	|	vypise se 1,
 8  	|	|	|	 vypise se 2,
 9  	|       |	vypise se 3,
10 	|   	vypise se 4,
11 	vypise se 5.

Kazde odsazeni odpovida jednomu cyklu. Takze radek 1 a 11 je v jednom cyklu, ale nez se z radku 1 dostaneme na radek 11, musime znovu zavolat funkci a tentokrat na radku dva, ke kteremu patri radek 10, ale aby jsme se mohli dostat k radku 10, musime zavolat znovu funkci, tzn. radek 3 a tak dal az na radek 6, ktery konecne uz nic nevola a muze se dostat na radek 7 pak 8, 9, 10, 11.

Vysledek tedy bude: 1 2 3 4 5

Deleni rekurze:

Rekurze prima nebo linearni je jiz zminovany priklad naseho faktorialu. Co se rekurze neprime tyce, ve smysluplnych vecech jsem ji zatim pouzitou nevidel (nekdo urcite rad doplni). Co se tyce rekurze sromove, tak me napada prochazeni adresaru, nebot to je stromova struktura.

Rekneme, ze mame adresar Home v nem adresar user. V adresari user jsou dva adresare a to Pepa a Karel a kazdy znich ma v adresari nejake soubory. Kdyz si to graficky znazornime vypada to nejak takhle:

	Home--user--Pepa--soubor1
		|     |
		|     |---soubor2 
 		|     |
		|     '---soubor3
		|
		'---Karel-soubor1
		      |
		      '---soubor2

A my chceme vypsat vsechny soubory. Pozadovany vypis bude vypadat tedy takto:

		soubor1
		soubor2	
		soubor3
		soubor1
		soubor2

V pascalu se mi nechce tohle programovat, takze to jen slovne zhrnu. Budeme potrebovat funkci, ktera jako argument vezme adresar. V nem funkce najde vsechny soubory a kazdy otestuje, jestli to nahodou neni adresar. Pokud to je, soubor vypise jeho jmeno, pokud to je adresar, zavola funkce sama sebe s nalezenym adresarem. To se opakuje tak dlouho, dokud funkce naleza nejake adresare.

Učinnost:

Co se ucinnosti rekurze tyce, tak zase na tom tak slavne neni. Napriklad nas prvni priklad jde prepsat do cyklu for ci while a provede se daleko rychleji nez ten nas a to hlavne kvuli mensi narocnosti na pamet. Pri kazde rekurzi se totiz vse uklada znovu do pameti a kdyz se dojede na konec, zase se to z te pameti cte. Ale nic to nemeni na tom, ze rekurze je prehlednejsi a je lepsi na reseni rekurzivnich problemu , napriklad adresarova struktura.

Tak to je vse co bych v tomhle miniclanku napsal , snad se to nekomu bude libit a treba napise jak na alsu v linuxu, ci jak na sambu.