Comprendre la récursion

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 emploie des boucles
    • remplacer les boucles par la récursion
  • Peut résoudre des problèmes qui semblent très complexes au départ
Structures de données et algorithmes en Python

Exemple - factorielle

$n!$

Structures de données et algorithmes en Python

Exemple - factorielle

$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 - factorielle avec récursion

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

def factorial_recursion(n):
  return n * factorial_recursion(n-1)
  • S'exécute à l'infini !
Structures de données et algorithmes en Python

Exemple - repérer le cas de base

  • Ajouter une condition
    • pour éviter une exécution infinie
  • Cas de base de la factorielle -> $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écursion

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

Fonctionnement de la récursion

  • factorial(5) démarre
  • Avant que factorial(5) se termine -> factorial(4) démarre
  • Avant que factorial(4) se termine -> 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écursion

  • factorial(5) démarre
  • Avant que factorial(5) se termine -> factorial(4) démarre
  • Avant que factorial(4) se termine -> factorial(3) démarre
  • Avant que factorial(3) se termine -> 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écursion

  • factorial(5) démarre
  • Avant que factorial(5) se termine -> factorial(4) démarre
  • Avant que factorial(4) se termine -> factorial(3) démarre
  • Avant que factorial(3) se termine -> factorial(2) démarre
  • Avant que factorial(2) se termine -> 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écursion

  • factorial(5) démarre
  • Avant que factorial(5) se termine -> factorial(4) démarre
  • Avant que factorial(4) se termine -> factorial(3) démarre
  • Avant que factorial(3) se termine -> factorial(2) démarre
  • Avant que factorial(2) se termine -> 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écursion

  • factorial(1) se termine
    • retourne 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écursion

  • factorial(1) se termine
    • retourne 1
  • factorial(2) se termine
    • retourne 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écursion

  • factorial(1) se termine
    • retourne 1
  • factorial(2) se termine
    • retourne 2
  • factorial(3) se termine
    • retourne 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écursion

  • factorial(1) se termine
    • retourne 1
  • factorial(2) se termine
    • retourne 2
  • factorial(3) se termine
    • retourne 6
  • factorial(4) se termine
    • retourne 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écursion

  • factorial(1) se termine
    • retourne 1
  • factorial(2) se termine
    • retourne 2
  • factorial(3) se termine
    • retourne 6
  • factorial(4) se termine
    • retourne 24
  • factorial(5) se termine
    • retourne 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écursion

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

Image d'une file vide.

Structures de données et algorithmes en Python

Programmation dynamique

  • Technique d'optimisation
  • Principalement appliquée à la récursion
  • Peut réduire la complexité des algorithmes récursifs
  • Sert à :
    • Tout problème divisible en sous-problèmes plus petits
    • Chevauchement des sous-problèmes
  • On mémorise les solutions des sous-problèmes pour éviter de recalculer
    • Mémorisation
Structures de données et algorithmes en Python

Passons à la pratique !

Structures de données et algorithmes en Python

Preparing Video For Download...