Comprendre la récursion

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Définition

  • Appel de fonction
  • Presque toutes situations où nous utilisons boucles
    • remplacer boucles par récursion
  • Peut résoudre problèmes qui semblent très complexes
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)
  • Exécuté pour toujours !
Structures de données et algorithmes en Python

Exemple - identification du cas de base

  • Ajouter condition
    • garantit algorithme ne s’exécute pas indéfiniment
  • 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

Comment fonctionne la récursion

  • Ordinateur utilise pile pour suivre fonctions
    • Pile d’appels
Structures de données et algorithmes en Python

Comment fonctionne la récursion

  • factorial(5) commence
  • Avant fin factorial(5) -> factorial(4) commence
  • Avant fin factorial(4) -> factorial(3) commence

Une image d’une file d’attente avec un élément qui représente une fonction.

Structures de données et algorithmes en Python

Comment fonctionne la récursion

  • factorial(5) commence
  • Avant fin factorial(5) -> factorial(4) commence
  • Avant fin factorial(4) -> factorial(3) commence
  • Avant fin factorial(3) -> factorial(2) commence

Une image d’une file d’attente avec deux éléments représentant deux fonctions.

Structures de données et algorithmes en Python

Comment fonctionne la récursion

  • factorial(5) commence
  • Avant fin factorial(5) -> factorial(4) commence
  • Avant fin factorial(4) -> factorial(3) commence
  • Avant fin factorial(3) -> factorial(2) commence
  • Avant fin factorial(2) -> factorial(1) commence

Une image d’une file d’attente avec trois éléments représentant trois fonctions.

Structures de données et algorithmes en Python

Comment fonctionne la récursion

  • factorial(5) commence
  • Avant fin factorial(5) -> factorial(4) commence
  • Avant fin factorial(4) -> factorial(3) commence
  • Avant fin factorial(3) -> factorial(2) commence
  • Avant fin factorial(2) -> factorial(1) commence

Une image d’une file d’attente avec quatre éléments représentant quatre fonctions.

Structures de données et algorithmes en Python

Comment fonctionne la récursion

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

Une image d’une file d’attente avec quatre éléments représentant quatre fonctions.

Structures de données et algorithmes en Python

Comment fonctionne la récursion

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

Une image d’une file d’attente 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

Comment fonctionne la récursion

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

Une image d’une file d’attente avec trois éléments représentant trois fonctions.

Structures de données et algorithmes en Python

Comment fonctionne la récursion

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

Une image d’une file d’attente avec deux éléments représentant deux fonctions.

Structures de données et algorithmes en Python

Comment fonctionne la récursion

  • 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

Une image d’une file avec un élément qui représente une fonction.

Structures de données et algorithmes en Python

Comment fonctionne la récursion

  • 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

Une image d’une file d’attente vide.

Structures de données et algorithmes en Python

Programmation dynamique

  • Technique d’optimisation
  • Principalement appliqué à récursion
  • Peut réduire complexité algorithmes récursifs
  • Utilisé pour :
    • Tout problème pouvant être divisé en sous-problèmes
    • Les sous-problèmes se chevauchent
  • Solutions sous-problèmes enregistrées, évitant ainsi 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...