Rekursiv algoritm

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

En rekursiv algoritm anropar/använder sig själv.

Ett exempel på detta är beräkning av fakultet. Eftersom 7! är detsamma som 7·6! och 6! är detsamma som 6·5! kan man göra en rekursiv funktion så här:

 FUNCTION FAK(X)
    IF X=0 THEN
       FAK=1            
    ELSE
       FAK=X*FAK(X-1)
    END IF
 END FUNCTION

Raden FAK=1 är ett bassteg där funktionen kommer att sluta. Utan det kommer rekursionen inte ha något slut. Ett problem med rekursiva funktioner är att de kan fylla upp minnet vid långa körningar, beroende på implementation. Ett sätt att lösa det är genom svansrekursion, eller genom att skriva den rekursiva funktionen som en loop med ackumulator.