[ srbinxp @ 20.05.2004. 13:38 ] @
Na fakultetu smo radili simulaciju rekurzije pomocu iteracije i steka,ali mi je ostalo nejasno da li su iteracija i rekurzija ekvivalentne,tj.jedna se moze uvijek izraziti preko druge i obrnuto,ili nisu?
[ chupcko @ 20.05.2004. 20:17 ] @
A sa kojeg je to faks-a :).

Da, u pravu si, svaki rekurzvni algoritam moze da se transformise u iterativni algoritam, a postupak je malo veci da ga ovde izazem. A sto se tice iterativnih u rekurzvine je dosta trivijalno:


A := while(B)C;

mozemo napisati kao:

A := if(B){C; A}

Dakle eto, taj smer je jednostavan :) za drugi smer, igraj se sa stekom i stavljanjem adrese povratka na stek :).
[ _owl_ @ 20.05.2004. 21:16 ] @
Jesi li bas siguran? Kakav bi bio iterativan algoritam za prolazak kroz graf (recimo za stablo)?
[ srbinxp @ 20.05.2004. 21:30 ] @
Sa PMFa Novi Sad smijer informatika.

Da znam da se simulacija rekurzije vrsi stavljanjem povratne adrese na stek,to nam je ispitni zadatak iz "Strukture podataka i algoritmi" :)

Ima li za smijer koji si naveo neki formalan dokaz iz teorije algoritama?
(Mislim dokaz je vjerovatno analogan,samo trebaju precizne definicije iterativnog i rekurzivnog algoritma)
Potrazicu u Teoriji algoritama one ekvivalencije izmedju prosto rekurzivnih i Tjuring-izracunljivih f-ja i jos necega ne sjecam se cega ,mozda tu ima nesto.
[ chupcko @ 21.05.2004. 08:39 ] @
Ima formalni dokaz, ali on prevazilazi redovne studije, radi se iz torije racunarstva na postdiplomskim studijama racunarstva recimo na Matematickom fakultetu u Boegrade, nisam siguran ali mislim da imas puno radova C.A.R.Hoare-a o tome.

owl, inace izgledao bi slozeno i glomazno i tesko za razumevanje. Ajde za domaci, uzmi neki rekurzivni algoritam i eliminisi rekurziju, ja sam na ispitu raido kule hanoja. To jest morao sam da eliminisem dvostruki poziv rekurzije.

Inace ukratko prvo se eliminisu lokalne promenljive, pa onda argumenti, pa se prepozna tip rekurzije. tail rekurzija se najlakse eliminise:

A: if(B){C;A}else D
se menja sa:
A: while(B)C;D

I naravno sada sledi tezi slucaj kada rekurzija nije tail tipa ... ali eto, igrajte se malo, i owl, otvori um, sve se umesto rekurzije moze resiti sa goto, a onda se lako goto moze izbaciti ako volis cistocu :).
[ -zombie- @ 22.05.2004. 03:15 ] @
owl: naravno da može, i to prilično lako..

u red (FIFO queue) ubaciš prvo koren stabla, i kreneš u petlju. u petlji izvadiš prvi element iz reda, i svu njegovu decu ubaciš na kraj reda. ponavljaš dok red nije prazan..

(ovo je naravno BFS. za DFS efekat umesto reda koristiti FILO stack strukturu)


chp: nikada nisam skapirao zašto matematičari smatraju da sva nauka mora da se i formalno dokaže da bi (po njima) nešto i vredela (mislim baš na hoare-ove i srodne radove)?

programiranje je mnogo lepše (i ako smem da kažem, bliže "umetnosti" ;) u ovom klasičnom nego u tom formalnom (matematičkom) obliku, a koliko mi se čini, praktično nigde se ni ne koristi taj formalizam (osim možda pri programiranju sistema za kontrolu avio saobraćaja)..

a za hanoja ne kapiram, kakav ispit pominješ? hoćeš da kažeš da je zadatak na nekom ispitu bio predstaviti algoritam za kule hanoja iterativno? na kom to ispitu!? na kom fakultetu?!?


i da, slažem se, to je odličan primer, jer je to "naj-rekurzivniji" algoritam (od prostijih) koji znam, tj baš tipičan školski primer.. a nije ni mnogo težak (mada?).. ja sam ga uradio nerekurzivno još pre 100 godina kada je u petnici neko postavio slično pitanje "rekurzivni vs. iterativni algoritmi".

(a što je smešno, tada još nisam formalno znao ni šta je to stack, pa sam umesto steka (za istu namenu, tj na isti način) koristio paskalove stringove. naravno, zbog toga program nije ninašta ličio, ali je bar radio.. ;)
[ Reljam @ 22.05.2004. 03:50 ] @
Koriscenje FILO strukture je prakticno ista stvar kao i rekurzija. Ako ti neko trazi da od rekurzivne funkcije napises nerekurzivnu, obicno se ne misli na koriscenje stack strukture (osim na skolskom nivou).
[ hype @ 22.05.2004. 06:38 ] @
Inace, na pismenom delu ispita (SPA, mada ne znam da li pismeni jos uvek postoji?), cini mi se da je prvi zadatak bio bas eliminacija rekurzije stekom, pa pokupi resene pismene iz biblioteke i eto ti jeftinog znanja... Sto se tice formalnog dokaza, pitaj Djuru ;)
[ chupcko @ 22.05.2004. 14:22 ] @
Pa zato sto je formalni dokaz jedan od retih nacina da znas da li program radi ili ne :). Znas vec pricu, testiranjem se moze dokazati jedino da program ne radi, a za dokaz da program radi u svim slucajevima moras probati sve slucajeve :).

E uzgred to je jedini nacin da racunarstvo pretvorimo u nauku, da ne bude samo skup recepata. Ovako je mnogo blize matematici i mnogo blize pravoj nauci. Ali to je nesto sto ne mozes da razumes ako ti je bitno samo da napises program. Kao sto u arapskoj mtematici je bitno jedino da se primeni recept, i resi jednacina, a kako se doslo do nje, nema veze. Razlika izmedju nadrilekarstva i farmacije je u toj nauci (jedni probaju dok ne uspeju u velikom broju slucajeva, a drugi proucave formalno nesto).

To je i bio jedan moj test sa mali c programima, da vidim koliko njih ce krenuti da pravi teoriju o tome, ali nije niko.

Sto se tice ispita, na usmenom ispitu iz "Teorije Racunarastva" na prvoj godini posdiplomskih studija iz Racunarstva na Matematickom fakultetu Unievrziteta u Beogradu sam imao sledeci od 4 pitanja: Objasniti postupak eliminacije rekurzije sa dokazom korektnosti, primeniti na primeru algoritma kule Hanoja.

Dakle da bi dobio 10, morao sam da pored ostalog napisem iterativne kule hanoja.

Inace ne mora nuzno da se eliminise stekom rekurzija, ali tako rekurziju realizuje skoro svaki C kopajler :).

Inace sto se tice nerekurzivnih kula hanoja, spomenuo bi algoritam Nebojse Vasiljevica koji je to uradio bez steka, jednom for petljom. Koristio je brojeve u promenljivom brojnom sistemu:

0 -> 0
1 -> 1
2 -> 10
3 -> 11
4 -> 20
5 -> 21
6 -> 100
7 -> 101
8 -> 110
9 -> 111
10 -> 120
11 -> 121
12 -> 200
13 -> 201
14 -> 210
15 -> 211
16 -> 220
17 -> 221
18 -> 300
19 -> 301
20 -> 310
21 -> 311
22 -> 320
23 -> 321
24 -> 1000

Eto malo igre za one koji vole razmisljanje.