Rekursiv algoritm

Från Wikipedia
Hoppa till: navigering, sök

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

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

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