Skillnad mellan versioner av "Rekursion"
Taifun (Diskussion | bidrag) m |
Taifun (Diskussion | bidrag) m |
||
| Rad 33: | Rad 33: | ||
=== <b><span style="color:#931136">Algoritmen Primtalsfaktorisering</span></b> === | === <b><span style="color:#931136">Algoritmen Primtalsfaktorisering</span></b> === | ||
| − | <big>Strategi för att faktorisera ett givet | + | <big>Strategi för att faktorisera ett givet tal, implementerad i den rekursiva [[Primtal#Programmet_PrimFaktorer|<b><span style="color:blue">funktionen faktorisera()</span></b>]].</big> |
<div style="border:1px solid black;display:inline-table;margin-left: 0px;"> [[Image: Algoritmen_Primtalsfaktoriseringa.jpg]]</div> | <div style="border:1px solid black;display:inline-table;margin-left: 0px;"> [[Image: Algoritmen_Primtalsfaktoriseringa.jpg]]</div> | ||
| − | |||
| − | |||
| − | |||
| − | |||
<big>Rekursion används här som ett koncept för prblemlösning: | <big>Rekursion används här som ett koncept för prblemlösning: | ||
| − | Hur gör jag för att | + | Hur gör jag för att dela upp givet tal i sina primfaktorer? Jag upprepar stegen 1-3 i algoritmen ovan. |
| − | + | Bara att jag gör det varje gång med ett annat startvärde: med n/en primfaktor istället för med n. | |
| − | 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>]]. | + | I matematiken realiseras konceptet med s.k. <i>rekursionsformler</i>, se t.ex. [[1.10_Rekursion#Fibonaccis_rekursionsformel|<b><span style="color:blue">Fibonaccis rekursionsformel</span></b>]]. |
</big> | </big> | ||
</div> | </div> | ||
Versionen från 13 mars 2023 kl. 21.18
| << Agenda | Genomgång Primtal | Genomgång Rekursion | Dagens övningar | Nästa lektion >> |
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 Primtalsfaktorisering
Strategi för att faktorisera ett givet tal, implementerad i den rekursiva funktionen faktorisera().
Rekursion används här som ett koncept för prblemlösning:
Hur gör jag för att dela upp givet tal i sina primfaktorer? Jag upprepar stegen 1-3 i algoritmen ovan.
Bara att jag gör det varje gång med ett annat startvärde: med n/en primfaktor istället för med n.
I matematiken realiseras konceptet med s.k. rekursionsformler, se t.ex. 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
Fortsätt med Dagens övningar.
Copyright © 2023 TechPages AB. All Rights Reserved.
