Python noob - forskjell på rekursiv og non-rekursiv funksjon

[sheherezade]

Vil følgende utsagn bli regnet som rekursivt eller ikke-rekursivt? (Det er x*(i+1) delen jeg er usikker på)

 

" for i in range(factorial):

x= x*(i+1)"

[tomsi42]

Vil følgende utsagn bli regnet som rekursivt eller ikke-rekursivt? (Det er x*(i+1) delen jeg er usikker på)

 

" for i in range(factorial):

x= x*(i+1)"

Dette er en ikke rekursiv funksjon da du gjør alt i en loop. Rekursjon krever at du i utgngspunktet kaller en funksjon som kaller seg selv 0 eller fler ganger.

 

Her vil resultatet av x * (i + 1) lagret i et midlertidig område (temporær variabel eller CPU register) og deretter bli puttet inn i x (og dermed klar til neste runde i loopen).

[kim009]

Vær obs på at python ikke er det beste språket for å foreta altfor dype rekursive kall. Python har også satt en max rekursion dybde som er relativt lav, men den kan økes ved å bruke setrecursionlimit(n). Denne blir satt for å beskytte mot stack overflow siden python bruker mase ekstra minne på rekursive kall. Så i Python er en iterativ (loop som du har gjort) metode å foretrekke fremfor rekursjon om det mange kall som må gjøres, men om du er helt sikker på det ikke er for mange kall som kreves så er det greit å bruke det om det er lettere å skrive en rekursiv kode.

 

Lærte det selv på en hard måte. Hadde løst en stor kompleks oppgave rekursivt bare for å finne ut når jeg testa den til slutt på et fult data sett att python ikke taklet så mange rekursive kall. Måtte skrive om hele greine over på en iterativ måte.

 

 

Men om python er ditt første språk så er dette kanskje så viktig å kunne enda.

Endret 9. november 2012 av kim0085

[EvenAug]

Et rekursivt kall går ut på å kalle samme metode/funksjon flere ganger. Når du jobber med rekursive kall er det viktig at du forstår hva stack overflow er, og hvordan du kan forhindre det. Ofte er det like greit å benytte iterative kall, men på den andre siden er det normalt at rekursive kall får penere kode.

 

Husk at når du jobber med rekursive kall er det viktig at du for hvert kall forenkler problemet ditt. Det er også viktig at du har en stoppeverdi (veldig opplagt). Rekursive kall brukes ofte i "splitt og hersk" metoder hvor du deler et problem opp i mindre delproblemer.

 

Les gjerne litt om rekursjon i kompendiet vi bruker på HiOA i faget Algoritmer og Datastrukturer: http://www.iu.hio.no/~ulfu/appolonius/kap1/5/kap15.html

Kompendiet er basert på java, men det har liten betydning. Prinsippene er de samme.

Endret 9. november 2012 av EvenAug

[LonelyMan]

rekursive kall er dårlig programmering og dårlig utnyttelse av ressurser. Men om du likevel skal gjøre det lønner det seg å bruke minimum 2 parametere og fastcall konvensjon for å unngå stack problemer. Men du kan unngå å lagre for mye på stacken ved å bruke en global buffer og bare sende en peker til den til alle rekursive kall, så er det kun en dword på stacken for hvert kall, det kan bli mange kall totalt uten at det blir overflow, du kan eventuelt justere størrelsen på stacken.

Endret 18. desember 2012 av LonelyMan

[Lycantrophe]

rekursive kall er dårlig programmering og dårlig utnyttelse av ressurser.

Så søt du er.

[LonelyMan]

Lycantrophe, jeg vet ikke hvordan jeg kan svare på det annet enn å være enig uten å være enig.

 

Om du er uenig så tar vi gjerne en diskusjon om det.

Endret 18. desember 2012 av LonelyMan

[Foxboron]

Lycantrophe, jeg vet ikke hvordan jeg kan svare på det annet enn å være enig uten å være enig.

 

Om du er uenig så tar vi gjerne en diskusjon om det.

 

Hvordan kan rekursive funksjoner være en dårlig idee når Haskell har det?!?!

[LonelyMan]

JuletreDuden, fordi industrien har forkastet de beste løsningene til fordel for simplicity. De velger de mest lettvinte løsninger og minimerer skadene så langt som mulig. Det er egentlig hele svaret på det, og det er bare slik ting er.

Endret 18. desember 2012 av LonelyMan

[Lycantrophe]

Hvordan kan rekursive funksjoner være en dårlig idee når Haskell har det?!?!

Rekursjon i seg selv er ikke en dårlig idé.

[LonelyMan]

Rekursive kall er vanlig å bruke, den er ikke dårlig, men den er langt fra optimal.

 

Her er noen fordeler ved rekursive kall.

 

1. Prosedyren som blir rekursivt kalt opp blir garantert cachet, og det øker ytelsen.

2. branch prediction blir mer forutsigbart og klokkesykluser er spart.

3. Om du bruker fastcall konvensjon og mindre enn 3 parametere så slipper du å pushe på stacken

4. Som det ble sagt lengre opp, koden ser mer elegant ut, men dette har bare kosmetisk betydning, og har ingen teknisk betydning

 

Og når det gjelder ulemper så er der noen

 

1. Om du bruker vanlig cdecl konvensjon så må du pushe alle parametere på stacken ved hver eneste rekursive kall om hvert kall har unike verdier (noe som rekursive kall som regel har), det betyr at du kan ha minst 5 write og 5 reads ved hvert kall, memory reads øker antall mikrooperasjoner kraftig for hver iterasjon.

 

2. Om du kjører rekursivt kall på, la oss si 100 tusen iterasjoner, 4 parametere på prosedyren du kaller og du har en cache størrelse på 2 MB, så behøver du 20 bytes data på stacken for hvert kall. 100 000 * 20 = 2 millioner, som er nøyaktig størrelsen på L2 cachen din. Det er ingen plass igjen for dataene som faktisk skal behandles og hele den rekursive stien din blir ingenting annet enn cache pollution.

 

3. Hver gang du kaller en prosedyre rekursivt (istedet for å bruke en ren unrollet loop) så tvinger du prosessoren til å flushe prefetch bufferen, avhengig av tiden din prosessor bruker på å pensjonere instruksjoner, som regel er den 4, men den kan være 3. Og her mister du uhorvelig mange sykluser enn om du ikke brukte rekursive kall.

 

4. Du tvinges til å jobbe med data i avbrutte bulker, maskinen får ikke tid til å varme seg opp. Instruksjoner har en latency, hver gang du skifter til et prosedyre kall tvinger du prosessoren til å vente til instruksjonene er flushet, og her mister du masse tid også.

 

Jeg kunne nevnt mer.

Endret 18. desember 2012 av LonelyMan

[Lycantrophe]

Det er jo helt opp til implementasjonen.

Endret 18. desember 2012 av Lycantrophe

[tomsi42]

Det er vel ikke rekursjon som er en dårlig ide; det er vel heller det at compiler og hardware implementasjon gir problemer når man bruker rekursjon.

[LonelyMan]

For å si det sånn, der fins mange gode ideer som ikke har gode løsninger i andre enden, det kan bety at ideen er god, men hvis der ikke er en fullverdig løsning for ideen så kan det vel ikke sies at den er god i praksis

 

Du vil ikke merke så veldig til problemene ved rekursive kall, maskinen er så rask, men på et diagram hvor du ser tallene (før-og-etter typen diagrammer) så kan du se effekten av det.

 

En god programmerer som vil ha god ytelse bruker minimalt med prosedyre-kall.

 

En strukturert programmerer som ikke ønsker å miste kontrollen på prosjektet sitt deler opp dataene og kallene sine slik at de blir håndterbare.

 

Men om du skal skrive en rutine som du vil gjenbruke gang på gang på gang, hvorfor ikke skrive den for å yte godt til å begynne med, og da lønner det seg å lage en stor loop, istedet for å bruke rekursive kall. Den kommer garantert til å yte bedre.

Endret 18. desember 2012 av LonelyMan

[LonelyMan]

Her har jeg laget to prosedyrer som begge gjør samme oppgave. Første prosedyre (stolpe 1) gjør samme oppgave rekursivt, andre prosedyre (stolpe 2) gjør samme oppgave i én stor loop på 25 prosent av tiden. Dette testet på en ivy bridge prosessor, som er ganske ny.

 

I TILLEGG, så bruker prosedyren med loopen absolutt ingen stack plass, med unntak av noen få bytes, den første vil bruke masse minne, den vil forurense hele cache hierarkiet, potensielt føre til kræsj om ikke nøye implementert, påvirker andre programmer negativt. På nesten alle måter er rekursive kall en ulempe i forhold. Og det er sikkert endel av årsakene til at man går tom for minne, om man har lite av det, tenk om 10 programmer kjører samtidig og alle kjører rekursivt mer eller mindre samtidig, det er som en udetonert bombe som skal tikke hvert mikrosekund, en karusell av resurs-konsumering som hopper kilometervis opp og ned ved hastigheten av moderne prosessorer. Nei, hold deg til looper om du skal være proff. Det er vanskeligere å lage all kode i én stor loop, det er mer krevende, men når den er ferdig er den også mye mer givende. Du får mer igjen for det.

Endret 18. desember 2012 av LonelyMan

[snippsat]

@JuletreDuden

Hvordan kan rekursive funksjoner være en dårlig idee når Haskell har det?!?!

 

@LonelyMan

JuletreDuden, fordi industrien har forkastet de beste løsningene til fordel for simplicity. De velger de mest lettvinte

løsninger og minimerer skadene så langt som mulig. Det er egentlig hele svaret på det, og det er bare slik ting er.

 

Det blir for lett og si at at de "forkaster de beste løsningene til fordel for simplicity".

Man kan ikke ha iterasjon i rene funksjonelle språk(Haskell,Erlang...) ,fordi iterasjon innebærer forandring av

tilstand(indeksen).

 

Dette er et veldig viktig design prinsipp i funksjonelle språk.

Når en "for loop" må være rekursive i funksjonelle språk er det ikke ytelse man tenker på,

men uforanderlighet(immutability)

 

Nå skal ikke jeg komme med noe forklaring,da andre som er mere inne i den funksjonelle verden gjøre det bedere.

Denne er bra.

http://stackoverflow...t-mutable-state

Short answer: you can't.

So what's the fuss about immutability then?

If you're well-versed in imperative language, then you know that "globals are bad". Why? Because they introduce (or

have the potential to introduce) some very hard-to-untangle dependencies in your code. And dependencies are not good;

you want your code to be modular. Parts of program not influence other parts as little as possible. And FP brings you

to the holy grail of modularity: no side effects at all. You just have your f(x) = y. Put x in, get y out. No changes

to x or anything else. FP makes you stop thinking about state, and start thinking in terms of values. All of your

functions simply receive values and produce new values.

This has several advantages.

First off, no side-effects means simpler programs, easier to reason about. No worrying that introducing a new part of

program is going to interfere and crash an existing, working part.

Second, this makes program trivially parallelizable (efficient parallelization is another matter).

 

Intervju med John Hughes forfatter av "Why Functional Programming Matters!"

http://www.infoq.com.../john-hughes-fp

 

tenk om 10 programmer kjører samtidig og alle kjører rekursivt mer eller mindre samtidig, det er som en udetonert bombe som skal tikke hvert mikrosekund

Tjaa funksjonelle språk(Haskell,Erlang...),skal gjøre "concurrent parallel programming" lettere fordi som postet over designet er immutability(no side effects).

Dette med parallell programmering er jo ikke lett,men funksjonelle språk skryter jo veldig at det skal være lettere i deres verden.

Endret 18. desember 2012 av SNIPPSAT

[Foxboron]

Her har jeg laget to prosedyrer som begge gjør samme oppgave. Første prosedyre (stolpe 1) gjør samme oppgave rekursivt, andre prosedyre (stolpe 2) gjør samme oppgave i én stor loop på 25 prosent av tiden. Dette testet på en ivy bridge prosessor, som er ganske ny.

---SNIPP----

 

Vær så snill å skriv koden du brukte. For alt vi vet bruker du et språk uten TCO som selvfølgelig vill gi rekursjon er dårlig bilde.

[LonelyMan]

Det blir for lett og si at at de "forkaster de beste løsningene til fordel for simplicity".

Man kan ikke ha iterasjon i rene funksjonelle språk(Haskell,Erlang...) ,fordi iterasjon innebærer forandring av

tilstand(indeksen).

 

Det er HELT riktig, og det er et språklig problem, ikke mitt problem. Det er sideeffekten av å velge slike språk, de er designet for simplicity, ikke for optimal teknisk implementasjon.

 

Dette er et veldig viktig design prinsipp i funksjonelle språk.

Når en "for loop" må være rekursive i funksjonelle språk er det ikke ytelse man tenker på,

men uforanderlighet(immutability)

 

Ja, og denne immutability'en som du snakker om, som kanskje høres meget komplisert ut for de som leser, handler om dependencies, og denne kneiken er lett å bryte løs fra om du designer loopen din etter noen prinsipper, de prinsippene som gjelder kan jeg ikke automatisk anta at folk her inne kommer til å gjøre, for de er ikke vant å tenke på lavt nivå, på et teknisk nivå. Men å si at det ikke handler om hastighet, men om immutability er det samme som å skyte seg selv i foten, det å knekke dependencies handler nettopp om større hastighet, hehe. Når du fjerner dependencies så kjører andre deler av koden din raskere.

 

Og jeg forstår meget godt hva de mener med å sende inn en verdi og få en annen ut, du fjerner dependencies, men om du skal kjøre en loop flere hundre tusen ganger, så får du likevel bare ÉN enkelt dependency ut av alle iterasjoner, og denne utveier alt det som snakkes om her. Dessuten, så er ikke en buffer global data, du putter pekeren på stacken og den deles av alle trådene og blir lokal, og hver tråd skal referere hver sin del av bufferen, ikke sekvensielt, du skal dele bufferen opp i antall tråder, slik at hver tråd kan cache sin egen del av den globale bufferen. Dette gjør at du får optimal parallell kjøring, med null dependencies.

 

Tjaa funksjonelle språk(Haskell,Erlang...),skal gjøre "concurrent parallel programming" lettere fordi som postet over designet er immutability(no side effects).

 

Ja jeg hører at du snakker om "no side effects", men det går dypere enn som så. Når disse folkene snakker om no side effect, så forstår ikke du helt hva som menes med dette. Jeg kan prøve å forklare på julenisse-språk, og gi et spesifikt eksempel:

 

Om en teknisk anlagt mann kommer frem til julenissen, og forteller han at han benytter seg av optimale metoder for å komme seg fra X til nordpolen på bare minutter, så sier julenissen tilbake: "Ja, men nå har jeg smurt sleden min slik at ikke sleden har noen side effekt på glidningen gjennom snøen så jeg behøver ikke denne gode teknologien.

 

Bare for å få deg til å skjønne at det nivået de snakker om på "no side effects" er bare en bitte liten del av helheten på problemet jeg løser ved å IKKE benytte meg av rekursjon. Det er så latterlig å lese det der.

 

Og ja det er riktig at det er dårlig å bruke globals................................ MEN, bare hvis du ikke vet hva du gjør selvfølgelig.

 

Alle disse tingene som du har nevnt her, det er tekniske problemer som for det meste oppstår fordi programmerere i høynivå språk har en tendens til å gjøre slike stygge uvaner, det er en sekundær advarsel på en måte, for de vet begrensningene, men på det absolutt laveste nivå hvor du vet hva du gjør, så er disse advarslene faktisk skadelidende, de kan gjøre ting verre. Tro det eller ei.

 

Så, alt jeg har å si nå, jeg kan oppsummere for å forhindre all tvil.

 

1: Ja, immutability er en positiv teknisk løsning.

2: Nei, immutability er ikke optimal, langt fra optimal.

3: Immutability i kontekst du snakker om gjør mer skade enn godt.

4: Helhetlig sett, så er immutability noe du bør ha som mål.

5: Nei, den vil ikke og har aldri gjort en kode mest effektiv ved rekursjon.

6: Immutability handles om å fjerne dependencies.

7: Dependencies handler om å gjøre deler av koden raskere (samt andre deler av koden), det handler om flyt, og dette bunner ned til hastighet.

8: Det som diskuteres at det handler om å unngå states for å unngå kræsj o.l er helt og 100% irrelevant, for det bunner ned til å anta at du er inkompetent til å begynne med, og har lite med en god teknisk løsning å gjøre, det handler om en filosofisk løsning på et problem, ikke en teknisk, så jeg overser all filosofi her.

9: Ja det er galt å benytte seg av globals hvis du har den minste lille tvil om hvorfor, så bør du styre unna.

10: Nei, inne i prosessoren så er det ikke noe som heter globals, om du vet hvordan du kan benytte globals uten å ødelegge flyten i koden, så kan du trygt bruke globals, men nå er det ekstremt mange som er religiøst opptatt av å si at du ALDRI skal bruke globals, vel, de sier dette fordi det er bedre å ha en regel som unngår 99% problemer, enn å ha 1% som kan gjøre dette effektivt.

 

Ha en god dag.

 

EDIT: Jeg glemte forresten å si at, rekursive kall kan ikke optimaliseres i en kompilator, det er en prosessor spesifik teknisk og uhåndterlig forhindring, som bare kan løses ved å styre unna den helt. Det jeg har sagt om rekursjon og å styre unna den er ikke noe som kan verken optimaliseres eller bli kvitt av, verken av haskell eller noen andre. Det er bare intel og AMD som kan ordne på dette.

 

Og for å forhindre misforståelser, å bruke funksjoner er selvfølgelig helt legitimt og bra å gjøre, men når man ser etter ytelse, det er da man skal styre unna funksjoner og flate ut hele koden i en stor og stygg loop. Tro meg det kommer til å kjøre raskere. Jeg kan oppsummere dette også:

 

1: Fjerner du rekursive kall, så fjerner du overheaden ved funksjoner, overheaden ved å kalle funksjoner er x antall parametere som skrives til stack, x antall parametere som leses fra stack (f.eks 20 writes (4 integere) og 20 reads) Å lese og skrive fra minnet er ikke optimalt i en kritisk del av koden.

 

2: Fjerner du rekursive kall så sparer du en hel masse stack plass.

 

3: Fjerner du rekursive kall så unngår du at andre deler av koden har mindre stackplass å gå på, unngå sjansen for kræsj. Det handler ikke bare om at den delen av koden som kjører i øyeblikket ikke skal kræsje, men andre funksjoner som avhenger av andre igjen blir mer skadelidende.

 

4: Fjerner du rekursive kall så unngår du cache pollution.

 

5: Fjerner du rekursive kall så har du større mulighet for å unrolle loopen til å yte enda bedre enn den kan gjøre i rekursive kall.

 

6: Fjerner du rekursive kall og vi antar at du rekurser 1 million ganger, med 4 parametere hver gang, så fjerner du 4 millioner memory reads og om du bruker stdcall så fjerner du også 4 millioner memory writes. Men du bruker antakeligvis cdecl konvensjon så du fjerner iallefall 4 millioner memory reads.

 

7. Fjerner du rekursive kall så har du større mulighet for å spre den store stygge loopen din over flere deler av prosessoren og større mulighet for å finne en spredning av mikrooperasjoner delt på tiden prosessoren din pensjonerer instruksjoner, kompilatoren vil finne en bedre løsning her, som gjør at den kjører raskere, dette er bare delvis mulig i rekursive kall.

 

8: Fjerner du rekursive kall så behøver du ikke allokere tråder med masse stackplass, som gjør at andre programmer har tilgjengelig mer minne, unngå store hopp i konsumeringen som gjør hele systemet mye bedre å bruke.

Endret 19. desember 2012 av LonelyMan

[LonelyMan]

Vær så snill å skriv koden du brukte. For alt vi vet bruker du et språk uten TCO som selvfølgelig vill gi rekursjon er dårlig bilde.

 

Jeg har skrevet det i assembler så du vil antakeligvis ikke forstå det, men jeg customizet epilog delen til å benytte cdecl konvensjon, hvilket c++ benytter seg av, og da blir den 100% lik som en kompilator genererer koden, ingen kode kjøres inni prosedyren, det er bare overhead som måles, dvs, du kommer ikke unna det jeg har skrevet, da en kompilator genererer prikk lik kode. Du kan gjerne åpne olly eller en debugger du har og verifisere at c++ genererer lik overhead.

[tomsi42]

Rekursive kall i assembler, ja ja. Noen har for mye fritid på handa