rekurzija - problem?

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

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.

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.

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".

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.

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.

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

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

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

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.

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

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.

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.

Misliš dobiti eno ali vse rešitve za sprehod konja čez šahovnico?

Pa recimo, da gremo na vse. Kaj praviš?

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.

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.

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

Vse to je itak sam filozofija.

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...