Récursivité

Algorithmique – Session 2

  • Algorithmes récursifs
  • Récapitulatif de la session

Algorithmes récursifs

Qu’est-ce que la récursion ?

Définition

La récursion est le processus qu’une procédure suit lorsqu’une des étapes de la procédure implique d’invoquer la procédure elle-même (Wikipedia)

En bref

  • Les fonctions récursives sont des fonctions qui s’appellent elles-mêmes
  • Les structures de données récursives contiennent des références à des instances d’elles-mêmes

Algorithmes récursifs

Un exemple classique : la factorielle

$$\begin{align*} n! &= \underbrace{1}_{1!} \times 2 \times \dots \times (n-1) &\times n\\ n! &= \underbrace{1 \times 2}_{2!} \times \dots \times (n-1) &\times n\\ n! &= \underbrace{1 \times 2 \times 3}_{3!} \times \dots \times (n-1) &\times n\\ &\dots\\ n! &= \underbrace{1 \times 2 \times 3\times \dots \times (n-1)}_{(n-1)!} &\times n\\ \end{align*}$$

Algorithmes récursifs

Un exemple classique : la factorielle

$$\begin{align*} n! &= \underbrace{1 \times 2 \times \dots \times (n-1)}_{} &\times n\\ n! &= \quad\quad\quad(n-1)! &\times n\\ \end{align*}$$

  • $n!$ et $(n-1)!$ sont liés par une formule simple

  • C’est une définition récursive de la fonction factorielle

Algorithmes récursifs

Principe

Les deux parties principales d’une fonction récursive

  • Le cas de base – La ou les conditions qui terminent la récursion

    • Valeur obtenue sans calcul, par définition ou par convention ($0! = 1$)

  • L’appel récursif – C’est lorsque la fonction s’appelle elle-même pour obtenir le résultat attendu

    • Par exemple, pour $n!$, on utilise la formule $(n-1)! \times n$

Algorithmes récursifs

Exemple

def factorial (n: int):

    # Base case, the recursion ends here
    if n <= 0: 
        return 1

    # Recursive call, the function calls itself
    return factorial(n-1) * n

Important — Assurez-vous que le cas de base est atteignable, sinon la fonction tournera indéfiniment

Algorithmes récursifs

Comment fonctionne la récursion ?

La pile d’appels

  • Chaque fois qu’une fonction est appelée, une nouvelle frame est ajoutée à la pile d’appels

  • La frame contient les arguments et les variables locales de la fonction

  • Quand la fonction retourne, la frame est retirée de la pile

Récapitulatif de la session

Éléments principaux à retenir

La récursion est le processus qu’une procédure suit lorsqu’une des étapes de la procédure implique d’invoquer la procédure elle-même


  • Cas de base :

    • Arrête la récursion
    • Définit le résultat pour le(s) cas le(s) plus simple(s)

  • Appel récursif :

    • Appelle la fonction avec un cas de taille réduite, se rapprochant d’un cas de base
    • La fonction doit finalement et impérativement atteindre un des cas de base

Récapitulatif de la session

Qu’est-ce qui vient ensuite ?

Activité pratique (~2h30)

Expérimenter la récursivité

  • Identifier les cas de base et les appels récursifs
  • Divers exercices d’application

Après la session

  • Relire les articles de la session
  • Vérifier votre compréhension avec le quiz
  • Compléter l’activité pratique
  • Consulter la section “Avant le cours” de la session suivante