Göm menyn

Upprepning

En klassisk roadtrip-låt

99 bottles of beer on the wall, 99 bottles of beer.
Take one down, pass it around. 98 bottles of beer.
98 bottles of beer on the wall, 98 bottles of beer.
Take one down, pass it around. 97 bottles of beer.
97 bottles of beer on the wall, 97 bottles of beer.
Take one down, pass it around. 96 bottles of beer.
96 bottles of beer on the wall, 96 bottles of beer.
Take one down, pass it around. 95 bottles of beer.
95 bottles of beer on the wall, 95 bottles of beer.
Take one down, pass it around. 94 bottles of beer.
94 bottles of beer on the wall, 94 bottles of beer.
Take one down, pass it around. 93 bottles of beer.
93 bottles of beer on the wall, 93 bottles of beer.
Take one down, pass it around. 92 bottles of beer.
...
...

Låten fortsätter så tills man kommer ner till "0 bottles of beer". Om vi vill skriva ett program som ska skriva ut texten till denna låt kan vi skriva 198 print-satser i följd, men ett smartare sätt vore att använda oss av upprepning. Ni kommer senare att få se att det då räcker med 4 rader kod.

Vi vill skriva en funktion som räknar ner ett tal i från 99 till 1. För varje i ska den skriva ut de två sångraderna med i på rätt ställe.

Vi vill ha något i denna stilen:

Hur fungerar range()?

För att se hur range() fungerar visar vi här lite körexempel.

Det finns tre olika sätt att använda range():

  • range(slut) som ger en sekvens från 0 till, men inte med, slut.
  • range(start, slut) som ger en sekvens från start till, men inte med, slut.
  • range(start, slut, steg) som ger en en sekvens från start till, men inte med, slut, med steglängd steg.

start, slut och steg måste vara heltal. En tom sekvens ges om inget giltigt interall är givet.

Dokumentation

Bottles of beer on the wall

Vi kan nu skriva en funktion som skriver ut vår låttext med hjälp av upprepning.

Iterativ version

På rad 2 säger vi att i ska börja på n och gå ner till (men inte inklusive) 0. -1 som steglängd ser till att vi räknar neråt istället för uppåt. På rad 3 och 4 skriver vi ut en del av låttexten med i insatt på rätt ställe. Dessa rader kommer att upprepas varje steg tills det att i har nått 0. Det här är en iterativ funktion. Vi ska nu kolla hur vi kan skriva funktionen på ett rekursivt sätt.

Rekursiv version

En rekursiv funktion är en funktion som anropar sig själv. Detta använder man ofta när man kan lösa ett problem om man vet svaret till mindre instanser av samma problem (som vi snart kommer att se i fakultetsfunktionen).

Så här kan en rekursiv variant av sången se ut:

På rad 3-4 gör vi samma sak som i den iterativa varianten, vi skriver ut låttexten och skriver in i på rätt ställe. Efter att vi har skrivit ut texten för ett visst i så anropar vi funktionen igen med i-1 (har vi skrivit ut texten för i=8 så vill vi skriva ut den för i=7 efter).

För att se till att funktionen någon gång slutar anropa sig själv har vi på rad 1 en if-sats som ser till att koden bara körs om song anropas med ett i som är större än 0. Försäkra er själva om att funktionen körs för evigt om if-satsen inte är där.

Fakultet

Det finns olika matematiska definitioner på fakultet.

Iterativ version

Fakulteten av n är produkten av alla tal från 1 till n.

n! = n x (n - 1) x (n - 2) x ... x 2 x 1

Hur kan man skriva detta i Python-kod?

På rad 2 börjar vi med att sätta resultatet till 1. På rad 3 säger vi sedan att vi vill gå igenom alla tal från 1 till (men inte inklusive) n+1. Inuti for-loopen multiplicerar vi varje sådant tal på resultatet (rad 4). Tillslut så skickar vi tillbaka resultatet med en retur-sats.

Vi testar programmet:

Rekursiv

Fakulteten av n är 1 om n är 0, annars är det n gånger fakulteten av n-1.

Matematisk definition av rekursiv fakultet

Hur kan man skriva det i Python-kod?

Den första raden i raden i den matematiska definitionen är basfallet som ser till att rekursionen slutar. Här ser vi att rad 2-3 i Python-koden är basfallet. Vi kollar här ifall n är lika med 0, är detta sant så returnerar vi 1. Alla rekursiva funktioner måste ha ett basfall för att se till rekursionen slutar.

Rekursionsfallet (den nedre raden i den matematiska definitionen) motsvaras av rad 4-5 i Python-koden. Här returneras värdet av n multiplicerat med fakulteten av n-1. För att räkna ut fakulteten av n-1 så använder vi factorial-funktionen igen. Rekursionsfallet måste se till att problemet går mot basfallet.

Tillhörande quiz

Finnes här


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2016-09-07