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:

$f(n)=\{\begin{array}{cc}1,& \text{jos }n\text{ = 0}\\ n\cdot f(n-1)& \text{muulloin}\end{array}$

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_1=F_2=1$

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

Rekursio tietotekniikassa/tietojenkäsittelytieteessä

Malline:Pääartikkeli 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ä. C-kielellä kertoma voitaisiin laskea seuraavaan tapaan:

unsigned int factorial(unsigned int n) {
    if (n == 0) {
        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 ylivuotovirheen (Malline:K-en). Rekursio voi olla hitaampaa ja vaatia enemmän muistia kuin toistorakenteen käyttö.

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

Malline:Pääartikkeli 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).