Recursjon

Recursjon er en metode der et problem løses ved å dele det inn i mindre ekvivalente underproblemer av samme type. En rekursiv løsning innebærer ofte at en funksjon kaller seg selv. I matematikk og informatikk brukes rekursive definisjoner og algoritmer for å uttrykke og løse problemer som naturlig kan deles opp i liknende delstykker. En rekursiv løsning har vanligvis et grunnleggende tilfelle som avslutter rekursjonen og et rekursivt tilfelle som bringer løsningen nærmere det grunnleggende tilfellet.

Slik fungerer det i praksis: hvert kall produserer et mindre underproblem og avklarer det ved hjelp av et grundig stoppunkt. Grunnleggende tilfelle er forankringen som gir et direkte svar, mens det rekursive tilfellet reduserer problemet til et mindre, som deretter løses av neste kall. Uten et riktig definert grunnleggende tilfelle kan rekursjonen bli uendelig og krasje programmet.

Et enkelt eksempel er faktorielt: f(n) = n × f(n−1) med f(0) = 1. Et annet vanlig eksempel er søk i sorterte tabeller ved å dele problemstillingen i to halvdeler (binary search). Rekursjon brukes også i tretraversering, kombinatorikk og dynamisk programmering.

Ytelse og begrensninger: antallet kall avgjør kjøretiden, og rekursive løsninger kan bruke betydelig stakkplass. Mange språk støtter tail recursion, som kan optimaliseres til en enkel loop, og memoisering som sparer resultater ved å lagre mellomløsninger i dynamiske programmeringsløsninger.

Anvendelse: rekursjon er et sentralt verktøy i algoritmedesign og matematikk, men den må brukes med omtanke på risiko for stack overflow og ineffektivitet ved ineffektive rekursive mønstre. I praksis velges ofte en iterativ tilnærming eller en kombinasjon av rekursjon og memoisering.