Versionen från 17 december 2020 kl. 17.08

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.

Exempel på en rekursiv algoritm

Algoritmen Intervallhalvering

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ö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.

Nu ska vi använda rekursion som ett koncept inom programmering.

I matematiken realiseras konceptet med s.k. rekursionsformler.

Annat exempel: Fibonacci

Kaniners fortplantning

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

Fibonaccitalen

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

Navigeringsmeny

Logga in

Mönster</b> för bildningen av Fibonaccis talföljd, även kallad Fibonaccitalen:

<b>Summan av två på varandra följande
fibonaccital ger nästa fibonaccital.</b>

</td> <td>\( \qquad\qquad\qquad \)</td> <td>
</td> </tr>
</table>

<b>Fibonaccis rekursionsformel

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

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

Programmet Fibonacci

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.

Körresultat

Läs om rekursion i kursboken på sid 98-100.

@@ Rad 59: / Rad 59: @@
-<big><big><b>Mönster</b> för bildningen av Fibonaccis talföljd, även kallad <b><span style="color:red">Fibonaccitalen</span></b>:</big></big>
+<big><big><b>Mönster</b> för bildningen av Fibonaccis talföljd, även kallad <b><span style="color:red">Fibonaccitalen</span>:</b></big></big>
 <table>
-<tr> <td><div class="border-divblue">
+<tr> <td>Mönster</b> för bildningen av Fibonaccis talföljd, även kallad <b><span style="color:red">Fibonaccitalen</span>:<div class="border-divblue">
 <big><b>Summan av två på varandra följande <br> fibonaccital ger nästa fibonaccital.</b></big>
 </div></td> <td><math> \qquad\qquad\qquad </math></td> <td><div style="border:1px solid black;display:inline-table;margin-left: 0px;">[[Image: FibonacciBilda.jpg]]</div></td> </tr>

Skillnad mellan versioner av "1.10 Rekursion"