{"id":91143,"date":"2022-10-11T13:13:34","date_gmt":"2022-10-11T18:13:34","guid":{"rendered":"https:\/\/blogging-techies.com\/sw\/vad-ar-rekursion-och-hur-anvander-du-det\/"},"modified":"2022-10-11T13:13:34","modified_gmt":"2022-10-11T18:13:34","slug":"vad-ar-rekursion-och-hur-anvander-du-det","status":"publish","type":"post","link":"https:\/\/blogging-techies.com\/sw\/vad-ar-rekursion-och-hur-anvander-du-det\/","title":{"rendered":"Vad \u00e4r rekursion och hur anv\u00e4nder du det?"},"content":{"rendered":"
\n

Rekursion \u00e4r ett roligt programmeringskoncept men kan vara lite knepigt att l\u00e4ra sig. Rekursion betyder helt enkelt n\u00e5got som upprepar sig. Om du vill se ett fr\u00e4ckt exempel p\u00e5 rekursion, f\u00f6rs\u00f6k att s\u00f6ka efter rekursion<\/strong> p\u00e5 Google. Du hittar ett p\u00e5sk\u00e4gg d\u00e4r f\u00f6rslagen p\u00e5 s\u00f6kresultat \u00e4r rekursiva. Om du d\u00e4remot skulle vilja l\u00e4ra dig hur man kodar en rekursiv funktion, l\u00e4s vidare!<\/p>\n

<\/span> Vad \u00e4r en rekursiv funktion?<\/span><\/h2>\n

En rekursiv funktion \u00e4r en funktion som kallar sig sj\u00e4lv. Du skapar i princip en loop med en funktion. Som du kan f\u00f6rest\u00e4lla dig kan det h\u00e4r vara knepiga funktioner att skriva. Du vill inte att din kod ska k\u00f6ras f\u00f6r alltid.<\/p>\n

I likhet med en loop kommer en rekursiv funktion att styras av ett villkor. N\u00e4r villkoret \u00e4r uppfyllt slutar funktionen att anropa sig sj\u00e4lv, vilket stoppar loopen. S\u00e5 h\u00e4r kan du skapa en funktion som kallar sig sj\u00e4lv utan att den k\u00f6rs f\u00f6r alltid.<\/p>\n

\u00c4ven om en rekursiv funktion fungerar som en loop, exekveras den p\u00e5 olika s\u00e4tt av datorn. S\u00e5, vissa algoritmer \u00e4r mer effektiva i en loop och andra drar nytta av en rekursiv funktion. Men innan vi tittar p\u00e5 hur man anv\u00e4nder en rekursiv funktion m\u00e5ste du veta hur man skriver en.<\/p>\n

<\/span> Hur man skriver en rekursiv funktion<\/span><\/h2>\n

Alla rekursiva funktioner har samma grundstruktur:<\/p>\n

FUNCTION nameIF condition THENRETURN resultELSECALL FUNCTION nameEND FUNCTION<\/pre>\n
Ovanst\u00e5ende exempel \u00e4r skrivet i pseudokod.  Den beskriver strukturen f\u00f6r funktionen, som kan till\u00e4mpas p\u00e5 alla spr\u00e5k.  F\u00f6r enkelhetens skull kommer vi i den h\u00e4r artikeln att koncentrera oss p\u00e5 Python.<\/p>\n
Det f\u00f6rsta att notera om en rekursiv funktion \u00e4r att n\u00e4r villkoret \u00e4r uppfyllt l\u00e4mnar funktionen rekursionen.  Det betyder att n\u00e4r du skriver en rekursiv funktion \u00e4r det f\u00f6rsta du vill best\u00e4mma n\u00e4r du ska stoppa rekursionen.<\/p>\n
Om villkoret inte \u00e4r uppfyllt anropar funktionen sig sj\u00e4lv.  S\u00e5 om du vill skicka information till n\u00e4sta loop m\u00e5ste du skicka den som ett argument i din funktion.  Detta kan ge rekursiva funktioner mycket mer kraft.<\/p>\n
<\/span>Exempel p\u00e5 rekursiv funktion i Python<\/span><\/h3>\n
Det blir mycket l\u00e4ttare att f\u00f6rst\u00e5 hur rekursion fungerar n\u00e4r du ser den i aktion.  F\u00f6r att demonstrera det, l\u00e5t oss skriva en rekursiv funktion som returnerar faktorialen f\u00f6r ett tal.<\/p>\n
Faktorer returnerar produkten av ett tal och av alla heltal f\u00f6re det.  Till exempel \u00e4r faktorv\u00e4rdet 5 5 x 4 x 3 x 2 x 1 eller 120.<\/p>\n
def factorialFunction(numberToMultiply):if numberToMultiply == 1 :return 1else :return numberToMultiply * factorialFunction(numberToMultiply - 1)
result = factorialFunction(3)print(result)\/\/Outputs: 6<\/p><\/pre>\n
Ovanst\u00e5ende program kommer att ge dig resultatet 6, vilket \u00e4r faktorn f\u00f6r siffran 3. Detta kan vara lite f\u00f6rvirrande till en b\u00f6rjan.  Det hj\u00e4lper om vi g\u00e5r igenom programmet steg f\u00f6r steg.<\/p>\n
        N\u00e4r funktionen anropas, numberToMultiply<\/strong> \u00e4r lika med 3. Villkoret \u00e4r inte uppfyllt, s\u00e5 vi g\u00e5r in p\u00e5 annan<\/strong> skick.  V\u00e5r funktion returnerar 3 * men pausas sedan.  Den m\u00e5ste anropa sig sj\u00e4lv f\u00f6r att best\u00e4mma resten av v\u00e4rdet den returnerar.  N\u00e4r funktionen anropas den h\u00e4r g\u00e5ngen \u00e4r v\u00e4rdet p\u00e5 numberToMultiply lika med 2. Villkoret \u00e4r inte uppfyllt, s\u00e5 vi g\u00e5r in p\u00e5 else-villkoret.  V\u00e5r funktion returnerar 2 * men pausas sedan.  Den m\u00e5ste anropa sig sj\u00e4lv f\u00f6r att best\u00e4mma resten av v\u00e4rdet den returnerar.  Funktionen anropas igen.  Den h\u00e4r g\u00e5ngen \u00e4r v\u00e4rdet p\u00e5 numberToMultiply lika med 1. V\u00e5r om<\/strong> villkoret \u00e4r uppfyllt.  Funktionen returnerar 1. Funktionen fr\u00e5n steg 6 kan nu returnera 2 * 1 till funktionen p\u00e5 steg 3. Funktionen p\u00e5 steg tre kan nu returnera 3 * 2 * 1, vilket \u00e4r 6.  <\/ol>\n
    \n<\/figure>\n
    Rekursion \u00e4r ett knepigt begrepp.  Det kan vara bra att t\u00e4nka p\u00e5 det som att stapla en funktion ovanp\u00e5 en annan.  N\u00e4r en funktion \u00e4ntligen \u00e4r l\u00f6st, kan den skicka informationen tillbaka ner i stacken, tills alla funktioner har sitt svar.<\/p>\n
    Detta \u00e4r faktiskt ungef\u00e4r vad din dator g\u00f6r.  N\u00e4r du anropar funktionen h\u00e5lls den i minnet tills den returneras.  Detta inneb\u00e4r att rekursiva funktioner kan anv\u00e4nda mycket mer minne \u00e4n en loop.<\/p>\n
    S\u00e5 det kanske inte \u00e4r effektivt att skriva loopar som rekursiva funktioner, men det \u00e4r ett bra s\u00e4tt att tr\u00e4na p\u00e5 att konstruera dem.  Du b\u00f6r kunna koda loopar som rekursiva funktioner med liknande resultat.<\/p>\n
    <\/span>  Ett exempel p\u00e5 hur man konverterar en loop till en rekursiv funktion<\/span><\/h2>\n
    print(\"Enter an even number:\")i = int(input())while (i % 2) != 0 :print(\"That number is not even. Please enter a new number:\")i = int(input())<\/pre>\n
    Denna loop kan ocks\u00e5 skrivas rekursivt som:<\/p>\n
    def recursiveFunction(number) :if (number % 2) == 0 :return numberelse:print(\"That number is not even. Please enter a new number:\")recursiveFunction(int(input()))
    print(\"Enter and even number:\")i = recursiveFunction(int(input()))<\/p><\/pre>\n
    Det f\u00f6rsta steget \u00e4r att best\u00e4mma n\u00e4r du vill att din funktion ska stoppas.  I det h\u00e4r fallet vill vi att det slutar n\u00e4r ett j\u00e4mnt tal har angetts.  I v\u00e5rt exempel, siffra <\/strong>sp\u00e5rar anv\u00e4ndarens input.  Om de matar in ett j\u00e4mnt tal returnerar vi numret.  Annars kommer vi att forts\u00e4tta att be om ett nytt nummer.<\/p>\n
    F\u00f6r att s\u00e4tta upp slingan anropar vi v\u00e5r funktion igen.  Men den h\u00e4r g\u00e5ngen \u00e4r numret vi skickar till n\u00e4sta funktion det nya numret som anv\u00e4ndaren matat in.  N\u00e4sta funktionsanrop kommer att kontrollera numret.<\/p>\n
    Detta \u00e4r en riktigt d\u00e5lig funktion!  Ja, den kontrollerar om numret \u00e4r j\u00e4mnt, som v\u00e5r loop, men det \u00e4r inte effektivt.  Varje g\u00e5ng anv\u00e4ndaren anger ett udda nummer h\u00e5lls funktionen i minnet och en ny funktion anropas.  Om du g\u00f6r detta tillr\u00e4ckligt m\u00e5nga g\u00e5nger kommer du f\u00e5 ont om minne!<\/p>\n
    <\/span>  Ett verkligt exempel p\u00e5 en rekursiv funktion<\/span><\/h2>\n
    Ovanst\u00e5ende exempel var bra exempel p\u00e5 n\u00e4r man inte ska anv\u00e4nda rekursion.  S\u00e5, var anv\u00e4nds rekursion?  Ett bra exempel p\u00e5 n\u00e4r du skulle vilja anv\u00e4nda rekursion \u00e4r att s\u00f6ka i ett bin\u00e4rt tr\u00e4d.<\/p>\n
    \n<\/figure>\n
    N\u00e4r data \u00e4r strukturerad i ett bin\u00e4rt tr\u00e4d m\u00e5ste du g\u00e5 ner p\u00e5 m\u00e5nga v\u00e4gar f\u00f6r att s\u00f6ka efter data.  Vid varje punkt i tr\u00e4det m\u00e5ste du best\u00e4mma om du vill forts\u00e4tta s\u00f6ka till h\u00f6ger eller v\u00e4nster.  Du kan spara vilken del av tr\u00e4det du bes\u00f6kte i en variabel, men en rekursiv funktion kan naturligtvis sp\u00e5ra den informationen.<\/p>\n
    F\u00f6rest\u00e4ll dig att vi letar efter siffran sex i tr\u00e4det ovan.  Vi skulle kunna g\u00f6ra en rekursiv funktion som s\u00f6ker i tr\u00e4det fr\u00e5n v\u00e4nster till h\u00f6ger.  Algoritmen skulle se ut ungef\u00e4r s\u00e5 h\u00e4r:<\/p>\n
    FUNCTION searchTree(branchToSearch)IF find 6 OR end of tree THENRETURN resultELSEPROCESS branchCALL FUNCTION searchTree(left)CALL FUNCTION searchTree(right)END FUNCTION<\/pre>\n
    I det h\u00e4r pseudokodexemplet skulle algoritmen f\u00f6rst s\u00f6ka p\u00e5 v\u00e4nster sida av tr\u00e4det.  Varje g\u00e5ng den bes\u00f6ker ett nytt nummer pausas funktionen och sparas i minnet.  Detta g\u00f6r att vi kan sp\u00e5ra var vi har varit.<\/p>\n
    Algoritmen kommer alltid att s\u00f6ka p\u00e5 v\u00e4nster sida s\u00e5 l\u00e5ngt den kan f\u00f6rst.  n\u00e4r den n\u00e5r slutet av tr\u00e4det kommer s\u00f6ktr\u00e4det (v\u00e4nster) att slutf\u00f6ras och det kommer att kontrollera den h\u00f6gra sidan.  N\u00e4r b\u00e5da sidor \u00e4r kontrollerade, backar s\u00f6kningen upp en gren och forts\u00e4tter att kontrollera den h\u00f6gra sidan.<\/p>\n
    Om algoritmerna s\u00f6kte igenom hela tr\u00e4det, skulle det g\u00f6ra det i f\u00f6ljande ordning:<\/p>\n
    2, 7, 2, 6, 5, 11, 5, 9 och 4<\/p>\n
    Se om du kan f\u00f6lja med med pseudokoden ovan.<\/p>\n
    <\/span>  Recension av Rekursion<\/span><\/h2>\n
    Rekursion \u00e4r ett avancerat \u00e4mne.  Det kommer att ta lite tid att f\u00f6rst\u00e5 och \u00e4nnu l\u00e4ngre tid att bli bra p\u00e5 att koda det.  Det hj\u00e4lper om du g\u00e5r igenom rekursiva funktioner steg f\u00f6r steg.  Det kan till och med hj\u00e4lpa att stapla registerkort eller post-it-lappar n\u00e4r du g\u00e5r igenom en funktion n\u00e4r du l\u00e4r dig representera varje funktionsanrop.<\/p>\n
    N\u00e4r du skriver en rekursiv funktion, b\u00f6rja med att best\u00e4mma hur du vill avsluta funktionen.  Best\u00e4m sedan hur du st\u00e4ller in din loop.  Identifiera vilken information som beh\u00f6ver skickas till n\u00e4sta funktionsanrop och vad som beh\u00f6ver returneras.<\/p>\n
    Det b\u00e4sta s\u00e4ttet att l\u00e4ra sig rekursion \u00e4r att \u00f6va p\u00e5 det och l\u00e4ra av dina misstag.  Titta p\u00e5 lite av din gamla kod och utmana dig sj\u00e4lv att skriva om loopar som rekursiva funktioner.  Det kommer sannolikt inte att g\u00f6ra din kod mer effektiv, men det kommer att vara bra praxis.<\/p>\n
        Om f\u00f6rfattaren<\/strong><\/p>\n
                Jennifer Seaton (21 artiklar publicerade)
    <\/strong><\/p>\n
    J. Seaton \u00e4r en vetenskapsskribent som specialiserat sig p\u00e5 att bryta ner komplexa \u00e4mnen.  Hon har en doktorsexamen fr\u00e5n University of Saskatchewan;  hennes forskning fokuserade p\u00e5 att anv\u00e4nda spelbaserat l\u00e4rande f\u00f6r att \u00f6ka elevernas engagemang online.  N\u00e4r hon inte arbetar hittar du henne n\u00e4r hon l\u00e4ser, spelar tv-spel eller tr\u00e4dg\u00e5rdsarbete.<\/p>\n
                                Mer fr\u00e5n Jennifer Seaton<\/p>\n
    <\/span>Prenumerera p\u00e5 v\u00e5rt nyhetsbrev<\/span><\/h4>\n
    G\u00e5 med i v\u00e5rt nyhetsbrev f\u00f6r tekniska tips, recensioner, free e-b\u00f6cker och exklusiva erbjudanden!<\/p>\n
    Klicka h\u00e4r f\u00f6r att prenumerera<\/p>\n<\/p><\/div>\n  
    \n
    \n
    Table of Contents<\/p>\nToggle<\/span><\/path><\/svg><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n