Functies en recursie
I Zelf een functie schrijven
1 Van gebruiken naar schrijven
Je gebruikt al functies zoals len(), max() en round(). Je geeft er iets in, je krijgt er iets uit, en hoe het binnenin werkt, moet je niet weten.
Vandaag draaien we dat om: jij schrijft de zwarte doos. Daarna laten we een functie zichzelf gebruiken. Dat heet recursie.
print(max(3, 8))
print(round(3.14159, 2))2 Een functie definiëren
Een functie schrijf je met het sleutelwoord def.
def kwadraat(x):
return x * x
print(kwadraat(5))
print(kwadraat(1.5))-
• kwadraat is de naam.
-
• x is de parameter: een variabele die pas een waarde krijgt wanneer je de functie aanroept.
-
• Alles wat ingesprongen staat, hoort bij de functie.
-
• return geeft de retourwaarde terug en stopt de functie.
De definitie zelf voert niets uit. Ze legt enkel vast wat er moet gebeuren als iemand de functie aanroept.
3 Return of print?
Een functie die iets toont, is niet hetzelfde als een functie die iets teruggeeft.
def toon_dubbel(x):
print(2 * x)
def dubbel(x):
return 2 * x
toon_dubbel(4)
resultaat = dubbel(4)
print(resultaat + 1)-
• print zet tekst op het scherm. Je kan er daarna niet mee rekenen.
-
• return levert een waarde af aan de code die de functie aanriep.
Probeer toon_dubbel(4) + 1: wat gaat er mis? Een functie zonder return geeft None terug.
4 Een functie met een beslissing
Binnen een functie gebruik je alles wat je al kent.
def grootste(a, b):
if a > b:
return a
return b
print(grootste(4, 9))
print(grootste(7, 2))Zodra een return uitgevoerd wordt, stopt de functie. De tweede return komt dus enkel aan bod als a > b niet waar is.
5 Functies roepen functies op
Een functie mag een andere functie gebruiken, ook een die je zelf schreef.
def kwadraat(x):
return x * x
def lengte_diagonaal(a, b):
return (kwadraat(a) + kwadraat(b)) ** 0.5
print(lengte_diagonaal(3, 4))Houd dit vast: lengte_diagonaal wacht tot kwadraat klaar is. Pas dan rekent ze verder. Straks is het niet langer een andere functie die we oproepen.
6 Oefeningen
Oefening 1
Download oefennotebookOpgave. Schrijf een functie omtrek_vierkant(zijde) die de omtrek van een vierkant teruggeeft. Roep ze op met zijde \(2.5\).
Denk vooraf na: Moet de functie de omtrek tonen of teruggeven? Wat verandert er voor de code die haar gebruikt?
De omtrek is \(4\) keer de zijde. Gebruik return.
def omtrek_vierkant(zijde):
...
print(omtrek_vierkant(2.5))
def omtrek_vierkant(zijde):
return 4 * zijde
print(omtrek_vierkant(2.5))
Oefening 2
Opgave. Schrijf een functie kleinste(a, b, c) die het kleinste van drie getallen teruggeeft, zonder de ingebouwde functie min() te gebruiken.
Vergelijk eerst a met b. Je kan ook je eigen functie grootste van hierboven omkeren tot een functie kleinste met twee getallen en die twee keer gebruiken.
def kleinste(a, b, c):
...
print(kleinste(4, 2, 9))
def kleinste(a, b, c):
resultaat = a
if b < resultaat:
resultaat = b
if c < resultaat:
resultaat = c
return resultaat
print(kleinste(4, 2, 9))II Een functie die zichzelf aanroept
1 Aftellen
Stel dat je wil aftellen van \(3\) naar \(1\). Zonder lus kan dat zo:
def aftellen(n):
print(n)
aftellen(n - 1)
aftellen(3)Laat dit lopen. De functie telt aan één stuk door en Python stopt met een RecursionError. Er is niets dat de functie zegt dat ze moet ophouden.
Een functie die zichzelf aanroept, heet recursief.
2 Het basisgeval
Een recursieve functie heeft altijd twee delen.
-
1. Het basisgeval: een situatie die zo klein is dat je het antwoord meteen kent. Hier stopt de recursie.
-
2. Het recursieve geval: de functie roept zichzelf op met een kleiner probleem.
def aftellen(n):
if n == 0:
print("Start!")
else:
print(n)
aftellen(n - 1)
aftellen(3)-
• Basisgeval: n == 0, dan tonen we Start!.
-
• Recursief geval: toon n en tel af vanaf n - 1.
Elke aanroep werkt met een kleinere n. Zo komen we vanzelf bij het basisgeval uit.
3 Eerst of laatst afdrukken
Verwissel de twee regels en kijk wat er gebeurt.
def opteller(n):
if n == 0:
print("Klaar!")
else:
opteller(n - 1)
print(n)
opteller(3)De uitvoer is \(\texttt {Klaar!}, 1, 2, 3\). De print(n) komt pas na de recursieve aanroep. Die aanroep moet dus eerst helemaal klaar zijn. In het volgende deel zien we waarom.
4 Oefeningen
Oefening 3
Opgave. Schrijf een recursieve functie lancering(n) die aftelt van n tot \(1\) en daarna Lancering! toont. Roep ze op met \(5\).
Denk vooraf na: Wat is het basisgeval? Welke waarde van n stopt de recursie?
Het basisgeval is n == 0. Daar toon je enkel Lancering!.
def lancering(n):
...
lancering(5)
def lancering(n):
if n == 0:
print("Lancering!")
else:
print(n)
lancering(n - 1)
lancering(5)III Recursie met een retourwaarde
1 Een som in kleinere sommen
We willen de som \(1+2+\dots +n\) berekenen. Schrijf haar als een kleinere som:
\[ 1+2+\dots +n = n + (1+2+\dots +(n-1)). \]
De som tot \(n\) is dus \(n\) plus de som tot \(n-1\). Dat is dezelfde vraag, maar kleiner. Het kleinste geval is de som tot \(0\), en die is \(0\).
def som(n):
if n == 0:
return 0
return n + som(n - 1)
print(som(4))-
• Basisgeval: som(0) is 0.
-
• Recursief geval: som(n) is n + som(n - 1).
2 Hoe Python dit uitrekent
Wat gebeurt er bij som(3)? De berekening gaat eerst naar beneden, tot het basisgeval, en daarna weer naar boven.
Elke aanroep wacht tot de volgende een antwoord geeft. Python onthoudt die wachtende aanroepen op een stapel, de call stack. Pas als som(0) 0 teruggeeft, kunnen ze één voor één afgewerkt worden.
Volg dit zelf met de debugger: bij elke stap zie je de call stack van wachtende aanroepen. De bovenste aanroep is blauw zolang we dieper gaan en oranje wanneer ze een waarde teruggeeft. Onder de stapel groeit de afleiding mee, met het deel gemarkeerd dat bij de aanroep van dat moment hoort. Pas som(3) aan naar een andere waarde en kijk hoe alles verandert.
\begin{align*}
\texttt {som(3)} &= 3 + \texttt {som(2)}\\ &= 3 + (2 + \texttt {som(1)})\\ &= 3 + (2 + (1 + \texttt {som(0)}))\\ &= 3 + (2 + (1 + 0))\\ &= 3 + (2 + 1)\\ &= 3 + 3\\
&= 6
\end{align*}
def som(n):
if n == 0:
return 0
return n + som(n - 1)
print(som(3))Een gewone lus onthoudt niets op een stapel. Daarom heeft Python een grens: bij te veel wachtende aanroepen (ongeveer duizend) stopt het met een RecursionError.
3 Faculteit
Het product \(n! = 1\cdot 2\cdot 3\cdots n\) heet de faculteit van \(n\). Ook die breekt in een kleinere versie van zichzelf:
\[ n! = n\cdot (n-1)!\qquad \text {en}\qquad 0! = 1. \]
def faculteit(n):
if n == 0:
return 1
return n * faculteit(n - 1)
print(faculteit(5))
print(faculteit(10))De werkwijze is telkens dezelfde:
-
1. Wat is het kleinste geval, waarvan ik het antwoord ken?
-
2. Hoe schrijf ik het probleem met een kleiner probleem van dezelfde soort?
4 Oefeningen
Oefening 4
Opgave. Schrijf een recursieve functie macht(x, n) die \(x^n\) berekent voor een geheel getal \(n\ge 0\), zonder ** of pow(). Roep ze op met \(2\) en \(10\).
Denk vooraf na: Wat is \(x^0\)? Hoe schrijf je \(x^n\) met \(x^{n-1}\)?
\(x^n = x\cdot x^{n-1}\) en \(x^0 = 1\).
def macht(x, n):
...
print(macht(2, 10))
def macht(x, n):
if n == 0:
return 1
return x * macht(x, n - 1)
print(macht(2, 10))
Oefening 5
Opgave. Schrijf een recursieve functie cijfersom(n) die de som van de cijfers van een positief geheel getal teruggeeft. Dus cijfersom(472) is \(4+7+2=13\).
Met n % 10 krijg je het laatste cijfer en met n // 10 de rest van het getal. Een getal van één cijfer is het basisgeval.
def cijfersom(n):
...
print(cijfersom(472))
def cijfersom(n):
if n < 10:
return n
return n % 10 + cijfersom(n // 10)
print(cijfersom(472))IV Recursie of lus?
1 Twee manieren, hetzelfde resultaat
De som van daarnet kan ook met een lus. Links staat de lus, rechts de recursie. Onder beide staat de oproep. Eén playknop voert alles uit, en je kan n voor beide tegelijk aanpassen.
def som_lus(n):
totaal = 0
for i in range(1, n + 1):
totaal += i
return totaaldef som(n):
if n == 0:
return 0
return n + som(n - 1)n = 4
print(som_lus(n))
print(som(n))-
• De lus is korter in geheugen en sneller.
-
• De recursieve versie volgt de wiskundige definitie letterlijk.
Soms is het probleem van nature een kleiner probleem van dezelfde soort. Dan is recursie de natuurlijke oplossing, en een lus ingewikkelder.
2 Een woord omkeren
Een woord omkeren: neem de laatste letter, zet die vooraan en keer de rest om.
def keer_om(woord):
if len(woord) == 0:
return ""
return woord[-1] + keer_om(woord[:-1])
print(keer_om("informaticawetenschappen"))-
• Basisgeval: het lege woord is al omgekeerd.
-
• Recursief geval: laatste letter plus het omgekeerde van de rest.
3 Fibonacci
De rij van Fibonacci begint met \(0, 1, 1, 2, 3, 5, 8, 13,\dots \): elk getal is de som van de twee vorige.
\[ F(0)=0,\qquad F(1)=1,\qquad F(n)=F(n-1)+F(n-2). \]
Hier zijn er twee basisgevallen en twee recursieve aanroepen.
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
for i in range(10):
print(f"F({i}) = {fibonacci(i)}")Dit werkt, maar zet range(10) eens op range(35). De getallen komen steeds trager, want fibonacci(n) berekent fibonacci(n - 2) opnieuw, terwijl fibonacci(n - 1) dat al deed. Op de site geeft Python het na 8 seconden op. Een recursieve oplossing is niet altijd de snelste. Zoek in een volgend hoofdstuk hoe het beter kan.
4 Oefeningen
Oefening 6
Opgave. Een woord is een palindroom als het van achter naar voor hetzelfde leest (lepel, racecar). Schrijf een recursieve functie palindroom(woord) die True of False teruggeeft.
Denk vooraf na: Welke woorden zijn zeker een palindroom, zonder iets te vergelijken? Wat vergelijk je anders eerst?
Een woord van \(0\) of \(1\) letter is altijd een palindroom. Anders moeten de eerste en de laatste letter gelijk zijn, en het woord er tussenin ook een palindroom (woord[1:-1]).
def palindroom(woord):
...
print(palindroom("lepel"))
print(palindroom("python"))
def palindroom(woord):
if len(woord) <= 1:
return True
if woord[0] != woord[-1]:
return False
return palindroom(woord[1:-1])
print(palindroom("lepel"))
print(palindroom("python"))V Samenvatting
-
• Een functie schrijf je met def, met parameters en een return. Een functie zonder return geeft None terug.
-
• print toont, return levert af.
-
• Een functie mag andere functies oproepen, ook zichzelf.
-
• Een recursieve functie heeft een basisgeval (stopt) en een recursief geval (kleiner probleem, dezelfde functie).
-
• Zonder basisgeval, of zonder dat het probleem kleiner wordt, krijg je een RecursionError.
-
• Wachtende aanroepen staan op de call stack.
-
• Recursie is natuurlijk bij problemen die uit kleinere versies van zichzelf bestaan, zoals faculteit, een woord omkeren of Fibonacci. Een lus is vaak sneller.