Begynder rekursion

Rekursion vil måske ved første øjekast ligne et komplekst begreb, men i virkeligheden er det meget simpelt. Denne artikel har til formål at illustrere dette gennem to simple rekursive funktioner: fakultet og exponentialfunktionen. Inden da: hvad er rekursion?

Rekursion er for matematikere en funktion eller procedure, der gentagende kalder sig selv indtil en bestemt betingelse er opnået.

Lad os straks se på et par eksempler.

Fakultetfunktionen er normalt defineret som F(n) = n*(n-1)*(n-2)...2*1, hvis n er et positivt heltal og F(n) = 1, hvis n=0. Sagt i ord er F(n) det samme som produktet af de første n positive heltal og pr. defination er F(0) = 1.

Ovenstående har ikke noget med rekursion at gøre, men hvad nu hvis vi vælger at definere fakultetfunktionen som F(n) = n * F(n-1) for n>0 og F(0) = 1? - Sagt i ord er F(n) det samme som n gange fakultetfunktionen for n-1, dvs. n gange produktet af de første n-1 positive heltal.
Begge definitioner leder frem til identiske funktioner, men den sidste funktion er altså rekursiv fordi den refererer til sig selv. F bliver ved med at kalde sig selv indtil tallet givet til funktion er nul. Når dette sker, så stopper funktionen med at kalde sig selv da løsningen F(0) = 1 på forhånd er givet og skal derfor ikke beregnes. Værdien for det sidste funktionskald F(0) bliver sendt tilbage til den kaldende funktion F(1). Denne funktion udregner så en værdi og sender den tilbage til den forrige kaldende funktion F(2), og så videre, og så videre.
For at lave denne rekursive procedure, er vi nødt til at bryde ligningen ned i tre stykker som eksisterer. Først, F(n) som kun tager en Integer parameter og returnerer en ditto. Det betyder at vores funktionserklæring kommer til at se ud som nedenstående:

function Faktultet(num: integer): integer;

Næste skridt er et specialtilfælde. Det er når F(0) er nået. For at håndtere dette, er vi nødt til at tilføje en betingelse til håndtering af dette, som ser således ud:

if num = 0 then
  result := 1
else
  ....

Til sidst er vi nødt til at tage højde for hvad F(n) er lig med, hvilket vi definerede til at være n * F(n-1). Det kommer til at se ud som følger:

result := num * Faktultet(num - 1);

Når vi samler det hele, får I en funktion som den her:

function Faktultet(num: integer): integer;
begin
  if num = 0 then
    result := 1
  else
    result := num * Fakultet(num - 1);
end;

Lad os prøve denne funktion med en værdi. Vi vil "spore" eksekveringen af Fakultet(6).

Fakultet(6) = 6 * Fakultet(5)
  Fakultet(5) = 5 * Fakultet(4)
    Fakultet(4) = 4 * Fakultet(3)
      Fakultet(3) = 3 * Fakultet(2)
        Fakultet(2) = 2 * Fakultet(1)
          Fakultet(1) = 1 * Fakultet(0)
            Fakultet(0) = 1
          Fakultet(1) = 1 * 1
        Fakultet(2) = 2 * 1
      Fakultet(3) = 3 * 2
    Fakultet(4) = 4 * 6
  Fakultet(5) = 5 * 24
Fakultet(6) = 6 * 120
= 720

Voila! Nu har vi en simpel rekursiv funktion, der kan beregne Fakultet af et tal. En ting du er nødt til at sikre dig inden du kommer ind i funktionen er hvorvidt tallet er størrere end eller lig med 0. Dette kunne være et simpelt tjek inden funktionen bliver kaldt.

Lad os nu prøve at lave en rekursiv funktion til at beregne B^n. Besvar de tre følgende funktioner: Hvor mange tal skal vi medgive til funktionen (parametre). Hvor mange skal vi have tilbage?
Er der nogen specialtilfælde?
Hvilken rekursiv ligning skal bruges for at beregne B^n?
Først, hvor mange tal skal vi give til funktionen? - Svaret er to: Basen og eksponenten.
Hvor mange tal skal vi have tilbage? - Vi behøver kun et tal tilbage som resultat af B^n.
Hvordan kommer funktionserklæring til at se ud?

Noget som det her:

function Exp(Base, Eksponent: integer): integer;

For det andet, er der nogen specialtilfælde? Ja det er der. Der er en anden numerisk konstant som vi skal basere vores funktion på: n^0 = 1. Så hvis eksponenten er nul, så skal resultatet være én. Det vil ligne specialtilfældet fra fakultetfunktionen meget:

if Eksponent = 0 then
  result := 1
else
  ....

Til sidst, hvad er den rekursive funktion til at beregne B^n? Den rekursive funktion til at beregne B^n er B^n = B * B^(n - 1). Igen implementering af dette kommer til at ligne beregningen i fakultetfunktionen:

result := Base * Exp(Base, Eksponent - 1);

Når så vi samler det hele får vi:

function Exp(Base, Eksponent: integer): integer;
begin
  if Eksponent = 0 then
    result := 1
  else
    result := Base * Exp(Base, Eksponent - 1);
end;

Igen lad os "spore" eksekveringen af Exp(3, 4).

Exp(3, 4) = 3 * Exp(3, 3)
  Exp(3, 3) = 3 * Exp(3, 2)
    Exp(3, 2) = 3 * Exp(3, 1)
      Exp(3, 1) = 3 * Exp(3, 0)
        Exp(3, 0) = 1
      Exp(3, 1) = 3 * 1
    Exp(3, 2) = 3 * 3
  Exp(3, 3) = 3 * 9
Exp(3, 4) = 3 * 27
= 81

Vi vil nu gribe rekursion lidt mere abstrakt an ved at introducere en værdifuld programmeringsteknik, der hedder rekursiv programmering. Det er kort fortalt en teknik, der har til formål at opdele et ikke-trivielt problem P i mindre trivielle delproblemer, hvis løsninger kan samles til en løsning for P.

Antag f.eks. at P er af en vis kompleksitet. Ideen er at opdele P i to delproblemer P1 og P2, som hver især har simplere løsninger benævnt ved L1 og L2. Når L1 og L2 er blevet bestemt så kombineres de til en løsning L for problemet P, som hermed er blevet løst. Dette kaldes ofte for Del-Løs-Kombiner/Divide-and-conquer princippet (DLK), hvilket kommentarerne i nedenstående pseudkode også antyder:

function Solve(p: Problem): Løsning;
var
  p1, p2: Problem;
  l1, l2: Løsning;
begin
  if p er simpel then
    result := den simple løsning for p;
  else
    begin
      // DEL
      Opdel p i delproblemer p1 og p2;

      // LØS
      l1 := Solve(p1);
      l2 := Solve(p2);

      // KOMBINER
      Kombiner l1 og l2 til l;
      result := l;
    end;
end;

Bemærk at koden er opdelt to tilfælde: "er p simpel eller ej?". Dette skyldes at enhver rekursiv funktion udover den rekursive definition også skal have et eller flere specialtilfælde, hvor løsningen er givet direkte da et evt. funktionskald ellers vil fortsætte ud i det uendelige. Hvis vi for fakultetfunktionens vedkommende f.eks. fjerner konventionen om at F(0) = 1, så vil F(0) kalde F(-1) som vil kalde F(-2) som vil kalde F(-3) osv. ud i det uendelige, hvilket kaldes for uendelig rekursion. En rekursiv funktion består derfor altid af en rekursiv definition (rekurensreglen) samt en termineringsregel, som sikrer at funktionen stopper på eller andet tidspunkt. Tag atter engang et kig på eksemplerne og se, hvordan de passer ind i skabelonen.

Som du kan se skal du kun bruge nogle få linjers kode til at lave en kraftfuld funktion, selvom det det ligner noget kompliceret skidt at håndtere, er det det ikke. Disse to eksempler med rekursion hører til blandt de simpleste rekursive funktioner. Mere komplicerede eksempler på brugen af rekursion er sortering og søgning. Disse to emner er at betragte som basal programmeringsviden/kunnen og vil derfor være en naturligt at studere i forlængelse af denne artikel. Enkelt - og dobbelt-kædet lister samt træer hører til blandt de mere komplicerede emner som kræver en god baggrundsviden om rekursion.