Recursie begrijpen

Datastructuren en algoritmen in Python

Miriam Antona

Software engineer

Definitie

Functie die zichzelf aanroept
Bijna alle situaties waar we lussen gebruiken
- lussen vervangen door recursie
Kan problemen oplossen die eerst heel complex lijken

Voorbeeld - faculteit

$n!$

Voorbeeld - faculteit

$n!=n$ · $(n-1)$ · $(n-2)$ · $...$ · $1$

$5!=$ $5$ · $4$ · $3$ · $2$ · $1=120$

def factorial(n):
  result = 1
  while n > 1:
    result = n * result
    n -= 1
  return result

factorial(5)

Voorbeeld - faculteit met recursie

$n!= n$ · $(n-1)!$

def factorial_recursion(n):
  return n * factorial_recursion(n-1)

Draait eindeloos!

Voorbeeld - basisgeval bepalen

Voeg een voorwaarde toe
- zorgt dat het algoritme niet eindeloos draait
Factorial basisgeval -> $n=1$

def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

Hoe recursie werkt

De computer gebruikt een stack om functies bij te houden
- Call stack

Hoe recursie werkt

factorial(5) start
Voor factorial(5) klaar is -> factorial(4) start
Voor factorial(4) klaar is -> factorial(3) start

Een afbeelding van een wachtrij met één element dat een functie voorstelt.

Hoe recursie werkt

factorial(5) start
Voor factorial(5) klaar is -> factorial(4) start
Voor factorial(4) klaar is -> factorial(3) start
Voor factorial(3) klaar is -> factorial(2) start

Een afbeelding van een wachtrij met twee elementen die twee functies voorstellen.

Hoe recursie werkt

factorial(5) start
Voor factorial(5) klaar is -> factorial(4) start
Voor factorial(4) klaar is -> factorial(3) start
Voor factorial(3) klaar is -> factorial(2) start
Voor factorial(2) klaar is -> factorial(1) start

Een afbeelding van een wachtrij met drie elementen die drie functies voorstellen.

Hoe recursie werkt

factorial(5) start
Voor factorial(5) klaar is -> factorial(4) start
Voor factorial(4) klaar is -> factorial(3) start
Voor factorial(3) klaar is -> factorial(2) start
Voor factorial(2) klaar is -> factorial(1) start

Een afbeelding van een wachtrij met vier elementen die vier functies voorstellen.

Hoe recursie werkt

factorial(1) eindigt
- geeft 1 terug
factorial(2) eindigt

Een afbeelding van een wachtrij met vier elementen die vier functies voorstellen.

Hoe recursie werkt

factorial(1) eindigt
- geeft 1 terug
factorial(2) eindigt
- geeft 2 terug

Een afbeelding van een wachtrij met vier elementen die vier functies voorstellen. De laatste functie gaat vergezeld van zijn geretourneerde waarde.

Hoe recursie werkt

factorial(1) eindigt
- geeft 1 terug
factorial(2) eindigt
- geeft 2 terug
factorial(3) eindigt
- geeft 6 terug

Een afbeelding van een wachtrij met drie elementen die drie functies voorstellen.

Hoe recursie werkt

factorial(1) eindigt
- geeft 1 terug
factorial(2) eindigt
- geeft 2 terug
factorial(3) eindigt
- geeft 6 terug
factorial(4) eindigt
- geeft 24 terug

Een afbeelding van een wachtrij met twee elementen die twee functies voorstellen.

Hoe recursie werkt

factorial(1) eindigt
- geeft 1 terug
factorial(2) eindigt
- geeft 2 terug
factorial(3) eindigt
- geeft 6 terug
factorial(4) eindigt
- geeft 24 terug
factorial(5) eindigt
- geeft 120 terug

Een afbeelding van een wachtrij met één element dat één functie voorstelt.

Hoe recursie werkt

factorial(1) eindigt
- geeft 1 terug
factorial(2) eindigt
- geeft 2 terug
factorial(3) eindigt
- geeft 6 terug
factorial(4) eindigt
- geeft 24 terug
factorial(5) eindigt
- geeft 120 terug

Een afbeelding van een lege wachtrij.

Dynamisch programmeren

Optimalisatietechniek
Vooral toegepast op recursie
Kan de complexiteit van recursieve algoritmen verlagen
Gebruikt voor:
- Elk probleem dat in kleinere subproblemen te delen is
- Subproblemen overlappen
Oplossingen van subproblemen worden opgeslagen om herberekening te vermijden
- Memoization

Laten we oefenen!

Datastructuren en algoritmen in Python