Versionen från 17 december 2020 kl. 14.29

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 detta i programmering med loopar. Rekursion erätter 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:

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

Mönster för bildningen av Fibonaccis talföljd, kallad kort Fibonaccitalen:

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

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 19: / Rad 19: @@
 Rekursion är ett koncept som används i problemlösning genom <b><span style="color:red">successiv upprepning</span></b>.
+Hittills har vi realiserat detta i programmering med loopar. Rekursion erätter loopar.
 </big></big>
 </div>