Recursie¶

Deze pagina bevat uitvoerbare code.

Een directory vol directories¶

Stel dat je de namen wilt afdrukken van alle bestanden in de directory documenten. Daar horen ook de bestanden in de subdirectories bij, en een subdirectory kan zelf weer subdirectories hebben. Voordat je iets programmeert, maak je eerst een plan, zoals bij de drie p’s uit week 1 van Programmeren 1: probeer, plan, programmeer.

Een plan kun je opschrijven in pseudocode: iets wat op code lijkt, maar geen Python is. Het zegt wat je wilt bereiken, zonder dat elk detail klopt.

Plan 1:

functie print_names(directory):
    druk de bestanden in directory af
    voor elke subdirectory in directory:
        druk de bestanden in subdirectory af
        voor elke subsubdirectory in subdirectory:
            druk de bestanden in subsubdirectory af
            voor elke subsubsubdirectory in subsubdirectory:
                druk de bestanden in subsubsubdirectory af

Hoeveel lussen heb je nodig? Dat weet je niet. Elke lus die je toevoegt, gaat één niveau dieper, en er kan altijd nog een niveau onder zitten. Directories vormen samen een boom: elke directory kan subdirectories bevatten, die weer hun eigen subdirectories kunnen bevatten, enzovoort.

        flowchart TD
    D["documenten"] --> F1(["verslag.docx"])
    D --> P["projecten"]
    P --> F2(["plan.docx"])
    P --> A["archief"]
    A --> F3(["notulen.docx"])
    A --> Q["... en zo verder"]

Kijk nog eens naar de boom. Een subdirectory is zelf ook een directory. Stel dat print_names al werkt voor een directory. Dan kun je hem ook gebruiken voor elke subdirectory. Dat mag: een functie mag zichzelf aanroepen.

Plan 2:

functie print_names(directory):
    druk de bestanden in directory af
    voor elke subdirectory in directory:
        print_names(subdirectory)

Een functie die zichzelf aanroept, heet recursief. Het verschijnsel heet recursie, en de aanroep waarmee een functie zichzelf aanroept, heet de recursieve aanroep. Plan 2 heeft geen vast aantal lussen meer, en werkt dus voor elke diepte. Aan het eind van dit college schrijf je het in Python. Eerst kijk je hoe zo’n functie werkt.

Een probleem dat op zichzelf lijkt¶

Stel je een functie voor die telt hoeveel i’s er in een string staan. Schrijf de berekening eerst uit, zonder aan Python te denken. Hoeveel i’s staan er in "i💙aliens"?

Een string is een rij tekens. Je kunt het eerste teken bekijken, en dat is een i of niet: 0 of 1. Daarbij tel je het aantal i’s in de rest van de string:

Aantal i’s in "i" + aantal i’s in "💙aliens"

Voor de rest doe je hetzelfde: je bekijkt het eerste teken en telt het aantal i’s in wat daarna komt.

Aantal i’s in "i" + aantal i’s in "💙" + aantal i’s in "aliens"

Enzovoort. Er ontstaat een patroon: na het eerste teken stel je dezelfde vraag over de rest van de string. Het probleem bevat een kleinere versie van zichzelf.

Het eerste teken en de rest van een string schrijf je in Python als s[0] en s[1:], zoals in week 2 van Programmeren 1.

Faculteit¶

Stel je 42 aliens voor die op een rij willen staan. Op hoeveel manieren kan dat? Voor de eerste plek heb je 42 keuzes, voor de tweede 41, enzovoort: 42 * 41 * 40 * ... * 3 * 2 * 1. Dat heet 42 faculteit, in de wiskunde geschreven als \(42!\).

Met vijf aliens:

fac(5) = 5 * 4 * 3 * 2 * 1, en dat is 120.

Kijk naar alles na de eerste 5 *. Dat is 4 * 3 * 2 * 1, en dat is precies fac(4). Dus:

fac(5) = 5 * fac(4)

En zo voor elke n:

fac(n) = n * fac(n - 1)

Net als bij de i’s bevat het probleem een kleinere versie van zichzelf.

Een eerste versie¶

Die regel kun je letterlijk in Python schrijven:

def fac(n):
    """Geeft n faculteit."""
    return n * fac(n - 1)

Wat gebeurt er als je fac(3) aanroept? Voorspel het eerst, en voer dan de cel hieronder uit.

fac(3)

RecursionError: maximum recursion depth exceeded

fac(3) roept fac(2) aan, die roept fac(1) aan, en dan fac(0), fac(-1), fac(-2), en zo verder. Nergens staat dat het moet stoppen. Python houdt dat niet eindeloos vol: na ongeveer duizend aanroepen die nog niet klaar zijn, stopt het met een RecursionError. Dat heet een oneindige recursie. Waarom Python bij ongeveer duizend stopt, zie je verderop bij de frames.

Hierboven staat alleen de laatste regel van de foutmelding. Voer je dit uit in VS Code, dan staat daarboven een lange traceback, met een regel als [Previous line repeated 996 more times]: dezelfde aanroep, bijna duizend keer.

Het basisgeval¶

Er moet een geval zijn waarin de functie zichzelf níet aanroept, maar meteen een antwoord teruggeeft. Dat heet het basisgeval. Het geval mét de recursieve aanroep heet het recursief geval.

Bij faculteit ligt het basisgeval bij 0: fac(0) is 1. Zo gaat n - 1 niet verder dan 0.

def fac(n):
    """Geeft n faculteit: 1 voor n = 0, en anders n * (n - 1) * ... * 1."""
    if n == 0:  # basisgeval
        return 1
    else:  # recursief geval
        return n * fac(n - 1)


assert fac(0) == 1
assert fac(1) == 1
assert fac(5) == 120

Eerst de aanroep, dan de rest¶

Kijk naar de laatste regel: n * fac(n - 1). Hoe kan Python n vermenigvuldigen met iets wat nog niet is uitgerekend? Dat kan niet. Python rekent eerst fac(n - 1) helemaal uit, en vermenigvuldigt daarna. Je kunt dat zichtbaar maken met een variabele:

def fac(n):
    """Geeft n faculteit: 1 voor n = 0, en anders n * (n - 1) * ... * 1."""
    if n == 0:  # basisgeval
        return 1
    else:  # recursief geval
        rest = fac(n - 1)
        return n * rest


assert fac(0) == 1
assert fac(5) == 120

De functie wacht bij rest = fac(n - 1) tot de recursieve aanroep een antwoord teruggeeft. Pas dan rekent ze n * rest uit.

Elke aanroep krijgt zijn eigen frame¶

In week 3 van Programmeren 1 zag je dat Python voor elke aanroep een frame op de stack zet, met de variabelen van die aanroep erin: elke aanroep krijgt zijn eigen frame. Dat geldt ook als een functie zichzelf aanroept. Elke aanroep van fac heeft zijn eigen n en zijn eigen rest.

Deze versie van fac drukt af wanneer een aanroep begint en wat hij teruggeeft:

def fac(n):
    """Geeft n faculteit, en drukt af wanneer een aanroep begint en eindigt."""
    print("fac(" + str(n) + ") begint")
    if n == 0:  # basisgeval
        result = 1
    else:  # recursief geval
        rest = fac(n - 1)
        result = n * rest
    print("fac(" + str(n) + ") geeft", result, "terug")
    return result


fac(3)

fac(3) begint
fac(2) begint
fac(1) begint
fac(0) begint
fac(0) geeft 1 terug
fac(1) geeft 1 terug
fac(2) geeft 2 terug
fac(3) geeft 6 terug

Lees de uitvoer van boven naar beneden. Eerst beginnen vier aanroepen, en geen ervan is klaar: fac(3) wacht op fac(2), die wacht op fac(1), die wacht op fac(0). Op dat moment staan er vier frames van fac tegelijk op de stack:

Frame	`n`	Wacht op
`fac(3)`	`3`	`fac(2)`
`fac(2)`	`2`	`fac(1)`
`fac(1)`	`1`	`fac(0)`
`fac(0)`	`0`	niets: dit is het basisgeval

Daarna geven ze in omgekeerde volgorde terug. fac(0) geeft 1 terug en zijn frame verdwijnt. Dan rekent fac(1) 1 * 1 uit, fac(2) 2 * 1 en fac(3) 3 * 2: 6.

Plak de functie en de aanroep fac(3) in Python Tutor en loop er stap voor stap doorheen. Je ziet de vier frames verschijnen en weer verdwijnen.

Nu zie je ook waarom de eerste versie stopte. Zonder basisgeval komt er bij elke aanroep een frame bij, en er verdwijnt er geen. Python staat maar een beperkt aantal frames tegelijk toe; daarboven geeft het een RecursionError.

Recursie unplugged¶

Een groep dieven zit op een rij. De dief helemaal links krijgt een beker met papiertjes, en op elk papiertje staat een getal. De groep moet erachter komen of het getal 42 in de beker zit. Zegt de dief helemaal links het goede antwoord tegen de bewakers, dan is de hele groep vrij. Zegt hij het verkeerde, dan blijven ze allemaal een jaar langer vastzitten. Er gelden twee regels. Breekt iemand een regel, dan heeft de groep verloren.

Elke dief mag één papiertje uit de beker halen en bekijken. Niemand anders mag het zien. Daarna mag hij de beker doorgeven aan zijn rechterbuur.
Elke dief mag één keer True of False fluisteren naar zijn linkerbuur. De rest van de groep mag het niet horen.

Met welke strategie lossen ze dit op?

Oplossing¶

Elke dief pakt één papiertje.

Staat er 42 op, dan fluistert hij True naar zijn linkerbuur. De beker hoeft niet verder.
Staat er iets anders op, dan geeft hij de beker door aan zijn rechterbuur, en wacht op wat die terugfluistert. Dat antwoord fluistert hij door naar links.
Krijgt een dief een lege beker, dan fluistert hij False naar links.

Zo komt het antwoord van rechts naar links terug, tot de dief helemaal links het weet. In Python:

def find_forty_two(cup):
    """Geeft True als 42 in de lijst cup staat."""
    if cup == []:  # basisgeval: de beker is leeg
        return False

    paper = cup[0]  # pak één papiertje
    if paper == 42:  # basisgeval: 42 gevonden
        return True

    answer = find_forty_two(cup[1:])  # de rest gaat naar je rechterbuur
    return answer  # fluister zijn antwoord door naar links


assert find_forty_two([3, 42, 7]) == True
assert find_forty_two([3, 7]) == False
assert find_forty_two([]) == False

Deze functie heeft twee basisgevallen: de lege beker, en het papiertje met 42. Bij het tweede stopt de recursie vroeg; de rest van de beker bekijkt niemand meer.

Je kunt het ook zo zien: elke dief is te lui om de hele beker na te kijken. Hij bekijkt één papiertje en schuift de rest van het werk door naar zijn buurman. Hoe die het oplost, maakt hem niet uit. De buurman is net zo lui: hij bekijkt ook één papiertje en schuift de rest weer door. Zo doet elke aanroep één stap, en laat hij de rest over aan de recursieve aanroep.

Opdracht 1¶

De dieven zitten weer op een rij, en de dief helemaal links krijgt weer een beker met getallen. Nu moet hij het hoogste getal noemen. Dit zijn de regels:

Elke dief mag één papiertje uit de beker halen. Daarna mag hij de beker doorgeven aan zijn rechterbuur.
Elke dief mag één getal laten zien aan zijn linkerbuur.

Met welke strategie lossen ze dit op?

Opdracht 2¶

De dieven zitten weer op een rij, maar nu zijn ze geblinddoekt. Ze zien elkaar niet en weten niet hoe groot de groep is. De dief helemaal links moet noemen hoeveel papiertjes er in de beker zitten. Dit zijn de regels:

Elke dief mag één papiertje uit de beker halen. Daarna mag hij de beker doorgeven aan zijn rechterbuur.
Elke dief mag één getal fluisteren naar zijn linkerbuur.

Met welke strategie lossen ze dit op?

Opdracht 3¶

De dief helemaal links moet de som noemen van alle getallen in de beker. De regels zijn dezelfde als bij opdracht 2. Met welke strategie lossen ze dit op?

Terug naar de directory¶

Nu kun je plan 2 in Python schrijven. Een directory is een dictionary, zoals in week 1 van Programmeren 2, met drie sleutels:

Sleutel	Waarde
`"naam"`	de naam van de directory
`"bestanden"`	een dictionary van bestandsnaam naar grootte in kilobyte
`"directories"`	een lijst van subdirectories, elk weer een dictionary in deze vorm

De boom van het begin van dit college ziet er dan zo uit, zonder het “… en zo verder”:

documents = {
    "naam": "documenten",
    "bestanden": {"verslag.docx": 120},
    "directories": [
        {
            "naam": "projecten",
            "bestanden": {"plan.docx": 40},
            "directories": [
                {
                    "naam": "archief",
                    "bestanden": {"notulen.docx": 25},
                    "directories": [],
                },
            ],
        },
    ],
}

print_files volgt plan 2. De lus over d["bestanden"] loopt langs de sleutels, en dat zijn de bestandsnamen.

def print_files(d):
    """Drukt de namen af van alle bestanden in d en in al zijn subdirectories."""
    for name in d["bestanden"]:
        print(name)

    for sub in d["directories"]:
        print_files(sub)


print_files(documents)

verslag.docx
plan.docx
notulen.docx

De recursieve aanroep staat hier in een lus: één aanroep per subdirectory. Hoe diep de boom ook is, de functie hoeft het niet te weten.

Waar is het basisgeval? Er staat geen if. Kijk naar archief: die heeft geen subdirectories, dus d["directories"] is een lege lijst. De lus doet dan niets, en er volgt geen recursieve aanroep. Een directory zonder subdirectories is hier het basisgeval.

Tot slot¶

Je hebt in dit college drie dingen gezien:

Een functie mag zichzelf aanroepen. Dat is de recursieve aanroep, en die gaat over een kleiner probleem: n - 1 in plaats van n, de rest van de beker, een subdirectory.
Elke aanroep krijgt zijn eigen frame op de stack, met zijn eigen variabelen.
Er moet een basisgeval zijn, waarin de functie zichzelf niet aanroept. Anders krijg je een oneindige recursie.

In het tweede college leer je zelf een recursieve functie ontwerpen: hoe vind je het basisgeval, wat is het kleinere probleem, en hoe maak je van het antwoord daarop het antwoord op het hele probleem? In het werkcollege doorzoek je een directory zoals documents op meer manieren.