Recursie in Python: concepten, voorbeelden en tips

Recursie is een fundamenteel concept in programmeren en heeft bijzondere betekenis in Python. Het verwijst naar de techniek waarbij een functie zichzelf aanroept om een probleem op te lossen door het op te delen in kleinere, beheersbare deelproblemen. 

Deze methode maakt elegante en beknopte oplossingen mogelijk, vooral bij problemen met herhalende taken of hiërarchische structuren. In Python wordt recursie gebruikt in allerlei toepassingen, van sorteeralgoritmen algoritmen tot complexe datadoorgangen. 

Recursieve oplossingen spiegelen vaak de wiskundige definities van problemen, waardoor ze intuïtief zijn voor wie vertrouwd is met wiskundig redeneren. De schoonheid van recursie zit in het vermogen om complexe algoritmen in slechts enkele regels code uit te drukken, wat zorgt voor oplossingen die zowel elegant als leesbaar zijn. Het beheersen van recursie vraagt echter om een andere manier van denken dan de meer gebruikelijke iteratieve aanpakken.

In dit artikel verken ik het concept recursie, hoe het werkt in Python en de praktische toepassingen ervan, inclusief een bespreking van veelvoorkomende problemen en een vergelijking met iteratie. Als je nieuw bent met Python, overweeg dan een van onze cursussen, zoals Introduction to Python, Programming Paradigm Concepts of Python Programming Fundamentals te volgen.

Wat is recursie in Python?

In Python verwijst recursie naar een functie die zichzelf aanroept om een probleem op te lossen. Dit omvat twee cruciale onderdelen:

• Basisgeval: Dit is de voorwaarde die de recursie beëindigt. Zonder dit zou de functie zichzelf eindeloos blijven aanroepen, wat uiteindelijk tot een crash of geheugentekort leidt.
• Recursief geval: In dit deel van de functie wordt het probleem opgesplitst in kleinere delen en wordt de functie opnieuw aangeroepen met die kleinere delen.

Hier is een eenvoudige manier om over recursie te denken: stel je een functie voor die een complex probleem oplost door kleinere versies van hetzelfde probleem op te lossen, totdat een oplossing is bereikt die geen verdere recursie vereist.

De recursieve aanpak volgt de "divide-and-conquer"-strategie: complexe problemen worden opgesplitst in eenvoudigere versies totdat een triviaal geval wordt bereikt. Deze aanpak weerspiegelt vaak hoe we van nature problemen oplossen. Bij het sorteren van een stapel kaarten delen we die bijvoorbeeld vaak eerst op in kleinere groepen en voegen we die daarna samen, wat in essentie is hoe recursieve sorteeralgoritmen zoals merge sort werken.

Elke recursieve functie moet minstens één basisgeval en minstens één recursief geval hebben. Het basisgeval voorkomt oneindige recursie door een voorwaarde te bieden die geen verdere aanroepen vereist. Het recursieve geval verkleint het probleem bij elke aanroep, zodat uiteindelijk het basisgeval wordt bereikt.

Hoe werkt recursie in Python?

Recursie werkt doordat een functie zichzelf kan aanroepen met aangepaste argumenten en zo het probleem stapsgewijs in kleinere stappen oplost. Om dit concreter te maken: bekijk de taak om de som van getallen van 1 tot num te berekenen.

Hier is een eenvoudige recursieve aanpak om de som te berekenen:

def sum_recursive(num):
    if num == 1:  # Base case
        return num
    return num + sum_recursive(num - 1)  # Recursive case

print(sum_recursive(3)) # 3 + 2 + 1 Mogelijk gemaakt door

6Mogelijk gemaakt door

In deze functie is het basisgeval wanneer num == 1, wat de recursie stopt. Anders roept de functie zichzelf aan met num - 1 totdat het basisgeval is bereikt.

Zo werkt het stap voor stap:

1. sum_recursive(3) roept sum_recursive(2) aan.
2. sum_recursive(2) roept sum_recursive(1) aan.
3. sum_recursive(1) retourneert 1 (basisgeval).
4. Nu kan sum_recursive(2) 2 + 1 = 3 retourneren en sum_recursive(3) 3 + 3 = 6.

Een ander voorbeeld is een recursieve functie om een macht te berekenen:

def power(base, exponent):
    if exponent == 0:  # Base case
        return 1
    else:
        return base * power(base, exponent - 1)  # Recursive case

print(power(2, 3))Mogelijk gemaakt door

8Mogelijk gemaakt door

Stap-voor-stap uitleg van deze machtfunctie:

• power(2, 3) roept power(2, 2) aan.
• power(2, 2) roept power(2, 1) aan.
• power(2, 1) roept power(2, 0) aan.
• power(2, 0) retourneert 1 (basisgeval).
• Terugwerkend: power(2, 1) retourneert 2 * 1 = 2.
• Dan retourneert power(2, 2) 2 * 2 = 4.
• Tot slot retourneert power(2, 3) 2 * 4 = 8.

Wanneer een recursieve functie wordt aangeroepen, creëert elke recursieve aanroep een nieuw item op de call stack. Deze stack houdt alle functieaanroepen en hun variabelen bij. Zodra het basisgeval is bereikt, werkt de stack de aanroepen in omgekeerde volgorde af en wordt het eindresultaat stap voor stap berekend.

Dit stackgedrag begrijpen is cruciaal, omdat het zowel de kracht als de beperkingen van recursie in Python verklaart. Het behoudt context op elegante wijze, maar kan ook tot geheugenproblemen leiden bij diepe recursie.

Factorial implementeren in Python met recursie

De faculteitsfunctie is een klassiek voorbeeld om recursie te demonstreren. De faculteit van een getal n, genoteerd als n!, is het product van alle positieve gehele getallen kleiner dan of gelijk aan n. Wiskundig:

n! = n × (n − 1) × (n − 2) × … × 1

Recursief kan de faculteit als volgt worden gedefinieerd:

n! = n × (n − 1)!

Laten we dit in Python implementeren:

def compute_factorial(num):
    if num == 0:  # Base case
        return 1
    return num * compute_factorial(num - 1)  # Recursive case

print(compute_factorial(4)) # 4 * 3 * 2 * 1Mogelijk gemaakt door

24Mogelijk gemaakt door

Stap-voor-stap uitleg van de code:

• De functie compute_factorial(num) controleert of num == 0 en retourneert in dat geval 1.
• Anders retourneert de functie num * compute_factorial(num - 1), waarbij de functie zichzelf aanroept met een kleinere waarde van num.

De faculteitsfunctie illustreert perfect de elegantie van recursie. De wiskundige definitie zelf is recursief, waardoor de code-implementatie intuïtief is en nauw aansluit bij het wiskundige concept. Dit is een van de krachten van recursie: code kan wiskundige definities rechtstreeks uitdrukken.

Het is de moeite waard om op randgevallen te letten. Zo is faculteit doorgaans alleen gedefinieerd voor niet-negatieve gehele getallen. Een robuuste implementatie kan foutafhandeling voor negatieve invoer of typecontroles bevatten. 

Bovendien kan de recursieve oplossing bij grote waarden van num tot een stack overflow leiden. Op die beperking ga ik later dieper in.

Veelvoorkomende problemen: recursiefouten in Python oplossen

Hoewel recursie een krachtig hulpmiddel kan zijn, is het gevoelig voor een paar veelvoorkomende problemen, zoals:

Maximale recursiediepte overschrijden

Python heeft een standaard recursielimiet van 1000 aanroepen. Als een recursieve functie zichzelf te vaak aanroept, wordt een RecursionError gegenereerd.

Zo los je het op:

Je kunt de recursiediepte verhogen met sys.setrecursionlimit(). Dit wordt echter niet aanbevolen tenzij het echt nodig is, omdat het tot een stack overflow kan leiden.

import sys  

# Get the current recursion limit
current_limit = sys.getrecursionlimit()
print(f'Current limit: {current_limit}')  

# Set a new recursion limit to 200
new_limit = 200
sys.setrecursionlimit(new_limit)  

# Get the new recursion limit
changed_current_limit = sys.getrecursionlimit()
print(f'Current limit after change: {changed_current_limit}')  Mogelijk gemaakt door

Current limit: 1000
Current limit after change: 200Mogelijk gemaakt door

Ontbrekend basisgeval

Een ontbrekend of verkeerd gedefinieerd basisgeval zorgt ervoor dat de functie oneindig recursief blijft, wat leidt tot een stack overflow.

Zorg ervoor dat je basisgeval duidelijk gedefinieerd en bereikbaar is.

Hoe stop je recursie in Python

De sleutel om recursie in Python te stoppen is een goed basisgeval te definiëren. Zonder dat eindigt de recursie nooit en resulteert dit in een fout.

In de faculteitsfunctie die ik eerder heb geïmplementeerd, was het basisgeval if num == 0, wat de recursie stopt. In het algemeen moet je ervoor zorgen dat elke recursieve functie een voorwaarde heeft waaronder deze beëindigt.

Effectieve basisgevallen ontwerpen vereist zorgvuldige afweging. Enkele richtlijnen:

• Identificeer de eenvoudigste versie van het probleem die je direct kunt oplossen.
• Zorg dat alle recursieve paden uiteindelijk een basisgeval bereiken.
• Test randgevallen apart om te controleren of ze correct worden afgehandeld.
• Overweeg meerdere basisgevallen als het probleem dat vereist.

Soms zijn defensieve programmeertechnieken handig, zoals extra controles op ongeldige invoer of runtime-checks om overmatige recursiediepte te voorkomen. Bijvoorbeeld:

def safe_factorial(num, depth=0, max_depth=100):
    # Check if recursion is too deep
    if depth > max_depth:
        raise ValueError("Maximum recursion depth exceeded")
   
    # Base case
    if num <= 0:
        return 1
   
    # Recursive case with depth tracking
    return num * safe_factorial(num - 1, depth + 1, max_depth)Mogelijk gemaakt door

# Calculate factorial of 5 with default depth limits
result = safe_factorial(5)

print(result) Mogelijk gemaakt door

120Mogelijk gemaakt door

# Calculate factorial of 5 with depth > max_depth
result = safe_factorial(5, depth=20, max_depth=10)

print(result) Mogelijk gemaakt door

ValueError: Maximum recursion depth exceededMogelijk gemaakt door

Met deze aanpak kun je eigen limieten instellen en betekenisvollere foutmeldingen geven dan de standaard RecursionError.

Hier is nog een voorbeeld dat een andere manier laat zien om basisgevallen te definiëren: het grootste gemene deler (ggd) van twee getallen vinden met recursie.

De ggd van twee getallen x en y kan worden berekend met het algoritme van Euclides, met de modulo-operator %:

• Basisgeval: als y == 0, dan is de ggd x.
• Recursief geval: anders is de ggd van x en y gelijk aan de ggd van y en x % y.

def find_gcd(x, y):
    # Base case: if y is 0, the GCD is x
    if y == 0:
        return x
    # Recursive case: GCD of y and x % y
    return find_gcd(y, x % y)

print(find_gcd(48, 18))  Mogelijk gemaakt door

6Mogelijk gemaakt door

Recursie vs. iteratie in Python

Zowel recursie als iteratie kunnen veel van dezelfde problemen oplossen, maar elk heeft z'n voor- en nadelen:

• Recursie is vaak eleganter en makkelijker te begrijpen, vooral bij problemen met een natuurlijke recursieve structuur (bijv. boomdoorloop, faculteiten, Fibonaccigetallen).
• Iteratie kan efficiënter zijn omdat het de overhead van meerdere functieaanroepen vermijdt en problemen met stack overflow voorkomt. Iteratieve oplossingen zijn meestal geheugen-efficiënter.

Wanneer recursie gebruiken:

• Wanneer het probleem zich natuurlijk laat opdelen in kleinere deelproblemen.
• Voor problemen met hiërarchische datastructuren, zoals bomen.
• Wanneer de recursieve oplossing intuïtiever is en leidt tot schonere code.
• Wanneer codeleesbaarheid belangrijker is dan prestatie-optimalisatie.
• Bij data met onbekende diepte (zoals het parsen van geneste JSON of XML).

Wanneer iteratie gebruiken:

• Bij problemen met herhalende taken zonder het probleem op te delen in kleinere deelproblemen.
• Voor prestatiekritische taken, waar diepe recursie tot hoog geheugengebruik kan leiden.
• Bij grote datasets die de recursielimiet kunnen overschrijden.
• Wanneer geheugengebruik een primaire zorg is.
• Bij problemen die van nature sequentieel zijn in plaats van hiërarchisch.

Laten we recursieve en iteratieve implementaties van hetzelfde probleem vergelijken: de som berekenen van de getallen van 1 tot num:

Recursief:

def sum_recursive(num):
    if num == 1:
        return 1
    else:
        return num + sum_recursive(num - 1)Mogelijk gemaakt door

Iteratief:

def iterative_sum(num):
    total = 0
    for i in range(1, num + 1):
        total += i
    return totalMogelijk gemaakt door

De iteratieve versie gebruikt een lus om de som op te bouwen, terwijl de recursieve versie het probleem opsplitst in het optellen van n bij de som van de getallen van 1 tot num - 1. Hoewel beide oplossingen werken, is de iteratieve versie efficiënter voor grote waarden van num, omdat er geen overhead is van meerdere functieaanroepen.

Sommige problemen die van nature recursief zijn, kun je omzetten naar iteratieve oplossingen door een stack of queue te gebruiken om de recursieve aanroepen te simuleren. Deze techniek is vooral nuttig bij boom- of graafdoorlopen.

Praktische voorbeelden van recursie in Python

Recursie kan op uiteenlopende interessante problemen worden toegepast:

1. Fibonaccigetallen berekenen

De Fibonacci-reeks is recursief gedefinieerd als:

• F(0) = 0
• F(1) = 1
• F(n) = F(n − 1) + F(n − 2)

Dit levert de volgende reeks op:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

Zo kun je het implementeren:

def compute_fibonacci(num):
    if num <= 0:
        return 0
    elif num == 1:
        return 1
    return compute_fibonacci(num - 1) + compute_fibonacci(num - 2)

print(compute_fibonacci(6))Mogelijk gemaakt door

8Mogelijk gemaakt door

Deze naïeve implementatie berekent waarden echter meerdere keren opnieuw. Een efficiëntere aanpak gebruikt memoization, waarbij eerder berekende resultaten (caching) worden opgeslagen om overbodige berekeningen te vermijden en de rekentijd aanzienlijk te verkorten:

def optimized_fibonacci(num, cache=None):
    if cache is None:
        cache = {}
    if num in cache:
        return cache[num]
    if num <= 1:
        return num
    cache[num] = optimized_fibonacci(num - 1, cache) + optimized_fibonacci(num - 2, cache)
    return cache[num]Mogelijk gemaakt door

Dit kan verder worden vereenvoudigd met de lru_cache()-decorator uit de module functools:

from functools import lru_cache

@lru_cache(maxsize=None)  # Cache all computed values
def cached_fibonacci(num):
    if num <= 1:
        return num
    return cached_fibonacci(num - 1) + cached_fibonacci(num - 2)Mogelijk gemaakt door

2. Geneste datastructuren doorlopen

Recursie is ook handig bij het werken met geneste datastructuren zoals lijsten van lijsten of JSON-objecten. Bijvoorbeeld bij het doorlopen van een mappenstructuur of het recursief "flattenen" van een geneste lijst.

def flatten(nested):
    result = []
    for element in nested:
        if isinstance(element, list):
            result.extend(flatten(element))
        else:
            result.append(element)
    return result

nested_structure = [1, [2, 3], [4, [5, 6]]]

print(flatten(nested_structure))  Mogelijk gemaakt door

[1, 2, 3, 4, 5, 6]Mogelijk gemaakt door

3. Sorteeralgoritmen (bijv. quicksort of merge sort) 

Sorteeralgoritmen zoals quicksort en merge sort leunen sterk op recursie. In deze algoritmen wordt het probleem opgedeeld in kleinere deelproblemen, die recursief worden gesorteerd.

Hier is een eenvoudige implementatie van quicksort:

def quicksort_algo(array):
    if len(array) <= 1:
        return array
    pivot = array[len(array) // 2]
    lower = [item for item in array if item < pivot]
    equal = [item for item in array if item == pivot]
    greater = [item for item in array if item > pivot]
    return quicksort_algo(lower) + equal + quicksort_algo(greater)

array = [220, 33, 400, 150, 16]

print(quicksort_algo(array))Mogelijk gemaakt door

[16, 33, 150, 220, 400]Mogelijk gemaakt door

Conclusie

Recursie is een krachtig concept in Python dat helpt complexe problemen op te lossen door ze op te delen in eenvoudigere deelproblemen. Correct toegepast leidt recursie tot schone, beknopte code die makkelijk te begrijpen is. 

Het is echter essentieel om goede basisgevallen te definiëren en rekening te houden met de recursiediepte om veelvoorkomende fouten te vermijden. 

Hoewel recursie soms minder efficiënt kan zijn dan iteratie, is het een onmisbaar hulpmiddel voor bepaalde soorten problemen, met name die met hiërarchische data of problemen die zich van nature lenen voor recursieve oplossingen.

Door recursie te begrijpen en te oefenen met voorbeelden zoals faculteiten, Fibonacci-reeksen en sorteeralgoritmen, ben je goed voorbereid om recursie in je Python-projecten te benutten.

Als je geïnteresseerd bent in meer gevorderde Python-onderwerpen waar je recursie kunt toepassen, bekijk dan de volgende leerroutes: Python Programming, Data Analyst in Python en Associate Data Scientist in Python