Rekursiv algoritm

En rekursiv algoritm anropar sig själv. Ett exempel på ett sådant anrop är en funktion för beräkning av fakultet.

n! = n·(n - 1)! = n·(n - 1)·(n - 2)! = ... ,

Då kan algoritmen skrivas som en rekursiv funktion,

function fakultet (n)

if n = 0 then

fakultet = 1     -- bassteg/terminerande anrop

else

fakultet = n · fakultet (n - 1)     -- rekursivt anrop

end if

end function

Raden fakultet = 1 är ett bassteg som terminerar anropskedjan vilket är nödvändigt för att undvika en oändlig följd av anrop. Ett problem med rekursiva funktioner är att de kan uppta för stor del av datorns minne genom för långa anropskedjor. Ett sätt att lösa detta är genom svansrekursion, eller genom att skriva den rekursiva funktionen som en slinga med ackumulator.

De rekursiva fallens/stegens utförda arbete kan ses som sätt att bryta ner komplexa ingångsvärden till enklare sådana. I en rätt utformad rekursiv algoritm måste med varje rekursivt steg det ingående problemet förenklas på ett sådant sätt att basfallen till slut uppnås. Underlåtenhet att skriva ett basfall, eller att felaktigt testa för basfallet, kan orsaka en oändlig anropskedja.