Rekurzivne funkcie

Rekurzovne funkcie pomocou DEF FN

Co myslite, daju sa pomocou DEF FN definovat aj rekurzivne funkcie ? Iste ste lahko uhadli, ze sa samozrejme daju, ved inak by som vam tuto otazku nedaval...
Pozrime sa na strukturu takej rekurzivnej funkcie. Na zaciatok si vezmime nejaky jednoduchy priklad - vypocet faktorial. Faktorialy su definovane takto: N! = N*(N-1)*(N-2)*...*2*1. Cize slovensky povedane faktorial cisla N je sucin vsetkych celych kladnych cisel od 1 po N. Tuto funkciu by sme mohli vypocitat nejak takto:

N! =	IF (N=1) THEN 1	: REM nerekurzivna vetva
	IF (N>1) THEN N * (N-1)!	: REM rekurzivna vetva

Ibaze toto je sice napisane velmi pekne, ale do DEF FN sa to zapisat neda, pretoze vo vyraze nemozeme pouzit prikaz IF-THEN. Avsak mozeme pouzit akusi vzdialenu nahradu za IF-THEN - a tou nahradou je binarny operator AND. Tento operator pracuje nasledovne:

X AND Y vrati:	X, ak je Y nenulove (X moze byt aj cislo aj retazec)
	0, ak je Y nulove a X je cislo
	prazdy retazec ak je Y nulove a X je retazec.

Toto sa da velmi pekne vyuzit pri nahrade IF-THEN vo funkciach definovanych "vidlickou". To su take funkcie, ktore maju viac definicii na roznych intervaloch. Napriklad absolutna hodnota by sa dala definovat takto:

ABS X =	IF (X>=0) THEN X
	IF (X<0) THEN -X

Ked to zapiseme do DEF FN a nahradime IF-THEN operatorom AND, bude to vyzerat takto:

DEF FN a(x)=

(x AND x>0)-(x AND x<0)

(x<0) je vyraz, ktory nadobuda hodnotu 0 (akoze nepravda) ak je X nezaporne. Skusme si teraz napisat nejaku inu funkciu, definovanu "vidlickou":

Funkcia B(X) =	IF X<=0 THEN X^2
	IF X>0 THEN LN X

DEF FN b(x)=

(x*x AND x <= 0)+(LN x AND x>0)

Lenze tento zapis pomocou DEF FN ma jednu veliku slabost: ked date pocitacu vypocitat kolko je FN b(-2) tak z toho zblbne a vypise chybove hlasenie "Invalid argument". Preco ? Operator AND totiz vyhodnocuje prvy oprerand aj v pripade, ze druhy je nulovy. To znamena ze funkcia LN sa vyhodnocuje aj vtedy ak X je zaporne alebo nulove.
Za kazdu cenu musime zabepecit aby sa v pripade X<=0 nevyhodnocovala funkcia LN. Kedze pri vyhodnocovani aritmetickeho vyrazu sa vzdy vyhodnocuju vsetky cleny tohto vyrazu, nemozeme tymto sposobom pisat rekurzivne funkcie. Pri vyhodnocovani vyrazu by sa nam zakazdym zacala vyhodnocovat aj rekurzivna vetva funkcie, co by viedlo k zacykleniu a preplneniu zasobnika a skoncilo by to chybovym hlasenim (pripadne kolapsom celeho systemu)...
Aby sme tomu zabranili, musime pouzit nejaky "spinavy" trik. Priklad takeho "spinaveho" triku je pouzitie funkcie VAL "retazec" spolu s operatorom "retazec" AND podmienka. Spravime jednu velmi jednoduchu vec: Akonahle bude X kladne, tak funkcii VAL podhodime na vyhodnotenie retazec "LN x" a v opacnom pripade jej podhodime retazec "x*x". Nasa "vidlickova" funkcia bude potom vyzerat takto:

DEF FN c(x)=

VAL (("x*x" AND x <= 0)+("LN x" AND x>0))

Tymto padom sme zabezpecili aby sa nevyhodnovcovalo LN X pre X<=0. Ked si namiesto LN predstavime rekurzivnu vetvu nejakej funkcie, mozeme tymto sposobom velmi pekne pisat aj rekurzivne funkcie. Napriklad nase faktorialy zapisane rekurzivne budu vyzerat takto:

DEF FN f(n)=

VAL (("1" AND n<2)+("n*FN f(n-1)" AND n >= 2))

Teraz trochu odbocme od cistej matematiky a skusme si napisat jednu zaujimavu funkciu - nazvime ju "nasobenie retazca cislom". Na vstupe bude mat retazet A$ a cislo N, na vystupe bude davat retazec pozostavajuci z N bezprostredne po sebe iducich retazcov A$. Priklad: Nech A$="zx" a N=4 potom vysledok bude "zxzxzxzx".

DEF FN m$(a$,a)=

VAL$ (("""""" AND a<1)+("a$+FN m$(a$,a-1)" AND a >= 1))

Vsimnite si ze aj tato funkcia je pisana rekurzivne. Tych sest uvodzoviek za sebou predstavuje retazec pozostavajuci z dvoch znakov - dvoch uvodzoviek. Prave sest ich je preto lebo ak sa maju v retazci vyskytovat uvodzovky, treba ich napisat dvakrat.
Pouzitie tejto funkcie je velmi rozmanite. Napriklad chceme vypisat na obrazovku N znakov '#'. Namiesto klasickeho

FOR a=1 TO N: PRINT "#";: NEXT a

pouzijeme ovela elegantnejsie

PRINT FN m$("#",N);

Alebo chceme zarovnavat vypisovane cisla podla praveho okraja. Da sa to spravit takto:

PRINT "Hodnota:"; TAB (31-LEN STR$ x);x

Lenze ked chceme aby medzi napisom "Hodnota" a samotnym cislom boli napr. bodky, mozeme s vyhodou pouzit nasu funkciu takto:

PRINT "Hodnota";FN m$(".",23-LEN STR$ x);x

Na zaver si spravme nieco zlozitejsie. Skusme si definovat funkciu "reverse" - obratenie poradia znakov v retazci. Ak bude na vstupe napriklad retazec "abcd", potom na vystupe bude "dcba". Nech tato nasa funkcia pracuje takto: Vezme posledny znak retazca a za neho dopise zvysok retazca, ktory medzi tym uz presiel nasou funkciou "reverse". V pripade retazca dlheho maximalne jeden znak nic netreba obracat a v tom pripade sa vrati ten isty retazec.

DEF FN r$(a$)=

VAL$ (("a$(LEN a$)+FN r$(a$( TO LEN a$-1))" AND LEN a$>1)+("a$" AND LEN a$ <= 1))

Funkcia by sa dala definovat este druhym sposobom: Vezmeme prvy znak retazca a tento prvy znak zapiseme za "reverznuty" zvysok retazca. Zapis takto definovanej funkcie bude vyzerat takto:

DEF FN o$(a$)=

VAL$ (("FN o$(a$(2 TO ))+a$(1)" AND LEN a$>1)+("a$" AND LEN a$ <= 1))

Na prvy pohlad je vsetko v poriadku a aj tento druhy sposob zapisu by mal bez problemov fungovat. Ale ked si ho vyskusate, zistite ze akosi predsa len nefunguje, hoci v nom nie je ziadna do oci bijuca chyba. V com je ten povestny hacik, preco to nefunguje tak ako by malo, nechavam uz na vasu vlastnu uvahu a badanie. Pre znalcov systemu iste nebude ziadny problem odhalit, v kde je pes zakopany...