De grootste gemeenschappelijke deler (ggd) van twee getallen \(a\) en \(b\) is het grootste getal waar \(a\) en \(b\) door gedeeld kunnen worden zonder dat er een rest overblijft. Zo is bijvoorbeeld de ggd van 15 en 20 gelijk aan 5, omdat dit het grootste getal is waar zowel 15 als 20 door gedeeld kunnen worden zonder rest.
Je kan de ggd van twee getallen uitrekenen met volgende formule:
$$ \mathrm{ggd}(a, b) = \begin{cases} a & \text{als \(b = 0\)},\\ \mathrm{ggd}(b, a \mod b) & \text{anders.} \end{cases} $$
Dit is een voorbeeld van een recursieve definitie: de functie \(\mathrm{ggd}(a,b)\) is gedefinieerd in termen van zichzelf. Dit houdt steek, omdat het tweede argument aan de functie telkens kleiner wordt wanneer de functie zichzelf oproept en we dus uiteindelijk in het basisgeval \(\mathrm{ggd}(n, 0) = n\) zullen belanden dat we direct kunnen uitrekenen. Deze programmeertechniek, waar een functie zichzelf oproept, noemen we recursie. Heel veel algoritmen worden het meest elegant geformuleerd op een recursieve manier, maar vaak heeft deze elegantie een kost: recursie is meestal niet de meest efficiënte manier om een algoritme te implementeren. Niettemin komt het vaak wel van pas en daarom is het één van de fundamentele technieken die elke programmeur moet kennen.
We werken bijvoorbeeld \(\mathrm{ggd}(15, 20)\) uit:
ggd(15, 20) = ggd(20, 15 % 20) = ggd(20, 15)ggd(20, 15) = ggd(15, 20 % 15) = ggd(15, 5)ggd(15, 5) = ggd(5, 15 % 5) = ggd(5, 0)ggd(5, 0) = 5Je ziet dat het tweede argument aan de ggd functie telkens kleiner wordt: we gaan van 20 naar 15 naar 5 naar 0. Eens het tweede argument 0 is, hebben we de gezochte ggd als eerste argument en kunnen we die direct teruggeven.
Schrijf een programma dat twee getallen inleest uit een bestand en hun ggd bepaalt. Probeer dit eerst te doen via recursie, waar je bijna letterlijk de bovenstaande formule implementeert via een functie ggd die zichzelf aanroept. Probeer dan eens een manier te bedenken om dit te doen zonder recursie.
Invoer:
15
20
Uitvoer:
5