Rekursio

Wikipedia

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

F₁ = F₂ = 1

F_n = F_{n − 2} + F_{n − 1} kun n > 2.

[muokkaa] Rekursio tietotekniikassa/tietojenkäsittelytieteessä

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.

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ä.

[muokkaa] 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;
}

[muokkaa] 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";

Ajattaessa 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).

[muokkaa] Katso myös

• Rekursioyhtälö

Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.