Skillnad mellan versioner av "1.10 Rekursion"
Taifun (Diskussion | bidrag) m |
Taifun (Diskussion | bidrag) m |
||
| (2 mellanliggande versioner av samma användare visas inte) | |||
| Rad 2: | Rad 2: | ||
{| border="0" cellspacing="0" cellpadding="0" height="30" width="100%" | {| border="0" cellspacing="0" cellpadding="0" height="30" width="100%" | ||
| style="border-bottom:1px solid #797979" width="5px" | | | style="border-bottom:1px solid #797979" width="5px" | | ||
| − | + | {{Not selected tab|[[Lektion 16 (Python)| << Lektion 16]]}} | |
| − | {{Not selected tab|[[Lektion 18 (DigSkap)| << Lektion 18]]}} | + | <!-- {{Not selected tab|[[Lektion 18 (DigSkap)| << Lektion 18]]}} --> |
{{Selected tab|[[1.10 Rekursion|Genomgång]]}} | {{Selected tab|[[1.10 Rekursion|Genomgång]]}} | ||
| − | + | {{Not selected tab|[[Övningar 16 (Python)|Övningar]]}} | |
| − | {{Not selected tab|[[Övningar 18 (DigSkap)|Övningar]]}} | + | <!-- {{Not selected tab|[[Övningar 18 (DigSkap)|Övningar]]}} --> |
| style="border-bottom:1px solid #797979" width="100%"| | | style="border-bottom:1px solid #797979" width="100%"| | ||
|} | |} | ||
| Rad 40: | Rad 40: | ||
<div style="border:1px solid black;display:inline-table;margin-left: 0px;"> [[Image: Gissa_tal_Korex.jpg]]</div> | <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 | + | <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>]]. | 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>]]. | ||
| Rad 134: | Rad 136: | ||
| − | [[Matte:Copyrights|Copyright]] © 2021 [https://www.techpages.se | + | [[Matte:Copyrights|Copyright]] © 2021 [https://www.techpages.se <span style="color:blue">TechPages AB</span></b>]. All Rights Reserved. |
Nuvarande version från 13 december 2021 kl. 10.17
| << 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ö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.
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 två på varandra följande |
\( \qquad\qquad\qquad \) |  |
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 © 2021 TechPages AB. All Rights Reserved.
