Recursieframework: basisgeval, vertrouwen, opbouw
Pas de methode in drie stappen toe om correcte recursieve oplossingen voor faculteit, macht en som van cijfers te schrijven zonder elke aanroep te traceren.
Recursieframework: basisgeval, vertrouwen, opbouw is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Waarom recursie moeilijk aanvoelt
De meeste beginners proberen elke recursieve aanroep in gedachten te volgen, waardoor zelfs recursie met vijf niveaus al snel overweldigend wordt. De professionele aanpak gebruikt een drie stappen tellend raamwerk — basisgeval, vertrouwen en opbouw — waarmee je correcte recursieve functies kunt schrijven zonder de volledige aanroepboom in gedachten te simuleren.
Dit raamwerk wordt soms de sprong in het diepe genoemd: je vertrouwt erop dat je functie werkt voor kleinere invoer en gebruikt die aanname om de oplossing voor grotere invoer op te bouwen.
Stap 1: Definieer het basisgeval
Het basisgeval is de eenvoudigste invoer waarvoor het antwoord bekend is zonder verdere recursie. Elke recursieve functie moet minstens één basisgeval hebben; zonder basisgeval recursieert de functie oneindig (stackoverloop). Goede basisgevallen zijn: een lege lijst, één element, n == 0, n == 1, of een probleem dat herleidt tot een triviale identiteit.
Schrijf het basisgeval eerst, vóór de recursieve logica. Bepaal het door te vragen: 'Wat is de kleinste versie van dit probleem die ik direct kan beantwoorden?'
# Base cases for common problems
def factorial(n):
if n == 0: # base case: 0! = 1
return 1
# ... recursive step below
def sum_list(lst):
if not lst: # base case: sum of empty list is 0
return 0
# ...
def height(node):
if node is None: # base case: height of null node is 0
return 0
# ...
print('Base cases identified')Stap 2: Vertrouw op de recursieve aanroep
De stap van vertrouwen is de sprong in het diepe: neem aan dat je functie al correct werkt voor elke invoer die strikt kleiner is dan de huidige invoer. Je hoeft dat nu niet voor elke kleinere invoer te bewijzen — het inductieve bewijs garandeert dit. Roep je functie gewoon aan voor het kleinere deelprobleem en vertrouw erop dat de juiste uitkomst wordt geretourneerd.
Beginners slaan deze stap vaak over en proberen in plaats daarvan alles mentaal te simuleren. Weersta die neiging; zodra je het raamwerk beheerst, werkt het ook voor recursie met een willekeurig grote diepte.
# Trust example: sum_list([3, 1, 4, 1, 5])
# Trust: sum_list([1, 4, 1, 5]) = 11 (we TRUST this, don't trace it)
# Build: 3 + 11 = 14
# So:
def sum_list(lst):
if not lst:
return 0
# Trust that sum_list(lst[1:]) returns sum of the rest
return lst[0] + sum_list(lst[1:])
print(sum_list([3, 1, 4, 1, 5])) # 14Stap 3: Bouw de oplossing
Bij de stap van opbouwen combineer je het vertrouwde resultaat van het deelprobleem met de bijdrage van het huidige element om het antwoord voor de volledige invoer te produceren. Dit is meestal één regel: pas een bewerking toe op het huidige element en het resultaat van de recursieve aanroep. Veelvoorkomende manieren om op te bouwen zijn: iets optellen bij een som, iets vooraan een lijst toevoegen, een teller verhogen of twee deelresultaten combineren.
def factorial(n):
if n == 0:
return 1
# Trust: factorial(n-1) gives (n-1)!
# Build: n * (n-1)! = n!
return n * factorial(n - 1)
def power(base, exp):
if exp == 0:
return 1
# Trust: power(base, exp-1) gives base^(exp-1)
# Build: base * base^(exp-1) = base^exp
return base * power(base, exp - 1)
print(factorial(6)) # 720
print(power(2, 10)) # 1024Het raamwerk toepassen op de som van cijfers
Probleem: bereken de som van de cijfers van een niet-negatief geheel getal. Basisgeval: n == 0 → de som is 0 (of n < 10 → n zelf). Vertrouwen: sumDigits(n // 10) retourneert de som van alle cijfers behalve het laatste. Opbouwen: tel het laatste cijfer n % 10 op bij het vertrouwde resultaat. Het raamwerk levert de oplossing in drie declaratieve stappen.
def sumDigits(n):
if n < 10:
return n # base case: single digit
# Trust: sumDigits(n // 10) gives sum of all digits except last
# Build: add the last digit
return n % 10 + sumDigits(n // 10)
print(sumDigits(0)) # 0
print(sumDigits(7)) # 7
print(sumDigits(123)) # 6
print(sumDigits(9999)) # 36Fibonacci: twee deelproblemen
Voor Fibonacci zijn twee recursieve aanroepen nodig: fib(n-1) en fib(n-2). Pas het raamwerk toe: de basisgevallen zijn fib(0) = 0 en fib(1) = 1. Vertrouwen: beide kleinere aanroepen retourneren de juiste Fibonacci-waarden. Opbouwen: retourneer hun som. Deze naïeve implementatie heeft een tijdscomplexiteit van O(2^n) — dat lossen we op in de les over memoisatie.
def fib(n):
if n <= 1:
return n # base cases: fib(0)=0, fib(1)=1
# Trust both smaller sub-problems
return fib(n - 1) + fib(n - 2)
for i in range(8):
print(f'fib({i}) = {fib(i)}') # 0,1,1,2,3,5,8,13Een tekenreeks recursief omkeren
Probleem: keer een tekenreeks recursief om. Basisgeval: een lege tekenreeks of één teken — die is al omgekeerd. Vertrouwen: reverse(s[1:]) retourneert de omgekeerde versie van alles na het eerste teken. Opbouwen: voeg het eerste teken achteraan de omgekeerde achtervoegselreeks toe. Het raamwerk levert een oplossing van drie regels.
def reverse_str(s):
if len(s) <= 1:
return s # base case
# Trust: reverse_str(s[1:]) = reverse of 'ello' for 'hello'
# Build: append first character at end
return reverse_str(s[1:]) + s[0]
print(reverse_str('')) # ''
print(reverse_str('a')) # 'a'
print(reverse_str('hello')) # 'olleh'
print(reverse_str('racecar')) # 'racecar'Recursief voorkomens tellen
Probleem: tel recursief hoe vaak een doelwaarde in een lijst voorkomt. Basisgeval: een lege lijst — de teller staat op 0. Vertrouwen: count(lst[1:], target) retourneert het aantal voorkomens in de staart. Opbouwen: tel 1 op als het eerste element overeenkomt met de doelwaarde, en anders 0. Elke recursieve stap boekt vooruitgang naar het basisgeval door de lijst één element korter te maken.
def count_occurrences(lst, target):
if not lst:
return 0
# Trust: count in rest of list is handled recursively
# Build: add 1 if first element matches, else 0
return (1 if lst[0] == target else 0) + count_occurrences(lst[1:], target)
print(count_occurrences([1, 2, 3, 2, 4, 2], 2)) # 3
print(count_occurrences([], 5)) # 0
print(count_occurrences([7, 7, 7], 7)) # 3Controleren of een lijst gesorteerd is
Probleem: controleer recursief of een lijst in oplopende volgorde is gesorteerd. Basisgeval: een lijst met 0 of 1 elementen is altijd gesorteerd. Vertrouwen: is_sorted(lst[1:]) vertelt je of de staart gesorteerd is. Opbouwen: de lijst is gesorteerd als het eerste element <= het tweede is EN de staart gesorteerd is. Dit is een duidelijk voorbeeld waarin de stap van het opbouwen een logische EN van twee voorwaarden gebruikt.
def is_sorted(lst):
if len(lst) <= 1:
return True
# Trust: is_sorted(lst[1:]) tells us if tail is sorted
# Build: head <= second element AND tail is sorted
return lst[0] <= lst[1] and is_sorted(lst[1:])
print(is_sorted([])) # True
print(is_sorted([1])) # True
print(is_sorted([1, 2, 3, 4])) # True
print(is_sorted([1, 3, 2, 4])) # FalseBinair zoeken met recursie (opnieuw bekeken)
Binair zoeken uitgedrukt met recursie via het raamwerk: basisgeval: lo > hi → niet gevonden (return -1). Vertrouwen: de recursieve aanroep voor de juiste helft vindt de doelwaarde of retourneert -1. Opbouwen: bereken mid, vergelijk en roep de juiste helft aan. De recursieve vorm laat de verdeel-en-heersstructuur duidelijk zien, hoewel in productie de iteratieve vorm de voorkeur heeft vanwege O(1) ruimtegebruik.
def binary_search(arr, target, lo, hi):
if lo > hi: # base case: search space exhausted
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
# Trust both halves return correct results
if arr[mid] < target:
return binary_search(arr, target, mid + 1, hi)
else:
return binary_search(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr) - 1)) # 3
print(binary_search(arr, 4, 0, len(arr) - 1)) # -1Wanneer recursie en wanneer iteratie gebruiken
Recursie is uitstekend wanneer het probleem zich van nature opsplitst in kleinere deelproblemen van hetzelfde type (bomen, verdeel-en-heersalgoritmen, terugzoeken). Iteratie heeft de voorkeur wanneer: de recursiediepte groot is (waardoor in Python stackoverloop dreigt, omdat de standaardlimiet ongeveer 1000 is), de recursieve en iteratieve versies even duidelijk zijn, of het probleem een eenvoudige lus is (factorial, Fibonacci zonder memoisatie).
Een goede vuistregel: als het tekenen van een recursieboom natuurlijk aanvoelt, gebruik dan recursie. Als de boom een rechte lijn is (staartrecursie), zet die dan om in iteratie.
import sys
# Python's default recursion limit
print('Recursion limit:', sys.getrecursionlimit()) # 1000
# A list of 2000 elements would overflow the recursive sum_list
# Use iteration for safety:
def sum_list_iter(lst):
total = 0
for x in lst:
total += x
return total
big = list(range(2000))
print(sum_list_iter(big)) # 1999000 — no stack overflowKorte controle
Test je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep van deze les.
Samenvatting van de les
In deze les heb je geleerd: het driedelige raamwerk bestaat uit Basisgeval (eenvoudigst bekende antwoord), Vertrouwen (neem aan dat het deelprobleem is opgelost) en Opbouwen (combineer het huidige element met het vertrouwde resultaat), schrijf basisgevallen eerst en probeer niet de volledige aanroepbomen mentaal te volgen, en gebruik iteratie wanneer de recursiediepte tot stackoverloop kan leiden of wanneer de recursieve en iteratieve vormen even duidelijk zijn. Hierna visualiseren we de aanroepstack in detail.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Recursieframework: basisgeval, vertrouwen, opbouw” gratis?
Ja — de volledige tekst van “Recursieframework: basisgeval, vertrouwen, opbouw” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Recursieframework: basisgeval, vertrouwen, opbouw”?
Pas de methode in drie stappen toe om correcte recursieve oplossingen voor faculteit, macht en som van cijfers te schrijven zonder elke aanroep te traceren. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “Recursieframework: basisgeval, vertrouwen, opbouw”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Recursieframework: basisgeval, vertrouwen, opbouw
- De call stack visualiseren
- Afwegingen tussen recursief en iteratief
- Memoisation: recursieve resultaten cachen