JAVA Program brez rekurzije

Pozdravljeni

Imam stevilko npr 143 in stevilke 2,7,14,17,22,63,98. Izracunati moram najmanjso vsoto vseh stevil ki bodo enaka prvi stevilki oz. bo imela najmanjso razliko.
72= 2,7,63
143=17,63,63

Vem, da je rekurzija..vendar je ne obvladam..Nasel sem sicer neko kodo ki s pomocjo rekurzije kreikra vse mozne mnozice danih stevil in potem bi lahko preverjal vsote, vendar bi vas prosil za nasvet/hint(ne za resitev) kako bi se to dalo resit na ne-rekurziven nacin ?

Hvala lp

Rekurzijo lahko vedno simuliras iterativno s skladom. Namesto rekurzivnega klica polozis relevantne vrednosti na sklad in namesto vrnitve iz funkcije poberes vrednosti dol s sklada.
Taka koda je ponavadi se tezje razumljiva koda kot rekurzivna koda, ima pa prednosti kot je vecja hitrost, potencialno manjsa poraba rama in posledicno omogoca vecjo globino kot rekurzija.

Spura brez dodatnih optimizacij nima nobenih prednosti... Razen tega da simulacijo sklada ponavadi daš v heap zato si manj omejen z globino. Ampak tudi velikost sklada ("hardverskega") se da nastavit. Je pa druga zgodba ce lahko ponovno uporabljas pomnilnik v tem primeru, ceprav bi lahko potem isto dosegel tudi pri rekurziji z uporabo globalnih spremenljivk.
Fora te simulacije s skladom je bolj to da lazje vidis ce je mogoce mozno izpeljati (resnično) iterativen pristop, tako da ti potem odpade ta simulacija sklada.

Spura je 1. jun 2012 ob 14:11 izjavil:

MrBrdo je 1. jun 2012 ob 07:25 izjavil:

Spura brez dodatnih optimizacij nima nobenih prednosti... Razen tega da simulacijo sklada ponavadi daš v heap zato si manj omejen z globino. Ampak tudi velikost sklada ("hardverskega") se da nastavit. Je pa druga zgodba ce lahko ponovno uporabljas pomnilnik v tem primeru, ceprav bi lahko potem isto dosegel tudi pri rekurziji z uporabo globalnih spremenljivk.
Fora te simulacije s skladom je bolj to da lazje vidis ce je mogoce mozno izpeljati (resnično) iterativen pristop, tako da ti potem odpade ta simulacija sklada.

Profit je v tem, da se velikost spremenljik, ki se v rekurziji spreminjajo precej manjsi od velikosti vseh parametrov rekurzije (ki ponavadi vkljucujejo tudi pointerje na zacetne parametre, ki se tekom rekurzije ne spreminjajo). Poleg tega moras rekurziji pristet se velikost celega stack okvirja in vseh lokalnih spremenljivk. Postavljanje in podiranje stack okvirjev pa tudi ni zastonj.

Ma to drži bolj za javo, funkcijski pohendlajo večji del problemov pod pokrovom. Je pa pri funkcijskih cela umetnost kako prav izraziti zadevo. Ker semanticno so compilerji ševedno precej butasti. No naredijo kar jim rečeš. Neko moje pravilo je da se ne pacam z iteratorji dokler ni mus. Že zavoljo časa in lepote. Je pa res da se tega ne gremo vCju. Tu se pa rekurzije kolikor se le da striktno izogibam.