Skillnad mellan versioner av "1.10 Rekursion"

Från Mathonline
Hoppa till: navigering, sök
m
m
Rad 66: Rad 66:
 
</td>
 
</td>
 
<td><math> \qquad\qquad\qquad </math></td>
 
<td><math> \qquad\qquad\qquad </math></td>
<td><div style="border:1px solid black;display:inline-table;margin-left: 0px;">[https://sv.wikipedia.org/wiki/Leonardo_Fibonacci [[Image: FibonacciBildb.jpg]]]</div></td> </tr>
+
<td>[https://sv.wikipedia.org/wiki/Leonardo_Fibonacci <div style="border:1px solid black;display:inline-table;margin-left: 0px;"> [[Image: FibonacciBildb.jpg]]</div>]</td> </tr>
 
</table>
 
</table>
  

Versionen från 18 december 2020 kl. 08.55

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

Algor IntervHalv.jpg

Körexempel på Gissa tal-spelet där algoritmen Intervallhalvering använts:

Gissa tal Korex.jpg

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, se Programmet Fibonacci.

I matematiken realiseras konceptet med s.k. rekursionsformler, se Fibonaccis rekursionsformel.


Annat exempel: Fibonacci

Kaniners fortplantning

Fibonacciproblemet.jpg


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

Fibonaccitalen

Fibonaccitalen.jpg


Mönster för bildningen av Fibonaccis talföljd,

även kallad Fibonaccitalen:


Summan av två på varandra följande
fibonaccital ger nästa fibonaccital.

\( \qquad\qquad\qquad \) <div style="border:1px solid black;display:inline-table;margin-left: 0px;"> FibonacciBildb.jpg</div>


Fibonaccis rekursionsformel

FibonacciRekFormel.jpg


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.

FibonacciProgr.jpg

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

FibonacciKorEx.jpg


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


 










Copyright © 2020 TechPages AB. All Rights Reserved.