Rekursiv programmering

[qwerty0192]

Hei,

 

hvordan kan man bli bedre/skjønne rekursiv programmering? Personlig føler jeg at jeg ikke har nok forståelse for emnet. Har prøvd å lese bøker, tittett på tutorials osv. Prøvd absolutt alt for å ha god forståelse for det. Personlig skjønner jeg eksempel rekrusjon med fakultet, men hvis jeg skal gjøre noe mer avansert enn det klarer jeg ikke å forstå det. Takker for svar på forhånd  

[siDDis]

Vi bruker rekursjon til så og si ALT MULIG. Det er en av de grunnleggende tingene alle programmere må kunne.

 

En rekursiv funksjon er bare en funksjon som kaller på seg selv

 

f.eks

void say(String message, int times){
    print(message)
    if (times > 0){
        say(message, times -1)
    }
}

Fordelen med rekursive funksjoner er at de ofte er O(n) (Les om Big O notation)

[qwerty0192]

Vi bruker rekursjon til så og si ALT MULIG. Det er en av de grunnleggende tingene alle programmere må kunne.

 

En rekursiv funksjon er bare en funksjon som kaller på seg selv

 

f.eks

void say(String message, int times){
    print(message)
    if (times > 0){
        say(message, times -1)
    }
}

Fordelen med rekursive funksjoner er at de ofte er O(n) (Les om Big O notation)

 

 

 

Nå skjønner jeg hvordan den du har skrevet der funker. Men la oss si eksempel denne:

public int proc(int n) {
        int x = 1;
        if (n> 1) {
            x = proc(n-1) + proc(n-1);
        }
        return x;
    }

Nå skjønner jeg ikke hvordan jeg får 8 her, hvis jeg setter n som 4. Hvilken funksjon går den til først proc(n-1) til venstre eller den til høyre? 

Endret 2. august 2017 av aom

[blured]

Bare rablet ned, men det evalueres vel noe ala dette:

proc(4)
x = (proc(3)) + (proc(3))
x = (x = proc(2) + proc(2)) + (x = proc(2) + proc(2))
x = (x = (x = proc(1) + proc(1)) + (x = proc(1) + proc(1)) + (x = (x = proc(1) + proc(1)) + (x = proc(1) + proc(1))
x = (x = (x = 1 + 1) + (x = 1 + 1))) + (x = (x = 1 + 1) + (x = 1 + 1)))
x = (x = 2 + 2) + (x = 2 + 2)
x = 4 + 4
x = 8

Rekursjon blir veldig mye lettere om du lærer deg et funksjonelt språk, da så og si alt du gjør her er å skrive rekursive funksjoner. Her har du noe som heter "higher-order functions" - dvs du kan ta funksjoner som argumenter, returnere funksjoner, osv, hvilket gjør det mye mer naturlig å skrive funksjonell/rekursiv kode.

 

Scheme - som ikke er så anvennlig i praksis, men veldig elegant, lite og oversiktelig - er vel det språket som er mest brukt på Universiteter for å lære bort funksjonell programmering. Med SICP (Structure and Interpretation of Computer Programs) (link) som 'Bibelen'.

 

Det føles kanskje unødvendig å lære seg et språk som ikke brukes utenfor uni... Men jeg merker at hvordan jeg skriver funksjonell (og dermed rekursiv) kode i f.eks. JavaScript har blitt svært mye bedre etter at jeg tok meg tiden til å lære meg Scheme. Mange likheter når det kommer til hvordan ting evalueres osv også.

Endret 2. august 2017 av blured

[etse]

Siden man først snakker om rekursiv-programmering tenker jeg det er lurt å nevne at rekursiv programmering kan vi enkelte utfordringer om man går ganske dypt. (altså funksjonenen kaller seg selv mange ganger nedover).

 

I de fleste språk fungerer funksjonskall på den måten at når den kaller en funksjon blir det laget en stack-frame for dette funksjonskalleet (altså allokerer noe minne) som blir frigitt når funksjonen returnerer. La oss f.eks. ta følgende funksjon for å regne ut fakultet (som du sier du forstår)

 

(eksempelkode i python)

def fakultet(number):
    if number == 1:
        return 1
    
    return number * fakultet(number-1)

Om du kaller denne metoden med f.eks. 5, 10 eller 15 så går det helt fint. Men hva skjer om du f.eks. ønsker å regne ut fakulteten av et større tall? 1000, 10000? Siden funksjonen kaller seg N anntall ganger (det vil si, tallet 10.000 krever 10.000 funksjonakall) betyr dette at den på et tidspunkt må holde på 10.000 stackframes. Vil maskinen takle dette, eller vil du gå tom for minne? Og hvor er grensen?

 

Dette er en problemstilling som er lurt å tenke på når man skriver rekursiv kode som potensielt kan gå veldig dypt.

 

For å unngå dette problemet har man kommet opp med noe som man kaller "Tail recursion". Om du googler det vil du finne mange mye bedre beskrivelser av det enn jeg klarer å gi. Men kort fortalt er det en måte å skrive koden på som enkelte språk har laget en optimalisering for, slik at du ikke bruker så mye "unødvendig" minne på å gjøre rekursjon.

 

Problemet med rekusjon er at det ytterste funksjonakallet sin returverdi er avhengig av alle indre funksjonskall før den kan returnere. Ved å skrive tail recursion kan compileren gjøre noen smarte triks. La oss skrive om fakultetsfunksjonen til å være tail-recursive

 

def fakultet(number, tmpSolution=1):
    if number == 1:
        return tmpSolution
    return fakultet(number-1, tmpSolution * number)

Så hva er den store forskjellen her? Det er ikke en stor endring, men en liten og veldig viktig en. Her gjør vi alt av utregning først og så kallet vi en indre funksjon etterpå. I motsetning til det tidligere eksempelet hvor vi kalte en indre funksjon først og så brukte svaret til å gjøre en utregning. Returverien fra vår funksjon er akkurat den samme som returverdien fra det indre kallet.

 

Dette betyr at når vi kaller den indre funksjonen har vi ikke lenger behov for å å huske på noen verdier vi hadde - og man kan bare gjenbruke dette minnet i det indre kallet. Dette fungerer fordi vi har sendt med den midlertidige utregningen til den indre funksjonen - det eneste vi egentlig trenger å huske på tvers av kall.

 

Personlig syntes jeg tail recursion var litt forvirrende å forstå hvorfor det funket i starten, og min forklaring er sikkert ikke den beste. Men vil absolutt anbefale å se litt på det om du ønsker å lære best practices innen funksjonell programmering.

 

PS: Vet python er et dumt eksempelspråk da den ikke egentlig har støtte for tail-recursion optimalisering, mewn håper eksempelet kom frem Språk som støtter dette inkluderer Scheme, Scala, Lisp osv.

Endret 3. august 2017 av etse

[qwerty0192]

Skjønner rekrusjon når det kommer til fakultet og at det lagres i ram. Men kan eksempel ikke skjønne det blurred har gjort.

 

Eksempel når n er 5

 

5 * 4 = 20

4 * 3 = 12 

3 * 2 = 6

2 * 1 = 2

3 * 2 = 6

4 * 6 = 24

5 * 24 = 120

Endret 3. august 2017 av Hårek
Unødvendig stort sitat, innlegget over

[etse]

La oss bruke det enkle eksempelet:

 

def fakultet(number):
    if number == 1:
        return 1
    return number * fakultet(number-1)

Hvis jeg kaller funksjonen med 1? Hva skjer da? Da vil den går inn i den første IF-setniongen og returnere 1 med en gang.

 

Ok, hva skjer om jeg bruker å kalle den med 2?

De vil den treffe else-casen, og utføre return 2 * fakultet(2-1).

Dette trigger en indre kall hvor maskinen må regne ut faktultet(2-1), altså faktultet(1).

Faktultet av 1 fant vi ut i satad at returnerte 1 med en gang gang, og derfor vil statementet

 

 

return 2 * 1

 

Hva nå om vi kaller den med 3?

Da vil den igjen treffe else-casen, og regne ut "return 3 * faktultet(2)".

For å kunne så svar på hva det statementet er må den regne ut fakultet(2), dette gjøres som over.

Altså kallet den fakultet med 2, som treffer else-casen og regner ut 2 * fakultet(1) og returnerer 2.

Dermed vet den at svaret skal være return 3 * 2

 

Viktig å vite at innerst blir utførst først, altså motsatt av hva man kanskje synes er intuitivt (men slik man er vant til fra matematikken).

Med N=5 blir altså følgende utregnionger gjort:

 

N=5:

fac(1) = 1

fac(2) = 2 * fac(1) = 2 * 1 = 2

fac(3) = 3 * fac(2) = 3 * 2 = 6

fac(4) = 4 * fac(3) = 4 * 6 = 24

fac(5) = 5 * fac(4) = 5 * 24 = 120

 

 

Eller slik maskinen ser det:

 

fac(5) = 5 * fac(4)

fac(5) = 5 * ( 4 * fac(3) )

fac(5) = 5 * ( 4 * ( 3 * fac(2) ) )

fac(5) = 5 * ( 4 * ( 3 * ( 2 * fac(1) ) ) )

fac(5) = 5 * ( 4 * ( 3 * ( 2 * 1 ) ) )

fac(5) = 5 * ( 4 * ( 3 * 2 ) )

fac(5) = 5 * ( 4 * 6 )

fac(5) = 5 * 24

fac(5) = 120

Endret 3. august 2017 av etse

[Emancipate]

Bruk et program med debugger som har step-funksjon. Så kjører du koden linje for linje, mens du hele tiden observerer verdiene til variablene.

 

Nå skjønner jeg ikke hvordan jeg får 8 her, hvis jeg setter n som 4. Hvilken funksjon går den til først proc(n-1) til venstre eller den til høyre?

Er dette C++? Da er det udefinert.

[qwerty0192]

Bruk et program med debugger som har step-funksjon. Så kjører du koden linje for linje, mens du hele tiden observerer verdiene til variablene.

 

Nå skjønner jeg ikke hvordan jeg får 8 her, hvis jeg setter n som 4. Hvilken funksjon går den til først proc(n-1) til venstre eller den til høyre?

Er dette C++? Da er det udefinert.

Det er java. 

[etse]

 

Bruk et program med debugger som har step-funksjon. Så kjører du koden linje for linje, mens du hele tiden observerer verdiene til variablene.

 

Nå skjønner jeg ikke hvordan jeg får 8 her, hvis jeg setter n som 4. Hvilken funksjon går den til først proc(n-1) til venstre eller den til høyre?

Er dette C++? Da er det udefinert.

 

Det er java.

 

Det har uenasett ingenting å si hvilken som blir regnet ut først, derfor udefinert i fleste speccer. Fordi du man uansett kalle begge funksjonene for å kunne regne ut verdien av selve summen. Så lenge man har returverdien fra begge kan man legge de sammen

[etse]

 

Bruk et program med debugger som har step-funksjon. Så kjører du koden linje for linje, mens du hele tiden observerer verdiene til variablene.

 

Nå skjønner jeg ikke hvordan jeg får 8 her, hvis jeg setter n som 4. Hvilken funksjon går den til først proc(n-1) til venstre eller den til høyre?

Er dette C++? Da er det udefinert.

 

Det er java.

 

 

 

La oss si vi skal lage en rekursiv fibonacci: (altså finne det N-te tallet i tallrekken 1, 1, 2, 3, 5, 8, 13...)

 

int f(int n) {
    if(n <= 1) {
        return 1;
    }
    return f(n-1) + f(n-2);
}

Utregningen av f(4) kan da presenteres som et tre:

 

Her vil f(4) kalle f(3) og f(2) og legge de sammen. Men det har ikke noe å si hvilken den regner ut først, men må bare ha svaret for begge før den kan regne ut f(4)

 

Ps: beklager dobbelpost, klarer ikke helt se hvordan jeg slår sammen innleggene nå som jeg har postet dem.

Endret 3. august 2017 av etse

[qwerty0192]

Bare rablet ned, men det evalueres vel noe ala dette:

proc(4)
x = (proc(3)) + (proc(3))
x = (x = proc(2) + proc(2)) + (x = proc(2) + proc(2))
x = (x = (x = proc(1) + proc(1)) + (x = proc(1) + proc(1)) + (x = (x = proc(1) + proc(1)) + (x = proc(1) + proc(1))
x = (x = (x = 1 + 1) + (x = 1 + 1))) + (x = (x = 1 + 1) + (x = 1 + 1)))
x = (x = 2 + 2) + (x = 2 + 2)
x = 4 + 4
x = 8

Rekursjon blir veldig mye lettere om du lærer deg et funksjonelt språk, da så og si alt du gjør her er å skrive rekursive funksjoner. Her har du noe som heter "higher-order functions" - dvs du kan ta funksjoner som argumenter, returnere funksjoner, osv, hvilket gjør det mye mer naturlig å skrive funksjonell/rekursiv kode.

 

Scheme - som ikke er så anvennlig i praksis, men veldig elegant, lite og oversiktelig - er vel det språket som er mest brukt på Universiteter for å lære bort funksjonell programmering. Med SICP (Structure and Interpretation of Computer Programs) (link) som 'Bibelen'.

 

Det føles kanskje unødvendig å lære seg et språk som ikke brukes utenfor uni... Men jeg merker at hvordan jeg skriver funksjonell (og dermed rekursiv) kode i f.eks. JavaScript har blitt svært mye bedre etter at jeg tok meg tiden til å lære meg Scheme. Mange likheter når det kommer til hvordan ting evalueres osv også.

Faller ut i tredje linje. Hvorfor blir det 1+1+1+1+1+1+1+1 og ikke 1+1+1+1+1+1? Siden N blir først 3+3. 2+2+2+2 pga du setter ned med 1 på n. Hvis du har muligheten for å si meg det, tror jeg det ville ha vært mer oppklarende  

[etse]

proc(4)
x = ( proc(3)) + (proc(3) )

Begge disse funksjonene blir kallt. Egentlig en etter den andre, men i praksis har ikke rekkefølge noe å si så vi sier det skjer samtidig. Vi vet at proc(3) = proc(3-1) + proc(3-1). Setter derfor dette inn i "ligningen":

 

x = ( proc(2) + proc(2) ) // proc(3)
  + ( proc(2) + proc(2) ) // + proc(3)

Nå har utrykket blitt nøstet ut enda et hakk. Siden proc(3) = proc(2) + proc(2). Igjen har rekkefølge ikke noe å si så vi bare sier alle blir kallt samtidig. Greit å få med seg at proc(2) = proc(1) + proc(1).

Igjen, bare erstattet proc(2) men det som er definisjonen i koden (altså proc(1) + proc(1))

 

x = (                        
        (proc(1) + proc(1)) // proc(2)
      + (proc(1) + proc(1)) // + proc(2)
  ) + (
        (proc(1) + proc(1)) // proc(2)
      + (proc(1) + proc(1)) // + proc(2)
  )

Vi vet at proc(1) = 1, erstatter derfor alle proc(1) med sine returverdier)

 

x = (                        
        (1 + 1)) // proc(2)
      + (1 + 1) // + proc(2)
  ) + (
        (1 + 1) // proc(2)
      + (1 + 1) // + proc(2)
  )

x = ( 2 + 2 ) // proc(3)
  + ( 2 + 2 ) // + proc(3)
// = 4 + 4 = 8

Endret 3. august 2017 av etse

[qwerty0192]

Forstå dessverre fortsatt ikke :/ Vet at proc 2 = 1+1. Men på den tredje linjen trekker jo vi alle med -1. Så da lurer jeg på hvordan de to ekstra 1+1 kommer med?

Endret 3. august 2017 av Hårek
Unødvendig stort sitat, innlegget over

[fokkeslasken]

Hei,

 

hvordan kan man bli bedre/skjønne rekursiv programmering? Personlig føler jeg at jeg ikke har nok forståelse for emnet. Har prøvd å lese bøker, tittett på tutorials osv. Prøvd absolutt alt for å ha god forståelse for det. Personlig skjønner jeg eksempel rekrusjon med fakultet, men hvis jeg skal gjøre noe mer avansert enn det klarer jeg ikke å forstå det. Takker for svar på forhånd

Dette er gode ting å lure på. Ikke minst fordi enhver jobbintervjuer innen programmering med repsekt for seg selv vil spørre om dette.

Selv er jeg litt usikker på nøyaktig hva du spør om. Lurer du på hvordan det fungerer, eller hva det gjør, eller hva poenget er, eller er det noe annet?

 

Selv pleier jeg å illustrere det med et direktory søk. Her med Lua da det er ganske intuitivt, illustrert med Lua tabeller: 

function dirPrint(directory)                 -- funksjonen
    for name,contents in pairs(directory)    -- vi går igjennom directoriet vi fikk
        if (type(contents)=="string") then   -- er det er string, da er det et navn
            print(name)                      -- skriv det på skjermen
        else                                 -- er det ikke en string er det et underdirectory
            print("-->",name)                -- skriv navnet på underdirectory
            dirPrint(name)                   -- gå igjennom dette med samme funksjon
        end
    end
end

Dette er det absolutte minimum. Man burde lagt til en "level" variabel for å indikere directory nivå man er på hvertfall.

function dirPrint(directory,level)                 -- funksjonen
    for name,contents in pairs(directory)    -- vi går igjennom directoriet vi fikk
        if (type(contents)=="string") then   -- er det er string, da er det et navn
            print(level,name)                -- skriv det på skjermen med nivå
        else                                 -- er det ikke en string er det et underdirectory
            print("-->",name)                -- skriv navnet på underdirectory
            dirPrint(name,(level or 0)+1)    -- gå igjennom dette med samme funksjon som neste nivå
        end
    end
end

Det som er viktig å huske er at hver gang du kaller opp funksjonen vil en ny kontekst bli laget. Derfor kan du hoppe til et underdirectory uten at det forrige glemmer hvor den var.

Du kan nesten tenke på dem som separate funksjoner som "alle driver med sitt". Og når du er ferdig i èn funksjon og går tilbake til den som kallet den opp så vil den fortsette med alle variablene intakte.

 

Det er finurligheter som nevnes av andre i tråden her selvfølgelig, men det er teknikaliteter som ikke nevneverdig påvirker selve funksjonsmetodikken.

"Tail call" er èn, som sparer minne. Men - alt dette er detaljer man tar etter at man klarer implementere rekursive funksjoner selv.

Endret 3. august 2017 av fokkeslasken

[etse]

Forstå dessverre fortsatt ikke :/ Vet at proc 2 = 1+1. Men på den tredje linjen trekker jo vi alle med -1. Så da lurer jeg på hvordan de to ekstra 1+1 kommer med?

forstår ikke hva du snakker om. det kommer ingen ekstra 1+1. Dette er ren algebra egentlig. Bare erstatter utrykk med definisjonen. Skal mye til å få det mer inn med teskje enn jeg ga deg i forrige post.

 

proc(2) er forresten proc(1) + proc(1)

 

proc(1) = 1

 

dermed kan man erstatte som i matematikken med ligninger til proc(2) = 1 + 1

Endret 3. august 2017 av etse

[qwerty0192]

Kan skrive ned slik jeg tenker det:

 

Proc(4)

3 + 3 (siden -1 på begge n)

2+2+2+2 (siden n -1 og man legger til to tall til)

1+1+1+1+1+1 (Siden n-1 og man legger to tall til) 

Det er akuratt her jeg har vanskligheter for å forstå hvordan det blir 1*8 og ikke 1*6.

Endret 3. august 2017 av Hårek
Unødvendig stort sitat, innlegget over

[etse]

Du hopper over så mange steg, derfor blir du forvirret.

 

Proc(n>1) = Proc(n-1) + Proc(n-1)
Proc(n==1) = 1

Proc(4) = Proc(4-1) + Proc(4-1) // ikke 3+3
Proc(3) = Proc(3-1) + Proc(3-1) // ikke 2+2
Proc(2) = Proc(2-1) + Proc(2-1) // ikke 1+1
Proc(1) = 1

Sidene dette er definisjonene kan man da driver med erstatning slik som i algebra. Det at du hipoper over hele "proc" biten i steget tror jeg er det som forvirrer deg. Se på min forklaring litt lenger opp og vit at hvert steg er veldig viktig. ikke hopp over noen.

 

Er man da veldig nøyaktig, samme stege som opver så sier man

 

 

x = proc(4)

 

Ok, vi vet at Proc(4) = Proc(4-1) + Proc(4-1), gjør en erstatning:

 

x = proc(3) + proc(3)

 

Ok, vi har enda ikke noe som ser ut som svaret. Vi må finne ut hva proc(3) er, definisjonen sier proc(2) + proc(2). Erstatter:

 

x = (proc(2) + proc(2)) + (proc(2) + proc(2))

 

Ok, vi er litt nærmere. Men enda ikke peiling på hva svaret er - for vi vet ikke hva proc(2) er, utenom at implemetasjonen vår sier det er proc(1) + proc(1). Erstatter alle proc(2) med proc(1) + proc(1):

 

x = ((proc(1) + proc(1)) + (proc(1) + proc(1))) + ((proc(1) + proc(1)) + (proc(1) + proc(1)))

 

Ok, vi ser av implementasjonen av om man kaller proc med 1 så returerer den 1. Derfor kan vi bytte alle proc(1) med 1.

 

x = ((1 + 1) + (1 + 1)) + ((1 + 1) + (1 + 1))

 

Legg merke til at frem til slutten har alt vært funksjonskall. Ingen utregning blir gjort før siste linje. Dette er slik maskinen også regner det ut. Den kaller først alle funksjonene nedover og til slutt legger den sammen returverdiene og får resultatet.

Endret 3. august 2017 av Hårek
Sitat

[qwerty0192]

 

proc(4)

 

proc(3) + (3)

 

proc(2) + proc(2) + proc(2) + proc(2)

 

Hmm, så det legges ikke til ekstra ledd på den siste runden slik som det gjorde med proc(2)? 

Så proc(2) = 1+1 * 4? 

 

P(3) + P(3) 1 ledd

P(2) + P(2) + P(2) + P(2) 2 ledd

P(1) + P(1) + P(1) + P(1) + P(1) + P(1) 3 ledd

 

Det jeg sliter med er hvorfor du får 4 ledd der, når man legger til bare 3 ledd? Har prøvd å følge det du har skrevet. Men så lenge du ikke forstår hvordan det fjerde leddet kommer inn, skaper det bare surr for meg.

Endret 3. august 2017 av Hårek
Unødvendig stort sitat, innlegget over

[blured]

Veldig enig med etse. Når jeg tok Funksjonell Programmering på uni, så slet jeg med det i starten nettopp fordi jeg forsøkte å forstå uten å lære meg å skrive de rekursive kallene på en presis måte. Selv i dag må jeg noen ganger skrive de ut for å forstå komplekse rekursive funksjoner. Men gradvis blir det bare lettere og lettere å forstå/se hvordan det fungerer. Og når du kommer over "kneika" så vil det å løse endel problemer på en rekursiv måte ofte virke lettere, mer lesbart/elegant, osv.