Rekursive algoritmer

En rekursiv algoritme er en metode, hvor et problem løses ved at henvise til en mindre udgave af sig selv. Idéen svarer til rekursive definitioner i matematik: vi starter med en basis, og derefter følger et rekursivt skridt, som gentager algoritmen på en enklere del af problemet.

 

 

Fra definition til kode

Når vi har en rekursiv definition, kan den ofte oversættes direkte til en algoritme. Man skal blot oversætte:

 

• Basis: hvornår algoritmen kan stoppe.
• Rekursivt skridt: hvordan problemet reduceres og algoritmen kalder sig selv.

 

 

Eksempel: Fakultet

Fakultetsfunktionen er defineret rekursivt som

 

$$ \large 0! = 1 $$

$$ \large n! = n \cdot (n-1)!, \quad n \geq 1 $$

 

Dette kan skrives som en algoritme i pseudokode:

 

function factorial(n):
    if n = 0:
        return 1        // basis
    else:
        return n * factorial(n - 1)   // rekursivt skridt

 

 

Algoritmen stopper når \( \large n = 0 \), ellers kalder den sig selv med et mindre tal. Til sidst foldes alle kald tilbage til resultatet.

 

 

Eksempel: Maksimum i en liste

Vi kan også definere en algoritme rekursivt for at finde det største tal i en liste:

 

• Basis: Hvis listen kun har ét element, er dette element maksimum.
• Rekursivt skridt: Sammenlign det første element med maksimum i resten af listen.

 

 

function max(list):
    if list has length 1:
        return list[0]            // basis
    else:
        m = max(rest of list)     // rekursivt skridt
        return the larger of list[0] and m

 

 

Eksempel i praksis

 

Hvis vi har listen \( \large [7, 2, 9, 4] \):

max([7,2,9,4])

= larger of 7 and max([2,9,4])

= larger of 7 and larger of 2 and max([9,4])

= larger of 7 and larger of 2 and larger of 9 and max([4])

= larger of 7 and larger of 2 and larger of 9 and 4

= larger of 7 and larger of 2 and 9

= larger of 7 and 9

= 9

 

 

Opsummering

En rekursiv algoritme oversætter idéen bag en rekursiv definition til kode. Først angives et basis-tilfælde, hvor algoritmen stopper. Derefter beskrives et rekursivt skridt, hvor algoritmen kalder sig selv på et enklere problem. Dette mønster går igen i mange kendte algoritmer, som sortering, søgning og behandling af datastrukturer.