Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Da li se svaki rekurzivni postupak moze izraziti iterativno i obrnuto?

[es] :: Art of Programming :: Da li se svaki rekurzivni postupak moze izraziti iterativno i obrnuto?

[ Pregleda: 4140 | Odgovora: 8 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

srbinxp

Član broj: 16278
Poruke: 101
*.teol.net



Profil

icon Da li se svaki rekurzivni postupak moze izraziti iterativno i obrnuto?20.05.2004. u 13:38 - pre 219 meseci
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?
 
Odgovor na temu

chupcko
Ima
Beograd

Član broj: 5560
Poruke: 1138

Sajt: www.google.com


+63 Profil

icon Re: Da li se svaki rekurzivni postupak moze izraziti iterativno i obrnuto?20.05.2004. u 20:17 - pre 219 meseci
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 :).

CHUPCKO
 
Odgovor na temu

_owl_

Član broj: 318
Poruke: 1043
*.drenik.net



+3 Profil

icon Re: Da li se svaki rekurzivni postupak moze izraziti iterativno i obrnuto?20.05.2004. u 21:16 - pre 219 meseci
Jesi li bas siguran? Kakav bi bio iterativan algoritam za prolazak kroz graf (recimo za stablo)?
Owl
 
Odgovor na temu

srbinxp

Član broj: 16278
Poruke: 101
*.teol.net



Profil

icon Re: Da li se svaki rekurzivni postupak moze izraziti iterativno i obrnuto?20.05.2004. u 21:30 - pre 219 meseci
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.
 
Odgovor na temu

chupcko
Ima
Beograd

Član broj: 5560
Poruke: 1138

Sajt: www.google.com


+63 Profil

icon Re: Da li se svaki rekurzivni postupak moze izraziti iterativno i obrnuto?21.05.2004. u 08:39 - pre 219 meseci
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 :).

CHUPCKO
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.dial.InfoSky.Net

Sajt: localhost


+4 Profil

icon Re: Da li se svaki rekurzivni postupak moze izraziti iterativno i obrnuto?22.05.2004. u 03:15 - pre 219 meseci
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.. ;)

 
Odgovor na temu

Reljam
Relja Markovic
San Francisco

Član broj: 531
Poruke: 1793
*.client.comcast.net



+18 Profil

icon Re: Da li se svaki rekurzivni postupak moze izraziti iterativno i obrnuto?22.05.2004. u 03:50 - pre 219 meseci
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).
 
Odgovor na temu

hype

Član broj: 16025
Poruke: 13
*.sttnwaho.covad.net



Profil

icon Re: Da li se svaki rekurzivni postupak moze izraziti iterativno i obrnuto?22.05.2004. u 06:38 - pre 219 meseci
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 ;)
for(i=&g->i;c++<++q;w~=0x2) /* RTFC */
 
Odgovor na temu

chupcko
Ima
Beograd

Član broj: 5560
Poruke: 1138

Sajt: www.google.com


+63 Profil

icon Re: Da li se svaki rekurzivni postupak moze izraziti iterativno i obrnuto?22.05.2004. u 14:22 - pre 218 meseci
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.
CHUPCKO
 
Odgovor na temu

[es] :: Art of Programming :: Da li se svaki rekurzivni postupak moze izraziti iterativno i obrnuto?

[ Pregleda: 4140 | Odgovora: 8 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.