Versionen från 13 december 2021 kl. 10.14

Genomgång

Vad är rekursion?

Ordet rekursion kommer från det latinska recurrere som betyder att köra igen. Dvs:

Man återvänder till något som man redan gjort en gång och upprepar ett känt förlopp, kanske under andra förutsättningar.

Rekursion är ett koncept som används i problemlösning genom successiv upprepning.

Hittills har vi realiserat upprepning i programmering med loopar. Rekursion är ett alternativ till loopar.

Optimal strategi för att med så få försök som möjligt gissa rätt i Gissa tal-spelet.

Körexempel på Gissa tal-spelet där algoritmen Intervallhalvering använts:

Rekursion används här som ett koncept för prblemlösning:

Hur gör jag för att med så få försök som möjligt gissa rätt i Gissa tal-spelet? Jag upprepar intervallhalvering.

Nu ska vi använda rekursion som ett koncept inom programmering, se Programmet Fibonacci.

I matematiken realiseras konceptet med s.k. rekursionsformler, se Fibonaccis rekursionsformel.

Följer man Fibonaccis instruktioner för kaniners fortplantning får man följande siffror:

Mönster för bildningen av Fibonaccis talföljd,

även kallad Fibonaccitalen:

Summan av två på varandra följande
fibonaccital ger nästa fibonaccital.

\( \qquad\qquad\qquad \)

Mer utförligt om om Fibonacciproblemet kan du läsa här.

Fibonaccis rekursionsformel kan direkt tas över till följande pythonprogram:

I Python kan Fibonaccis rekursionsformel kodas som en rekursiv funktion fib().

En funktion kallas för rekursiv om den anropar sig själv i sin egen definition.

Funktionen fib() anropar sig själv två gånger i sin definition på rad 9: rekursiva anrop!

Anropet på rad 14 är ett vanligt (inte rekursivt) funktionsanrop i huvudprogrammet.

@@ Rad 40: / Rad 40: @@
 <div style="border:1px solid black;display:inline-table;margin-left: 0px;"> [[Image: Gissa_tal_Korex.jpg]]</div>
-<big>Rekursion används här som ett koncept för prblemlösnig: Hur gör jag för att med så få försök som möjligt gissa rätt i Gissa tal-spelet? Jag upprepar intervallhalvering.
+<big>Rekursion används här som ett koncept för prblemlösning:
+Hur gör jag för att med så få försök som möjligt gissa rätt i Gissa tal-spelet? Jag upprepar intervallhalvering.
 Nu ska vi använda rekursion som ett koncept inom programmering, se [[1.10_Rekursion#Programmet_Fibonacci|<b><span style="color:blue">Programmet Fibonacci</span></b>]].