Comprendre la récursivité

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Définition

  • Fonction qui s’appelle elle-même
  • Presque tous les cas où l’on utilise des boucles
    • remplacer les boucles par la récursivité
  • Permet de résoudre des problèmes qui semblent complexes au départ
Structures de données et algorithmes en Python

Exemple - factoriel

$n!$

Structures de données et algorithmes en Python

Exemple - factoriel

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

120
Structures de données et algorithmes en Python

Exemple - factoriel récursif

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

def factorial_recursion(n):
  return n * factorial_recursion(n-1)
  • S’exécute indéfiniment !
Structures de données et algorithmes en Python

Exemple - identifier le cas de base

  • Ajouter une condition
    • garantit que l’algorithme ne s’exécute pas indéfiniment
  • Cas de base du factoriel -> $n=1$
def factorial_recursion(n):
  if n == 1:

    return 1

  else:

    return n * factorial_recursion(n-1)

print(factorial_recursion(5))

120
Structures de données et algorithmes en Python

Fonctionnement de la récursivité

  • L’ordinateur utilise une pile pour suivre les fonctions
    • Pile d’appels
Structures de données et algorithmes en Python

Fonctionnement de la récursivité

  • factorial(5) démarre
  • Avant la fin de factorial(5) -> factorial(4) démarre
  • Avant la fin de factorial(4) -> factorial(3) démarre

Image d’une file avec un élément représentant une fonction.

Structures de données et algorithmes en Python

Fonctionnement de la récursivité

  • factorial(5) démarre
  • Avant la fin de factorial(5) -> factorial(4) démarre
  • Avant la fin de factorial(4) -> factorial(3) démarre
  • Avant la fin de factorial(3) -> factorial(2) démarre

Image d’une file avec deux éléments représentant deux fonctions.

Structures de données et algorithmes en Python

Fonctionnement de la récursivité

  • factorial(5) démarre
  • Avant la fin de factorial(5) -> factorial(4) démarre
  • Avant la fin de factorial(4) -> factorial(3) démarre
  • Avant la fin de factorial(3) -> factorial(2) démarre
  • Avant la fin de factorial(2) -> factorial(1) démarre

Image d’une file avec trois éléments représentant trois fonctions.

Structures de données et algorithmes en Python

Fonctionnement de la récursivité

  • factorial(5) démarre
  • Avant la fin de factorial(5) -> factorial(4) démarre
  • Avant la fin de factorial(4) -> factorial(3) démarre
  • Avant la fin de factorial(3) -> factorial(2) démarre
  • Avant la fin de factorial(2) -> factorial(1) démarre

Image d’une file avec quatre éléments représentant quatre fonctions.

Structures de données et algorithmes en Python

Fonctionnement de la récursivité

  • factorial(1) se termine
    • renvoie 1
  • factorial(2) se termine

Image d’une file avec quatre éléments représentant quatre fonctions.

Structures de données et algorithmes en Python

Fonctionnement de la récursivité

  • factorial(1) se termine
    • renvoie 1
  • factorial(2) se termine
    • renvoie 2

Image d’une file avec quatre éléments représentant quatre fonctions. La dernière fonction est accompagnée de sa valeur de retour.

Structures de données et algorithmes en Python

Fonctionnement de la récursivité

  • factorial(1) se termine
    • renvoie 1
  • factorial(2) se termine
    • renvoie 2
  • factorial(3) se termine
    • renvoie 6

Image d’une file avec trois éléments représentant trois fonctions.

Structures de données et algorithmes en Python

Fonctionnement de la récursivité

  • factorial(1) se termine
    • renvoie 1
  • factorial(2) se termine
    • renvoie 2
  • factorial(3) se termine
    • renvoie 6
  • factorial(4) se termine
    • renvoie 24

Image d’une file avec deux éléments représentant deux fonctions.

Structures de données et algorithmes en Python

Fonctionnement de la récursivité

  • factorial(1) se termine
    • renvoie 1
  • factorial(2) se termine
    • renvoie 2
  • factorial(3) se termine
    • renvoie 6
  • factorial(4) se termine
    • renvoie 24
  • factorial(5) se termine
    • renvoie 120

Image d’une file avec un élément représentant une fonction.

Structures de données et algorithmes en Python

Fonctionnement de la récursivité

  • factorial(1) se termine
    • renvoie 1
  • factorial(2) se termine
    • renvoie 2
  • factorial(3) se termine
    • renvoie 6
  • factorial(4) se termine
    • renvoie 24
  • factorial(5) se termine
    • renvoie 120

Image d’une file vide.

Structures de données et algorithmes en Python

Programmation dynamique

  • Technique d’optimisation
  • Principalement appliquée à la récursivité
  • Peut réduire la complexité des algorithmes récursifs
  • Utilisée pour :
    • tout problème divisible en sous-problèmes plus petits
    • sous-problèmes qui se recouvrent
  • Les solutions des sous-problèmes sont mémorisées, évitant de recalculer
    • Mémoïsation
Structures de données et algorithmes en Python

Passons à la pratique !

Structures de données et algorithmes en Python

Preparing Video For Download...