Alle fag › Videregående programmering › Rekursjon

Rekursjon

En rekursiv funksjon kaller seg selv med et mindre problem, og trenger et basistilfelle som stopper kjedet av kall. Uten basistilfelle ender funksjonen i RecursionError fordi kallene aldri tar slutt.

f(n)=n⋅f(n−1),  f(1)=1f(n) = n\cdot f(n-1),\ \ f(1) = 1fakultet: rekursivt trinn og basistilfelle

Symboler

nnproblemstørrelsen

Eksempel

def fak(n):

if n <= 1: return 1

return n * fak(n - 1)

fak(3) gir 3⋅2⋅1=63\cdot 2\cdot 1 = 6.

Skriv alltid basistilfellet først — det er det som garanterer at rekursjonen faktisk stopper.
Øv på algoritmer og datastrukturer gratis →

← Tidskompleksitet, O-notasjon · Stakk og kø →

Del av Videregående programmering: Algoritmer og datastrukturer.