Rekursio

Kohteesta Wikipedia
Loikkaa: valikkoon, hakuun

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:

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

kun n > 2.

Rekursio tietotekniikassa/tietojenkäsittelytieteessä[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]