Rekursjonen

Rekursjon er en metode der en funksjon eller prosess løser et problem ved å referere til seg selv. I matematikk og informatikk brukes rekursjon ofte når problemet kan deles opp i identiske underproblemer som ligner på originalen. En rekursiv løsning består vanligvis av to deler: en base-case som avslutter rekursjonen, og ett eller flere rekursive kall som bearbeider delproblemene.

Base-case er tilfellet som ikke trenger videre rekursjon, og rekursjonskallet kaller seg selv med en mindre eller enklere input. For at rekursjonen skal avsluttes riktig, må hvert kall bevege problemet mot base-case og til slutt oppfylle avslutningsbetingelsen.

Et klassisk eksempel er fakultet: n! = n × (n−1)! med 0! = 1. En rekursiv implementasjon kan beskrives som: hvis n er 0 returner 1 ellers returner n × fakultet(n−1). Et annet eksempel er Fibonacci-rekken: F(n) = F(n−1) + F(n−2) med F(0) = 0 og F(1) = 1. Begge viser hvordan et større problem kan deles i mindre.

Typer rekursjon inkluderer direkte rekursjon, indirekte rekursjon og mutual rekursjon der to eller flere funksjoner kaller hverandre. Noen språk bruker tail rekursjon, der rekursive kall er den siste operasjonen i funksjonen, noe som i mange språk kan optimaliseres for å spare stackminne.

Bruksområder inkluderer tre- og grafgjennomganger, algoritmer som mergesort og hurtigsort, samt matematiske definisjoner og dynamisk programmering hvor rekursjon ofte kombineres med memoisering for å unngå gjentatte beregninger.