Scala voor backend-engineering en functioneel programmeren · Les

Recursief denken

Basisgevallen en recursieve stappen.

Les 1 van 413 stappen

Recursief denken is een gratis Scala voor backend-engineering en functioneel programmeren-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 Scala voor backend-engineering en functioneel programmeren. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Scala voor backend-engineering en functioneel programmeren bevat in totaal 4 lessen.

Wat recursie betekent

Recursie betekent dat een functie zichzelf aanroept om een kleinere versie van hetzelfde probleem op te lossen.

In Scala past recursie goed bij functioneel programmeren, omdat je er lussen mee kunt uitdrukken zonder veranderlijke variabelen.

Elke recursieve functie heeft twee dingen nodig: een manier om te stoppen en een manier om het probleem kleiner te maken.

Eerst het basisgeval

Het basisgeval is de eenvoudigste invoer die de functie rechtstreeks kan beantwoorden, zonder verdere recursie.

Zonder basisgeval zou de functie zichzelf voor altijd aanroepen en crashen door een stackoverloop.

Ontwerp het basisgeval altijd vóór de recursieve stap.

def countdown(n: Int): Unit =
  if (n < 0) ()           // base case: stop
  else {
    println(n)
    countdown(n - 1)      // recursive step
  }

Een eerste recursieve functie

Hier staat een compleet programma dat de getallen van 1 tot en met n optelt.

Het basisgeval retourneert 0; het recursieve geval telt n op bij de som van alles daaronder.

def sum(n: Int): Int =
  if (n == 0) 0
  else n + sum(n - 1)

@main def run(): Unit =
  println(sum(5))   // 15

De aanroepen volgen

Om recursie te begrijpen, schrijf je de aanroepen met de hand uit.

sum(3) wordt 3 + sum(2), dat 3 + 2 + sum(1) wordt, en daarna 3 + 2 + 1 + sum(0).

Pas wanneer sum(0) 0 retourneert, klapt de keten terug tot één waarde: 6.

// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6

Recursie op lijsten

Lijsten zijn van nature recursief: een lijst is leeg (Nil) of bestaat uit een kop en een kleinere staart.

Deze vorm sluit rechtstreeks aan op recursieve functies. De lege lijst is het basisgeval; de kop plus recursie op de staart vormt de recursieve stap.

def length[A](xs: List[A]): Int = xs match {
  case Nil     => 0
  case _ :: t  => 1 + length(t)
}

De staart matchen met patronen

Het patroon :: splitst een niet-lege lijst op in zijn kop en staart.

Elke recursieve aanroep werkt met een strikt kortere lijst, waardoor voortgang richting Nil gegarandeerd is.

Dit is de standaardmanier om in Scala recursief door een lijst te lopen.

def sumList(xs: List[Int]): Int = xs match {
  case Nil    => 0
  case h :: t => h + sumList(t)
}

@main def run(): Unit =
  println(sumList(List(1, 2, 3, 4)))  // 10

Twee recursieve aanroepen

Sommige problemen vertakken zich in meer dan één recursieve aanroep.

Het klassieke voorbeeld is Fibonacci, waarbij elke waarde afhangt van de twee voorgaande waarden.

Deze naïeve versie is eenvoudig maar traag, omdat dezelfde waarden vele malen opnieuw worden berekend.

def fib(n: Int): Int =
  if (n < 2) n
  else fib(n - 1) + fib(n - 2)

@main def run(): Unit =
  println(fib(7))   // 13

De kosten voor de stack

Elke recursieve aanroep voegt een frame toe aan de aanroepstack, dat moet wachten tot de innerlijke aanroep terugkeert.

Bij zeer diepe recursie kan de stack vollopen en een StackOverflowError ontstaan.

Als je de diepte telt, en niet alleen de omvang, kun je dit risico voorspellen.

// This would overflow the stack for large n:
// def deep(n: Int): Int =
//   if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000)  // StackOverflowError

Naar het basisgeval toe verkleinen

De belangrijkste invariant van recursie is dat elke aanroep dichter bij het basisgeval moet komen.

Als het argument niet kleiner wordt of de stopvoorwaarde nooit bereikt, eindigt de recursie niet.

Controleer dit voordat je iets uitvoert.

def reverse[A](xs: List[A]): List[A] = xs match {
  case Nil    => Nil
  case h :: t => reverse(t) :+ h   // t is smaller than xs
}

Recursie versus lussen

Imperatieve code gebruikt while-lussen met veranderlijke tellers; functionele code gebruikt recursie met onveranderlijke waarden.

Beide kunnen dezelfde berekeningen uitdrukken, maar recursie beschrijft de structuur van de gegevens directer.

In Scala geef je vaak de voorkeur aan recursie of functies van hogere orde boven gewone lussen.

// Imperative
var total = 0
for (i <- 1 to 5) total += i

// Recursive
def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)

Een recursieve oplossing ontwerpen

Een betrouwbaar recept: bepaal het basisgeval, neem aan dat de recursieve aanroep al werkt op de kleinere invoer en combineer vervolgens de kop met dat resultaat.

Deze sprong in vertrouwen vormt de kern van recursief denken. Je vertrouwt op de kleinere aanroep en behandelt slechts één stap.

def maxOf(xs: List[Int]): Int = xs match {
  case h :: Nil => h
  case h :: t   => math.max(h, maxOf(t))
}

@main def run(): Unit =
  println(maxOf(List(3, 9, 2, 7)))  // 9

Korte controle

Test je inzicht in recursieve structuren.

Beantwoord dit in de interactieve les

Samenvatting

Recursie lost een probleem op door het te herleiden tot een kleinere instantie van zichzelf.

Elke recursieve functie heeft een basisgeval nodig om te stoppen en een recursieve stap die de invoer naar dat basisgeval toe verkleint.

Lijsten, met hun Nil- en kop-staartstructuur, zijn ideaal om recursief denken te oefenen. Let bij zeer grote invoer op de stackdiepte.

Gratis beginnen

Leer Scala 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: 39
Lessen: 143

Gratis beginnen met leren Bekijk de volledige cursus

Veelgestelde vragen

Is de les “Recursief denken” gratis?

Ja — de volledige tekst van “Recursief denken” 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 Scala voor backend-engineering en functioneel programmeren wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Scala voor backend-engineering en functioneel programmeren bevat in totaal 4 lessen.

Wat leer ik in “Recursief denken”?

Basisgevallen en recursieve stappen. Je oefent met Scala voor backend-engineering en functioneel programmeren 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 Scala voor backend-engineering en functioneel programmeren te beginnen?

Ervaring vooraf is niet nodig. Scala voor backend-engineering en functioneel programmeren 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 “Recursief denken”?

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 Scala voor backend-engineering en functioneel programmeren?

Ja. Elke les over Scala voor backend-engineering en functioneel programmeren 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

← Terug naar Scala voor backend-engineering en functioneel programmeren