Skillnad mellan versioner av "1.10 Rekursion"
Taifun (Diskussion | bidrag) |
Taifun (Diskussion | bidrag) m |
||
| Rad 49: | Rad 49: | ||
= <b><span style="color:#931136">Annat exempel: Fibonacci</span></b> = | = <b><span style="color:#931136">Annat exempel: Fibonacci</span></b> = | ||
<div class="ovnA"> | <div class="ovnA"> | ||
| − | == <b><span style="color:#931136">Kaniners fortplantning</span></b | + | == <b><span style="color:#931136">Kaniners fortplantning</span></b> == |
<div style="border:1px solid black;display:inline-table;margin-left: 0px;"> [[Image: Fibonacciproblemet.jpg]]</div> | <div style="border:1px solid black;display:inline-table;margin-left: 0px;"> [[Image: Fibonacciproblemet.jpg]]</div> | ||
| Rad 60: | Rad 60: | ||
<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> | ||
| − | |||
<div class="border-divblue"> | <div class="border-divblue"> | ||
<big><b>Summan av av två på varandra följande fibonaccital ger nästa fibonaccital.</b></big> | <big><b>Summan av av två på varandra följande fibonaccital ger nästa fibonaccital.</b></big> | ||
</div> | </div> | ||
| − | </div> | + | </div><math> \qquad\qquad\qquad </math> <div style="border:1px solid black;display:inline-table;margin-left: 0px;"> [[Image: FibonacciBilda.jpg]]</div> |
Versionen från 17 december 2020 kl. 16.42
| << Lektion 16 | Genomgång | Övningar |
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:
Summan av av två på varandra följande fibonaccital ger nästa fibonaccital.
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.
Copyright © 2020 TechPages AB. All Rights Reserved.
