Skillnad mellan versioner av "1.10 Rekursion"
Taifun (Diskussion | bidrag) m |
Taifun (Diskussion | bidrag) m |
||
| (24 mellanliggande versioner av samma användare visas inte) | |||
| Rad 3: | Rad 3: | ||
| 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 16 (Python)| << Lektion 16]]}} | ||
| + | <!-- {{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 16 (Python)|Ö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 38: | 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 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. | |
| − | I matematiken realiseras konceptet med s.k. <i>rekursionsformler | + | 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>]]. |
| − | </ | + | |
| + | I matematiken realiseras konceptet med s.k. <i>rekursionsformler</i>, se [[1.10_Rekursion#Fibonaccis_rekursionsformel|<b><span style="color:blue">Fibonaccis rekursionsformel</span></b>]]. | ||
| + | </big> | ||
</div> | </div> | ||
| Rad 53: | Rad 57: | ||
| − | <big><big>Följer man | + | <big><big>Följer man Fibonaccis instruktioner för kaniners fortplantning får man följande siffror:</big></big> |
== <b><span style="color:#931136">Fibonaccitalen</span></b> == | == <b><span style="color:#931136">Fibonaccitalen</span></b> == | ||
| Rad 66: | Rad 70: | ||
</td> | </td> | ||
<td><math> \qquad\qquad\qquad </math></td> | <td><math> \qquad\qquad\qquad </math></td> | ||
| − | <td> | + | <td>[https://sv.wikipedia.org/wiki/Leonardo_Fibonacci [[Image: FibonacciBildb.jpg]]]</td> </tr> |
</table> | </table> | ||
| + | </div> | ||
| Rad 86: | Rad 91: | ||
<div class="ovnA"> | <div class="ovnA"> | ||
| − | + | <big>I Python kan Fibonaccis rekursionsformel kodas som en <b><span style="color:red">rekursiv funktion fib()</span></b>. | |
| − | + | ||
En funktion kallas för <b><span style="color:red">rekursiv</span></b> om den anropar sig själv i sin egen definition. | En funktion kallas för <b><span style="color:red">rekursiv</span></b> om den anropar sig själv i sin egen definition. | ||
| − | </big> | + | </big> |
| − | + | ||
<div style="border:1px solid black;display:inline-table;margin-left: 0px;"> [[Image: FibonacciProgr.jpg]]</div> | <div style="border:1px solid black;display:inline-table;margin-left: 0px;"> [[Image: FibonacciProgr.jpg]]</div> | ||
| − | + | <big>Funktionen <b><span style="color:red">fib()</span></b> anropar sig själv två gånger i sin definition på rad 9: <b><span style="color:red">rekursiva anrop!</span></b> | |
| − | + | ||
| − | + | ||
Anropet på rad 14 är ett vanligt (inte rekursivt) funktionsanrop i huvudprogrammet. | Anropet på rad 14 är ett vanligt (inte rekursivt) funktionsanrop i huvudprogrammet. | ||
| − | + | </big> | |
</div> | </div> | ||
| − | + | == <b><span style="color:#931136">Körresultat</span></b> == | |
| − | = <b><span style="color:#931136">Körresultat</span></b> = | + | |
<div class="ovnA"> | <div class="ovnA"> | ||
<div style="border:1px solid black;display:inline-table;margin-left: 0px;"> [[Image: FibonacciKorEx.jpg]]</div> | <div style="border:1px solid black;display:inline-table;margin-left: 0px;"> [[Image: FibonacciKorEx.jpg]]</div> | ||
| Rad 110: | Rad 110: | ||
| − | = <b><span style="color:#931136">Läs om rekursion i kursboken på sid 98-100.</span> | + | == <b><span style="color:#931136">Läs om rekursion i [http://www.mathonline.se/Digitalt%20skapande%201/Koda_matte_finalversion_4_sep.pdf <span style="color:blue">kursboken</span>] på sid 98-100.</span> == |
| Rad 136: | Rad 136: | ||
| − | [[Matte:Copyrights|Copyright]] © | + | [[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. 09.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.
