👀 Voorbeeld - Recursie als algoritmische techniek

Farah en Ferre hebben een gekke doos gevonden op school. Op de doos staat de volgende boodschap:

Vanbinnen in mij bevinden zich gekleurde dozen maar ik wil enkel weten hoeveel dozen een stip hebben met dezelfde kleur stip als de kleinste doos helemaal vanbinnen.

Farah en Ferre zoeken op de buitenste doos naar een stip. Ze vinden een rode stip en schrijven met dikke stift ‘ROOD’ op de zijkant. Dan openen ze de doos en vinden ze een andere doos vanbinnen met een blauwe stip. Dit doen ze totdat ze bij de laatste doos komen. Deze doos heeft een grote blauwe stip op de binnenkant van een zijwand staan. Ze beginnen nu te tellen:

1. Deze kleine doos is de eerste doos met een blauwe stip.
2. Dan kijken ze naar de doos die ze net openmaakten. Deze doos heeft een zwarte stip. Het aantal dozen met een blauwe stip blijft dus 1.
3. Zo keren ze helemaal terug naar de buitenste doos en komen ze aan het getal 4.

Wanneer ze wat beter naar de doos kijken die ze als vierde openden, vinden ze dat er een snoepje aan vasthangt. Wat een avontuur!

Farah en Ferre gebruikten hier, zonder dat ze het doorhadden, recursie.

Ze openden steeds de doos die net kleiner was dan de andere doos. Ze pasten dus dezelfde regel toe op een kleiner probleem. Uiteindelijk was er een doos waarvan ze wisten of ze hem moesten tellen of niet (de kleinste doos). En hierdoor konden ze terug door elke al geopende doos zich naar buiten werken zodat het probleem was opgelost.

❗ Begrip – Recursie

Bij recursie lost een algoritme een probleem op door zichzelf toe te passen op een kleiner deelprobleem, totdat een basisgeval bereikt wordt dat direct opgelost kan worden.