» »

rekurzija - problem?

rekurzija - problem?

robinzon ::

1.
Prosil bi ce mi lahko kdo razlozi kako deluje rekurzija. Npr. na spodnjem primeru-izracun fakultete.
Jasno mi je da se izvajanje prekine ko je izplnjen pogoj n je manjse ali enako 1 in da ce temu ni tako da se vsakic poklice ponovno funkcija.
Ce bi mi lahko kdo napisal tocno kaksen je vrstni red izracuna za 5!. Predvsem me zanima kako se to shranjuje v sklad in kako se potem to izracuna.
skratka cimvec informacij, da mi bo rekurzija bolj jasna.

2.a lahko naceloma vsako iterativno resitev spravis v rekurzivno-(kako pa?)?


PRIMER: (recimo da je n=5 torej je treba izracunat 5!)


int fakultetaRe(int n)
{
if (n < = 1)
return 1;
else
return fakultetaRe(n-1) * n;
}


hvala vnaprej

Thomas ::

V resnici, se nikoli nobena rekurzija ne izvede. To vedo vsi programerji. Kar se v resnici zgodi je to, da se tolikokrat pokliče nek sub, da en pogoj ni več izpolnjen. Pri fakulteti se toliko časa kliče subrutina ki množi z n in manjša n za 1, dokler n ne doseže ena. Rekurzija je samo - čvek.
Man muss immer generalisieren - Carl Jacobi

Seadoo ::

No Thomas, zdej pa že pretiravaš. Kako ti misliš da se nobena rekurzija ne izvede?

Če funkcija kliče samo sebe, temu pravimo Rekurzivna funkcija. Seveda da se mora klicati vsakič z manjšim pogojem, da se lahko nekje konča, drugače bi tekla v nedogled - zaciklala bi se, po domače.

@Robinzon: Vsako rekurzijo se da spremenit v iterativno funkcijo in obratno, čeprav se to doseže s takšnim kompliciranjem kot je metanje spremenljivk na sklad. Skratka, počneš to, kar bi počel operacijski sistem oz. prevajalnik, kar je pa butasto. Če je izračun takšne narave, da zahteva rekurziven izračun, pol je najbolj pregledno, če ga tako tudi zakodiraš. In seveda obratno.
Problem nastane pri rekurzivnih funkcijah, ki večkrat kličejo same sebe z istimi parametri - tam se uporabljajo pomožne tabele, kjer shranjuješ vmesne rezultate. Recimo izračun fibbonacijevega zaporedja. Za n=2000 kličeš n(1999) in n(1998), potem pa v n(1999) spet n(1998). Opaziš nepotrebno podvajanje računanja? To se seveda eksponentno veča, globlje kot greš. Zato za vsak izračun najprej pogledaš če si ga že izračunal in če ga nisi, ga izračunaš in rezultat shraniš v tabelo.

kopernik ::

Vsak princip pri programiranju lahko spoznaš (razumeš ?) s pomočjo debugiranja. Sploh v novejših IDE okoljih (Delphi, itd..), kjer vidiš po korakih, kako se izvaja koda in kakšne so vrednosti spremenljivk v vsakem trenutku. Mislim, da boš tako tudi rekurzijo najhitreje razumel.

Thomas ::

Ja, če bi debugiral bi videl, da se ta famozna rekurzija VEDNO razdeli na segment kode ki je klicanje pod pogojem in na segment kode, ki deluje kot subrutina. Tako lahko rekurzijo razumeš. Samo figurativna zadeva je rekurzija. Eno fancy ime za iterativno klicanje neke procedure.
Man muss immer generalisieren - Carl Jacobi

kopernik ::

Dejstvo je, da se lahko nekatere probleme zelo elegantno reši s pomočjo rekurzije. En lep primer je branje vsebine diska. Z nekaj vrsticami lahko hitro rešiš tak problem (pa še blizu našemu "razmišljanju" je).

Zgodovina sprememb…

  • spremenil: kopernik ()

Thomas ::

Boš rekel, da rekurzija je dobra bergla? :\ V resnici se disk nič "rekurzivno ne bere". Bergla, kot strukturiranost, recimo. V resnici se disk nič "strukturirano ne bere".
Man muss immer generalisieren - Carl Jacobi

kopernik ::

Ni važno kako se disk dejansko bere (premikanje glav me ne zanima:))). Vem pa, kako pomembno je, da so programi lepo(razumljivo in berljivo) napisani (poleg tega, da so tudi _pravilno_ napisani). Pisati nekajkrat daljšo(in precej manj razumljivo) metodo samo zato, ker ti rekurzija ni všeč? Zakaj? Saj je samo drugačen pristop.

Thomas ::

Rekurzija je v resnici:
 

begin:

do something


under condition do something and later GOTO begin:


say "AMEN!"


Samo nekaj več šminke dodajajo nanjo. V resnici v naravi "prave rekurzije" ni. Program je pa naraven pojav.
Man muss immer generalisieren - Carl Jacobi

kopernik ::

hmmm... o rekurzivnih formulah je govora tudi v matematiki. Tako da je tak način razmišljanja kar pogost.



while(condition) {
do something
}

say AMEN



Je to kaj boljše? Vseeno je z vidika rešitve problema. Vendar je pa včasih (uporaba rekurzije je dejansko redka) princip rekurzije precej bolj eleganten. Kot je lažje reči for(i=0;i < 10;i++) namesto desetkrat ponoviti isti del kode.

Zgodovina sprememb…

  • spremenil: kopernik ()

DMouse ::

Saj noben ne pravi da je odkril Ameriko če uporablja rekurzijo, so pa stvari s pomočjo nje res veliko enostavnejše in preglednejše, pa še manj napak se pojavi v kodi.

Thomas ::

Kakorkoli že, ugotovili smo, da gre za eno navadno zanko, drugega nič. Jaka muda. Matematično gledano, so pa rekurzivne funkcije:
For-loops (which have a fixed iteration limit) are a special case of while-loops. A function which can be implemented using only for-loops is called primitive recursive.
Pa še link.
Man muss immer generalisieren - Carl Jacobi

kopernik ::

To nismo ugotovili, to že vemo in to na faksu tudi učijo

Thomas ::

Samo da je jasno. Kaj pa ni?
Man muss immer generalisieren - Carl Jacobi

kopernik ::

Veliko stvari :) Vsak dan zvem kaj novega. Ok, dovolj o tej rekurziji z moje strani.

Thomas ::

Ne sej smo samo robinzonu razložil, da se ni kej bat rekurzije. Da so pač eni konja našemili v pegaza.
Man muss immer generalisieren - Carl Jacobi

Seadoo ::

Thomas "v naravi prave rekurzije ni". Kaj pa je zate prava rekurzija? In kje je najti tvojo pravo rekurzijo?

Thomas ::

Rekurziven bi bil proces, ki bi bil sestavljen iz dveh podprocesov.

Preverjanja če naj se celoten rekurziven proces prekine in če ne, še klicanja samega sebe.

Rekurzivna fakulteta naj bi preverila če naj neha klicati samo sebe, potem pa naj bi se še poklicala.

V resnici je sestavljena iz dveh delov. En (prvi) del res preveri če naj gre na EXIT, drugi del naredi izračun, množenje in vrne kontrolo prvemu delu. Nikakor ne sproži še ene instance te funkcije. Kar poglej debug!

Lahko daš kontraprimer (iz narave)?
Man muss immer generalisieren - Carl Jacobi

Seadoo ::

Rekurzivna fakulteta mora vrniti kontrolo prvemu delu, vendar šele po izračunu fakultete ze en n manj. Recimo 5! najprej izračuna 4!, pol pa ti množi z 5.

In še ena instanca funkcije se sproži! Oz. prenesejo se lokalne spremenljivke in parametri funkcije na sklad in funkcija se pokliče še enkrat.

BigWhale ::

Rekurzija (navidezna ali prava ali kakrsna koli) je nekaj cesar se clovek oz programer izogiba kot hudic kriza in vampir cesna.

Razen ce ima kdo posebno rad razne, out of stack errorje... ;>

kopernik ::

Ne, če pravilno zastaviš problem oz. izstopne pogoje.

Thomas ::

Ako bi se res klicale nove instance (rekurzivne) funkcije, potem bi rekurzivna funkcija, ki računa vsoto (namesto fakultete) do 4 milijarde, bila klicana 4 miljardokrat. Tak orto kompajler je samo za v smeti.
Man muss immer generalisieren - Carl Jacobi

Seadoo ::

Thomas, fakulteta za 4 milijarde, narejena rekurzivno, SE kliče 4 miljardo krat. In če pogledaš tazaden klic, so na stacku točno 4 milijarde krat zmetani parametri gor. Seveda je to zelooo počasno, ampak tako je.

Kako vsoto a+b+c+d+..... compiler spravi v strojno kodo je pa druga stvar.

BigWhale: Kot programer se rekurije čisto nič ne izogibam. Če jo pravilno napišeš, je program zelo pregleden in tudi učinkovit.

Zgodovina sprememb…

  • spremenilo: Seadoo ()

BigWhale ::

> Tak orto kompajler je samo za v smeti.

Kaj bi bilo, ce bi compilerji poceli to kar programerji pisej(m)o.... ;>

Thomas ::

See_a?_Dothis way! Tole rekurzijo znajo tanovi kompilerji sicer počistiti sami. Tastari pa namesto nje naredijo zelo kosmato zanko. Pravzaprav tudi _nič_ rekurzivno. Pri eventualnem "izračunavanju" vsote (ne fakultete, da ne bo še z bitnostjo problemov), pa nimaš do 4 milijarde dovolj RAMa. Recursion bad idea.
Man muss immer generalisieren - Carl Jacobi

zigadr ::

Pogovarjate se o čisto neprimernih primerih za uporabo rekurzije. Računanje fakultete definitivno ne spada med tipične primere rekurzije, saj ta rekurzija izgleda tako, da se do konca poglobi in se vrne nazaj z rešitvijo. Rekurzija je bolj primerna za reševanje problemov, kjer se nekaj časa poglabljaš in prideš do mrtve točke, se vrneš eno stopnjo nazaj in poskusiš drugo možnost, če tudi te ni, še eno stopnjo nazaj in tam poskusiš nekaj drugega itd. Primer: kako naj skakač preskače vsa polja šahovnice, da na vsakega skoči 1x. Pa primerjajte rešitev tega problema z rekurzijo in brez nje...

Zgodovina sprememb…

  • spremenil: zigadr ()

Thomas ::

Misliš dobiti eno ali vse rešitve za sprehod konja čez šahovnico?
Man muss immer generalisieren - Carl Jacobi

zigadr ::

Za oboje se mi zdi bolj smiselna rekurzija. Ali pa tudi samo za ugotavljanje, koliko je možnih rešitev.
Pa recimo da gremo samo na 1 rešitev.

Thomas ::

Pa recimo, da gremo na vse. Kaj praviš?
Man muss immer generalisieren - Carl Jacobi

Seadoo ::

@Thomas: Link ki si ga poslal, govori o tem, da ni "magičnih poti skakača". Se pa na tistih straneh najde tudi razlago, da rekurzivni algoritmi (backtracking) niso najbolj optimalni za reševanje takih primerov.

Seveda lahko za skoraj vsak problem, ki se ga da rešit z rekurzijo na enostaven način najdeš način, ki je hitrejši in izkorišča določene matematične trike. Se pa v procesu izobraževanja programerjev dostikrat zatekamo k takim problemom, ker človek dobi občutek kaj rekurzija zmore in čemu je namenjena. Tak primer je tudi problem skakača na šahovnici. Rešitev z backtrackingom se da v prologu napisati v nekaj minutah, program z linearno časovno zahtevnostjo pa so pogruntali Conrad in sodelavci leta 1994 in je algoritmično gledano precej bolj zahteven.

Thomas ::

Mhm ... dam ti bolj prav, kot zgleda. Jest samo razlagam rekurzijo z njeno dekonstrukcijo. Beseda "dekonstrukcija" mi gre sicer na vsa jetra, ampak boljše zaenkrat ne najdem.
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

Seadoo ::

Ja opažam da ti rekurzija ni lih najbolj všeč :D

zigadr ::

V prid rekurziji je samo, da jo je pri problemih, ki jih lahko zajeme, dosti laže kodirati kot iterativna rešitev istega problema. Iterativna rešitev naj bi bila vedno hitrejša pri delovanju in seveda mogoča za vse probleme, kar rekurzija ni. Sedaj je samo odvisno, ali je dragocenejši čas programerja ali procesorja.

Thomas ::

Seadoo: Ne, rekurzija je ena od zadev, ki se mi zdijo off this world. Podobno kot neskončnost, naprimer. Kot miselni aparat lahko uporabljamo oboje, vsaj dokler se ne zavemo, da v resnici šaflamo simbole. Pa naj označujejo neskončnost, rekurzijo ... ali karkoli.

antitrust: Affirmative.
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

user4683 ::

There is no spoon. -ne, nism falu teme:)

Vse to je itak sam filozofija.

ashi ::

A se men zdi, al je ene ljudi tuki mal strah rekurzije. Ce jim kej ne pase, naj pac uporabljajo iterativne algoritme. Sem pa ze slisal govoriti ljudi, ki jih je blo prou manicno strah rekurzije, ker je niso razumeli.. Ne vidim zakaj ne, sej je vse cist jasno...

Kako pa se vsa rekurzivna funcija izvaja na hadware-skem nivoju nas pa tko al tko ne zanima, ker gre za programsko tehniko, ki nam v dolocenih skrajsa muke, v dolocenih primerih pa poslabsa dan. Uporabljajo jo pametno, tko kot vsako drugo stvar, pa bo slo.

lep dan se naprej...

snow ::

Nisem še do sedaj rabil rekurzije, zato se niti nisem z njo ubadal.

Dajte mi povedat par pametnih primerov, kjer je rekurzija bošlja od iterativnega načina...
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Vesoljc ::

sprehodi čez drevesa?
Abnormal behavior of abnormal brain makes me normal...


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Programiranje-rekurzije

Oddelek: Šola
151473 (964) OrkAA
»

Java metode;

Oddelek: Programiranje
354509 (3701) ragezor
»

JAVA Program brez rekurzije

Oddelek: Programiranje
61125 (920) noraguta
»

rekurzija in iteracija

Oddelek: Programiranje
133084 (2829) Matako
»

rekurzivni izračun matrične determinante

Oddelek: Programiranje
131972 (1760) blabla

Več podobnih tem