Wat is recursie?

Oefenen met coding-interviewvragen in Python

Kirill Smirnov

Data Science Consultant, Altran

Definitie

Recursie is het definiëren van een probleem in termen van zichzelf
Recursie is wanneer een functie zichzelf aanroept als subroutine

Voorbeeld: Faculteit $n!$

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1$

$n = 4$:

$4! = 4\cdot3\cdot2\cdot1$

4! = 24

Faculteit - Iteratieve aanpak

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1 = $

$ = 1\cdot2\cdot3\cdot...\cdot n$

Iteratieve oplossing:

# iterative factorial
def fact_iter(n):
    result = 1
    # looping over numbers from 1 to n
    for num in range(1, n+1)
        result = num * result

    return result

$n = 4:$

result = 1

result = 1 * result(1) = 1
result = 2 * result(1) = 2
result = 3 * result(2) = 6
result = 4 * result(4) = 24

$4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24$

Faculteit - Recursieve aanpak

$n!$ $=n\cdot(n-1)!$

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

Wat klopt er niet aan die code?

fact_rec(4)

RecursionError

We moeten een basisgeval definiëren!

$n! = n\cdot(n-1)\cdot(n-2)\cdot...\cdot1$

Een stopcriterium / basisgeval: $1! = 1$

def fact_rec(n):
    if n == 1:
        return 1
    return n * fact_rec(n-1)

fact_rec(4)

Afronden

Recursieve functies hebben twee hoofdonderdelen:

een recursieve aanroep naar een kleiner subprobleem
een basisgeval dat een oneindige lus voorkomt

Voorbeeld - Beslissingsbomen

Beslissingsboom

Classificatie met de beslissingsboom

Een beslissingsboom doorlopen

De beslissingsboom doorlopen

x - een nieuwe sample $(x_1, x_2)$

# Pseudo-algoritme om de categorie te vinden:

category = pred(node, x):

  # Check of er een splitsing is  
  if node.hasSplitting:

    # Bepaal naar welk kind je gaat
    if node.goToLeftChild(x):
      return pred(node.leftChild, x)   
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

Een beslissingsboom doorlopen

Voorspellen met de beslissingsboom

x - een nieuwe sample $(x_1, x_2)$

# Pseudo-algoritme om de categorie te vinden:

category = pred(node, x):

  # Check of er een splitsing is  
  if node.hasSplitting:

    # Bepaal naar welk kind je gaat
    if node.goToLeftChild(x):
      return pred(node.leftChild, x) 
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

  # Categorie retourneren
  return node.category

Laten we oefenen!

Oefenen met coding-interviewvragen in Python