Recursie en backtracking
Recursie - De Basis
Een recursieve functie roept zichzelf aan met een kleinere versie van het probleem, totdat het een basisgeval bereikt dat de keten stopt.
Elke recursie heeft twee dingen nodig:
- Basisgeval - de eenvoudigste invoer waarbij je direct retourneert.
- Recursief geval - splits het probleem op en roep jezelf aan.
def factorial(n):
if n <= 1: # basisgeval
return 1
return n * factorial(n - 1) # recursief geval
De Call Stack - Gevisualiseerd
Elke recursieve aanroep pusht een frame op de call stack. Wanneer het basisgeval retourneert, worden frames in omgekeerde volgorde ge-popt.
factorial(4)
→ factorial(3)
→ factorial(2)
→ factorial(1) → geeft 1 terug
← geeft 2 terug
← geeft 6 terug
← geeft 24 terug
Als er geen basisgeval is, loopt de stack over. Python's standaard recursielimiet is 1.000 frames.
Fibonacci - De Klassieke Valkuil
De naïeve recursieve Fibonacci is O(2ⁿ) omdat het dezelfde deelproblemen herberekent. Memoisatie lost dit op in O(n) tijd en ruimte.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
Backtracking - Probeer Alles, Maak dan Ongedaan
Backtracking is recursie met een twist: je maakt een keuze, recurseert, en maakt de keuze ongedaan voordat je de volgende optie probeert. Zie het als het verkennen van een doolhof - loop vooruit, loop vast, loop terug, probeer het volgende pad.
Het Backtracking-Sjabloon
def backtrack(state, choices):
if is_solution(state):
result.append(state.copy())
return
for choice in choices:
if is_valid(choice):
state.add(choice) # kies
backtrack(state, ...) # verken
state.remove(choice) # maak ongedaan
Dit drieledige patroon - kiezen, verkennen, ongedaan maken - is de ruggengraat van vrijwel elk backtracking-probleem.
Discussie
Inloggen deelnemen aan de discussie