Qu'est-ce que la récursivité ?

S'entraîner aux questions d'entrevue de programmation en Python

Kirill Smirnov

Data Science Consultant, Altran

Définition

La récursivité consiste à définir un problème en fonction de lui-même
C'est un procédé où une fonction s'appelle elle-même comme sous-routine

Exemple : factorielle $n!$

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

$n = 4$ :

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

4! = 24

Factorielle – approche itérative

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

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

Solution itérative :

# 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$

Factorielle – approche récursive

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

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

Quel est le problème avec ce code ?

fact_rec(4)

RecursionError

Il faut définir un cas de base !

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

Un critère d'arrêt / cas de base : $1! = 1$

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

fact_rec(4)

En résumé

Les fonctions récursives ont deux composantes principales :

un appel récursif à une version plus petite du problème
un cas de base qui évite un appel infini

Exemple – arbres de décision

Arbre de décision

Classification à l'aide de l'arbre de décision

Parcourir un arbre de décision

Parcours de l'arbre de décision

x – un nouvel échantillon $(x_1, x_2)$

# Pseudo-algorithme pour trouver la catégorie :

category = pred(node, x):

  # Vérifier s'il y a une division
  if node.hasSplitting:

    # Déterminer quel nœud enfant prendre
    if node.goToLeftChild(x):
      return pred(node.leftChild, x)   
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

Parcourir un arbre de décision

Prédiction avec l'arbre de décision

x – un nouvel échantillon $(x_1, x_2)$

# Pseudo-algorithme pour trouver la catégorie :

category = pred(node, x):

  # Vérifier s'il y a une division
  if node.hasSplitting:

    # Déterminer quel nœud enfant prendre
    if node.goToLeftChild(x):
      return pred(node.leftChild, x) 
    if node.goToRightChild(x):
      return pred(node.rightChild, x)

  # Retourner la catégorie
  return node.category

Passons à la pratique !

S'entraîner aux questions d'entrevue de programmation en Python