Rekursio


Rekursio on matemaattinen keino määritellä funktioita niin, että funktion arvo tietyssä pisteessä riippuu funktion arvosta edellisessä pisteessä. Rekursioyhtälö annetaan yleensä kaksiosaisena: toinen osa määrittelee funktion arvon jollain tunnetulla alkuarvolla (alkuarvoja voi olla myös useita) ja toinen osa muulloin. Esimerkiksi kertoma on helppo määritellä luonnollisille luvuille rekursiivisesti seuraavaan tapaan:

\({\displaystyle f(n)=\left\{{\begin{matrix}1,&{\mbox{jos }}n{\mbox{ = 0}}\\n\cdot f(n-1)&{\mbox{muulloin}}\end{matrix}}\right.}\)

Rekursioyhtälöllä tarkoitetaan yhtälöä, jossa annetun funktion arvo voidaan laskea käyttäen hyväksi sen edellisissä pisteissä saamia arvoja. Esimerkkinä rekursioyhtälöstä on Fibonaccin jono

\({\displaystyle F_{1}=F_{2}=1}\)
\({\displaystyle F_{n}=F_{n-2}+F_{n-1}}\) kun n > 2.

Sisällysluettelo

Rekursio tietotekniikassa/tietojenkäsittelytieteessä


Pääartikkeli: Rekursiivinen algoritmi

Myös tietotekniikassa käytetään rekursiivisia ohjelmarutiineja. Niissä idea on sama kuin matemaattisesti määritellyissä rekursiivisissa funktioissa, ja rekursiivisesti lasketut välitulokset tallennetaan useimmiten pinoon. Viimeisellä rekursiokierroksella pinosta kerätään vastaukset käänteisessä järjestyksessä. Pseudokoodina kertoma voitaisiin laskea seuraavaan tapaan:

 procedure factorial(integer n):
   if n < 2
     return 1
   else
     return n * factorial(n-1)

Yleinen ohjelmointivirhe on niin sanottu ikuinen silmukka, jossa funktiokutsu ei koskaan palaa vaan etenee yhä toistuvasti saman funktion kautta rekursiivisesti kiertäen. Pino on välttämätön rekursiivisten aliohjelmien toteuttamiseen, mutta pinolla on myös rajattu koko: useissa ohjelmointikielissä rajaamaton rekursio voi aiheuttaa pinon ylivuodon (engl. stack overflow). Rekursio voi olla hitaampaa ja vaatia enemmän muistia kuin toistorakenteen käyttö.[1]

Mikäli ohjelmakoodin rekursiivinen osa on niin sanottu häntärekursio, voidaan rekursio muuttaa tavalliseksi silmukaksi.

Erityisesti Lisp-ohjelmointikielessä rekursion käyttäminen on yleistä.

Hanoin torni

Pääartikkeli: Hanoin torni

Hanoin torni -ongelma voidaan ratkaista yksinkertaisella tavalla rekursion avulla. Esimerkki Perl-skriptistä, jolle annetaan parametrina levyjen lukumäärä. Ohjelma palauttaa siirto siirrolta, missä tangossa olevaa levyä on liikuteltava.

#!/usr/bin/perl
#sub hanoi
{
       if($_[0] == 1)
       {
               print "@{[A,B,C]}[$_[1]-1] => @{[A,B,C]}[$_[2]-1]" . "\n";
       }
       elsif($_[0] > 1)
       {
               hanoi($_[0]-1, $_[1], 6-$_[1]-$_[2]);
               hanoi(1, $_[1], $_[2]);
               hanoi($_[0]-1, 6-$_[1]-$_[2], $_[2]);
       }
       else {}
}if($ARGV[0] > 0)
{
       hanoi $ARGV[0], 1, 3;
}

Sama algoritmi Haskellilla:

hanoi :: Integer -> a -> a -> a -> [(a, a)]
hanoi 0 _ _ _ = []
hanoi n p q r = hanoi (n-1) p r q ++ [(p,q)] ++ hanoi (n-1) r q p

Labyrintti


Kaksiulotteisen labyrintin polun selvittäminen on yksinkertaista ratkaista rekursiolla. Ajatellaan vaikkapa seuraavaa sokkeloa:

  Alku -> XXXXX..XXX
          .X..X..X..
          .X..X.XXX.
          .X..X.X.X.
          XX..XXX.XX
          X..XX.X..X
          X.....XX.X
          XXXXX.X...
          X..XX.XX..
          XXXX...XXX <- Loppu

Seuraava Perl-skripti ratkaisee polun koordinaatit:

#!/usr/bin/perl
#@laby = (
[1,1,1,1,1,0,0,1,1,1],
[0,1,0,0,1,0,0,1,0,0],
[0,1,0,0,1,0,1,1,1,0],
[0,1,0,0,1,0,1,0,1,0],
[1,1,0,0,1,1,1,0,1,1],
[1,0,0,1,1,0,1,0,0,1],
[1,0,0,0,0,0,1,1,0,1],
[1,1,1,1,1,0,1,0,0,0],
[1,0,0,1,1,0,1,1,0,0],
[1,1,1,1,0,0,0,1,1,1]);@polku = ();sub minotaurus($$)
{
        if($_[0]<0 or $_[0]>9 or $_[1]<0 or $_[1]>9)
        {
                return 0;
        }
        elsif($laby[$_[0]][$_[1]] != 1)
        {
                return 0;
        }
        else
        {
                $laby[$_[0]][$_[1]] = 2;
                if($_[0] == 9 and $_[1] == 9)
                {
                        unshift @polku, "-> ($_[1],$_[0])";
                        return 1;
                }
                if(     minotaurus($_[0]+1, $_[1])
                or      minotaurus($_[0]-1, $_[1])
                or      minotaurus($_[0], $_[1]+1)
                or      minotaurus($_[0], $_[1]-1))
                {
                        unshift @polku, "-> ($_[1],$_[0])";
                        return 1;
                }
                return 0;
        }
}minotaurus 0, 0;
$polku[0] =~ s/^-> // if defined $polku[0];
print "@polku\n";

Ajettaessa tulostuu: (0,0) -> (1,0) -> (2,0) -> (3,0) -> (4,0) -> (4,1) -> (4,2) -> (4,3) -> (4,4) -> (5,4) -> (6,4) -> (6,5) -> (6,6) -> (6,7) -> (6,8) -> (7,8) -> (7,9) -> (8,9) -> (9,9).

Lähteet


Aiheesta muualla











Luokat: Matemaattinen logiikka | Tietojenkäsittelyteoria | Ohjelmointi




Tiedot vuodesta: 30.11.2020 07:32:48 CET

Lähde: Wikipedia (Tekijät [Historia])    Lisenssi: CC-BY-SA-3.0

Muutokset: Kaikki kuvat ja suurin osa niihin liittyvistä sisustuselementeistä poistettiin. Jotkut kuvakkeet korvattiin FontAwesome-kuvakkeilla. Jotkut mallit poistettiin (kuten ”artikkeli tarvitsee laajennusta”) tai osoitettiin (kuten ”viittaukset”). CSS-luokat joko poistettiin tai yhdenmukaistettiin.
Wikipediakohtaiset linkit, jotka eivät johda artikkeliin tai luokkaan (kuten ”Punaiset linkit”, “linkit muokkaussivulle”, “linkit portaaliin”) poistettiin. Jokaisella ulkoisella linkillä on lisäksi FontAwesome-kuvake. Joidenkin pienten suunnittelumuutosten lisäksi media-säilö, kartat, navigointiruudut, puhutut versiot ja geomikroformaatit poistettiin.

Huomaa: Koska annettu sisältö otetaan automaattisesti Wikipediasta tiettynä ajankohtana, manuaalinen tarkistaminen oli eikä ole mahdollista. Siksi LinkFang.org ei takaa hankitun sisällön paikkansapitävyyttä ja todellisuutta. Jos tiedossa on tällä hetkellä vääriä tietoja tai siinä on virheellinen näyttö, ota rohkeasti yhteyttä ota meihin yhteyttä: sähköposti.
Katso myös: Valmistusmerkintä & Tietosuojakäytäntö.