Récursivité

par cfaury · Publié 26 mai 2020 · Mis à jour 8 septembre 2024

Un algorithme récursif est un algorithme qui résout un problème en calculant des solutions d’instances plus petites du même problème.

L’approche récursive est un des concepts de base en informatique.

Récursivité dans les langages informatiques

Les premiers langages de programmation qui ont autorisé l’emploi de la récursivité sont LISP et Algol 60. Depuis, tous les langages de programmation généraux réalisent une implémentation de la récursivité.

Algorithme itératif vs récursif

On oppose généralement les algorithmes récursifs aux algorithmes itératifs … mais quelle est leur différence ?

Exemple de problème : compter des billes sur un tas

Approche itérative

Initialiser un compteur
Tant qu’il y a des billes sur le tas :
- Incrémenter de 1 le compteur
- Ôter une bille du tas (ou la déplacer dans un autre tas)
Le compteur vaut le nombre de billes

Un algorithme itératif utilise des boucles pour et des boucles tant que, pour répéter des opérations.

Approche récursive

Dans cette approche, on tente de réduire le problème donné à un problème plus réduit (mais de même nature). Cette technique est parfois appelée « diviser pour régner ».

Nombre de billes dans le tas = 1 + nombre de billes dans le tas diminué de 1 bille

ou bien, en plus détaillé :

Nombre de billes dans le tas :
- si le tas est vide
  - renvoyer 0
- sinon
  - renvoyer 1 + Nombre de billes dans un tas diminué de 1 bille

Fonctions récursives

Une fonction est qualifiée de récursive si elle s’appelle elle-même.

Exemple : fonction exponentiation qui permet de calculer $x^y$ (avec $y\in\mathbb{N}^+$) :

On peut remarquer que $x^y$ peut s’écrire :

$\large{x^y=\underbrace{x\times x\times x\dots\times x}_{\text{$y$ fois}}=\color{gray}{x\times}\underbrace{\color{blue}{x\times x\dots\times x}}_{\text{$y-1$ fois}}=\color{gray}{x\times}\color{blue}{x^{y-1}}}$

Cette écriture permet de faire apparaître la structure récursive de l’expression $x^y$.

La fonction peut donc être définie par récurrence :

$\large{x^y = \begin{cases}
1, & \text{si $y=0$} \\
x\times x^{y-1}, & \text{sinon}
\end{cases}}$

On voit bien que la définition de la fonction exponentiation $x^y$ :

fait appelle elle-même à la fonction exponentiation
comporte deux cas, dont l’un n’utilise pas la fonction exponentiation

Implémentation en Python :

def puissance(x, y):
   if y > 0 :                        # Si y > 0 alors …
      return x * puissance(x, y-1)   # auto appel de la fonction
   else :                            # Sinon (y == 0)
      return 1                       # Arrêt de la récursion

print(puissance(3,8))

Structure d’un algorithme récursif

Toute fonction récursive doit avoir, grâce à une structure conditionnelle, une condition pour laquelle elle ne s’appelle pas elle-même. Sans cela, elle ne s’arrêterait jamais !

Cette condition s’appelle le cas de base.

Dans l’exemple précédent, le cas de base est la condition y <= 0 .

En pratique Python prévoit une profondeur de récursion maximum (par défaut 1000, mais modifiable), mais l’atteindre provoque une erreur, et surtout témoigne souvent d’une faute de programmation.

A contrario, les cas pour lesquels un appel récursif à lieu sont appelés cas récursifs.

Il existe toujours une façon non récursive de réaliser une fonction donnée.

Lorsque la structure à traiter où le problème à résoudre apparaît clairement récursif (peut être décrit par récurrence), écrire une fonction sous forme récursive est souvent plus naturel. En revanche, les grandes profondeurs de récursion peuvent solliciter fortement la mémoire et rendre son exécution plus lente.

Exercices

Fonction factorielle

Elle est définie par : $n!=1\times 2\times 3\times\dots\times n$ (avec $n\in\mathbb{N}^+$)

Comme pour la fonction exponentiation (voir plus haut), faire apparaître (à l’aide d’un « croquis » sur papier) l’aspect récursif de cette fonction.

Correction

$n!=\underbrace{1\times 2\times 3\times\dots\times (n-1)}_{(n-1)!}\times n$

Identifier le cas de base pour cette fonction, c’est à dire la condition sur $n$ qui fait qu’il n’est pas nécessaire de calculer $(n-1)!$ pour obtenir $n!$. .

Correction

Si $n=1$, on sait que $n!=1$. Le cas de base est donc « si $n=1$ ».

Écrire sous forme récursive la fonction : $factorielle:x \rightarrow x!$

Correction

def factoriel_recursif(n):
    if n > 1:
        return n * factoriel_recursif(n-1)
    else:
        return n

Calculer l’ordre de complexité de cet algorithme.

Correction

Complexité : $\mathcal{O}(n)$

Somme de deux entiers

Proposer un algorithme récursif de calcul de la somme de deux entiers naturels a et b en supposant que les seules opérations disponibles sont :

l’ajout de 1 à un entier : a += 1
le retrait de 1 à un entier : a -= 1
les comparaisons à 0 d’un entier : a == 0 , a > 0 et a < 0

Aide

Observer l’animation suivante … et réaliser un schéma (sur papier !) illustrant graphiquement le cas récursif à mettre en œuvre.

Étendre cette fonction aux entiers relatifs.

Palindrome

Un palindrome est un mot dont les lettres lues de gauche à droite sont les mêmes que celles lues de droite à gauche.

Exemple : les mots « radar » , « elle » , « été » , « ici » sont des palindromes.

On cherche à écrire en Python une fonction palindrome(mot) qui renvoie True si mot est un palindrome.

Faire apparaître (à l’aide d’un « croquis » sur papier) l’aspect récursif de cette fonction.

Réaliser une fonction, selon un algorithme récursif, qui teste si un mot est un palindrome ou non.

Identifier la ligne traitant le cas de base de cette fonction.

Calculer l’ordre de la complexité temporelle de cet algorithme et comparer avec une méthode itérative.

Calculer l’ordre de la complexité spatiale de cet algorithme et comparer avec une méthode itérative.

Sources :
https://fr.wikipedia.org/wiki/Algorithme_récursif

Connexion

Récursivité