Recursion

Algorithmics – Session 2

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

Recursive algorithms

What is recursion?

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

Recursive algorithms

A classic example: factorial

$$\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*}$$

Recursive algorithms

A classic example: factorial

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

Recursive algorithms

Principle

Les deux parties principales d’une fonction récursive

  • Le cas de base – Cette condition(s) qui termine la récursion

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

def factorial (n: int):

    # Base case, the recursion ends here
    if n <= 1: 
        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

Recursive algorithms

How recursion works

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

Recap of the session

Main elements to remember

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 plus élémentaire
    • La fonction doit finalement atteindre le cas de base

Recap of the session

What’s next?

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