Rekursion

I det förra avsnittet repeterade vi vad en talföljd är och hur vi kan beräkna värdet på ett visst element i en talföljd, samt summan av elementen i vissa typer av talföljder.

I det här avsnittet ska vi introducera begreppet rekursion. Vi kan använda rekursion för att beräkna värdet på ett visst element i en talföljd, utifrån information om värdet på tidigare beräknade element i talföljden.

Rekursion

Vi vet från avsnittet om talföljder att värdet på det n:te elementet i en aritmetisk talföljd kan beräknas med den allmänna formeln

$${a}_{n}={a}_{1}+(n-1)\cdot d$$

där an är värdet på det n:te elementet i talföljden, a1 är värdet på det första elementet i talföljden, och d är differensen mellan värdet på ett element och det närmast föregående elementet i talföljden.

Till exempel kan värdet på det n:te elementet i talföljden

$$3,\,5,\,7,\,9,\,11,\,...$$

beräknas med formeln

$$ {a}_{n}=3+(n-1)\cdot 2=$$

$$=3+2n-2=$$

$$=2n+1$$

för alla n ≥ 1.

Detta är ett exempel på en sluten formel (kallas även direkt formel eller explicit formel). Med en sluten formel kan vi direkt beräkna värdet på det n:te elementet i en talföljd.

Men det finns även en annan typ av formel som vi kan använda för att beräkna värdet på det n:te elementet i talföljden ovan: en rekursiv formel.

När vi använder oss av en rekursiv formel beräknar vi värdet på det n:te elementet i en talföljd genom att använda information om de föregående elementen i talföljden. Därigenom beräknar vi värdet på elementen successivt snarare än i godtycklig ordning.

För aritmetiska och geometriska talföljder fungerar det ofta utmärkt att beräkna värdet på elementen med hjälp av en sluten formel, men vi kan även använda oss av en rekursiv formel i dessa fall.

I fallet med aritmetiska talföljder får vi då med en rekursiv formel värdet på det n:te elementet (n > 1) genom att addera en viss term (differensen d, som vi tidigare använt) till det (n-1):te elementets värde (värdet på det första elementet i talföljden förutsätts vara känt):

$${a}_{n}={a}_{n-1}+d$$

I exemplet med talföljden

$$3,\,5,\,7,\,9,\,11,\,...$$

kan vi därför beräkna värdet på det n:te elementet med följande rekursiva formel:

$$\begin{cases} & {a}_{1}=3 \\ & {a}_{n}={a}_{n-1}+2,\,\, \text{ om } n>1 \end{cases}$$

Detta tolkar vi som att om n = 1, då har elementet värdet 3. Om n > 1, då har elementet värdet av det föregående elementet plus 2.

I fallet med geometriska talföljder får vi med en rekursiv formel värdet på det n:te elementet (n > 1) genom att multiplicera en viss faktor (värdet k, som vi tidigare använt) med det (n-1):te elementets värde (även i detta fall förutsätts värdet på det första elementet i talföljden, a1, vara känt):

$${a}_{n}=k\cdot {a}_{n-1}$$

I exemplet med talföljden

$$9,\,-3,\,1,\,-\frac{1}{3},\,\frac{1}{9},\,...$$

kan vi därför beräkna värdet på det n:te elementet med följande rekursiva formel:

$$\begin{cases} & {a}_{1}=9 \\ & {a}_{n}=\left (-\frac{1}{3}  \right )\cdot {a}_{n-1},\,\, \text{ om } n>1 \end{cases}$$

Detta tolkar vi som att om n = 1, då har elementet värdet 9. Om n > 1, då har elementet värdet som bildas av faktorn -1/3 multiplicerad med det föregående elementets värde.

När vi har att göra med aritmetiska eller geometriska talföljder kan vi alltså välja vilken typ av formel vi använder oss av när vi beräknar värdet på det n:te elementet - en sluten formel eller en rekursiv formel. Dock finns det vissa typer av talföljder där en rekursiv formel blir betydligt enklare att formulera än en sluten formel för att beräkna värdet på det n:te elementet. Ett välkänt exempel på en sådan talföljd är Fibonaccis talföljd, som vi ska bekanta oss med härnäst.

Fibonaccis talföljd

Den medeltida italienska matematikern Fibonacci har gett namn till en talföljd där värdet på ett element beräknas som summan av värdena på de två föregående elementen (med undantag för värdena på de två första elementen i talföljden, som båda har värdet 1).

Värdet på det n:te elementet i Fibonaccis talföljd kan därför beräknas med följande rekursiva formel:

$$\begin{cases} & {a}_{1}=1 \\ & {a}_{2}=1 \\ & {a}_{n}={a}_{n-1}+{a}_{n-2},\,\, \text{ om } n>2 \end{cases}$$

Den här definitionen ger upphov till en talföljd vars tio inledande element är

$$1,\,1,\,2,\,3,\,5,\,8,\,13,\,21,\,34,\,55,\,...$$

Beräknar vi värdena på elementen successivt får vi följande värden med hjälp av den rekursiva formeln ovan:

$$ {a}_{1}=1$$

$$ {a}_{2}=1$$

$$ {a}_{3}={a}_{2}+{a}_{1}=1+1=2$$

$$ {a}_{4}={a}_{3}+{a}_{2}=2+1=3$$

$$ {a}_{5}={a}_{4}+{a}_{3}=3+2=5$$

$$ ...$$

$$ {a}_{n}={a}_{n-1}+{a}_{n-2}$$

Fibonaccitalen har visat sig vara nära förknippade med det gyllene snittet, och många biologiska fenomen uppvisar egenskaper som har en motsvarighet i talen i Fibonaccis talföljd, t.ex. i de spiralmönster som kan uppkomma hos växter.

Har du en fråga du vill ställa om Rekursion? Ställ den på Pluggakuten.se
Har du hittat ett fel, eller har du kommentarer till materialet på den här sidan? Mejla matteboken@mattecentrum.se
Läs sidan på andra språk

Här går vi igenom rekursion

  • Sluten formel: Med en sluten formel kan vi direkt beräkna värdet på det n:te elementet i en talföljd.
  • Rekursiv formel: beräknar värdet på det n:te elementet i en talföljd genom att använda information om de föregående elementen i talföljden. Därigenom beräknar vi värdet på elementen successivt snarare än i godtycklig ordning.
  • Fibonaccis talföljd: en känd talföljd med många verkliga tillämpningar som vi kan beräkna med följande rekursiva formel:

    $$\begin{cases} & {a}_{1}=1 \\ & {a}_{2}=1 \\ & {a}_{n}={a}_{n-1}+{a}_{n-2},\,\, \text{ om } n>2 \end{cases}$$

    Den här definitionen ger upphov till en talföljd vars tio inledande element är

    $$1,\,1,\,2,\,3,\,5,\,8,\,13,\,21,\,34,\,55,\,...$$