Rekursion

Från Unix.se, den fria unixresursen.

I programmeringssammanhang att en funktion som anropar sig själv. Vanligt i funktionell programmering, och medför ofta mer överskådlig kod.

En funktion som använder rekursion kallas rekursiv.

Exempel

Rekursivt exempel i O'Caml:

let rec mylen = function
    [] -> 0
  | x::xs -> 1 + mylen xs
;;

Förklaring: Funktionen mylen tar emot en lista som argument. Om listan är tom returnerar mylen värdet 0 (noll). Annars returnerar den 1 plus mylen av listan förutom det första elementet. Dvs. om listan ser ut som följande: [1;2;3] så kommer mylen först matcha x::xs, och returnera 1 + mylen xs, där xs alltså är resten av listan ([2;3]). Därefter kommer mylen att returnera 1 + mylen [3]. Till slut kommer mylen att stöta på en tom lista, och sluta anropa sig själv och istället returnera värdet 0 (noll). Det medför att det första anropet returnerar 1 + 1 + 1 + 0 = 3. Tada! (Uh, det blev en lite virrig förklaring...)

Se även

Personliga verktyg