2. Algorithmes récursifs

sept. 10, 2018

Une poupée russe, c’est une poupée avec une poupée russe à l’intérieur.

des poupées russes

Les poupées russes (source Wikipedia)

Objectifs

  • Découvrir une autre forme d’expression d’algorithmes
  • Plusieurs types de récursivité
  • La récursivité en Python

2.1. Introduction

En programmation, nombreux sont les problèmes qu’on résout en répétant plusieurs fois des séquences d’instructions.

Certains langages sont munis de structures de contrôles répétitive. C’est le cas notamment pour Python, qui dispose des boucles pour (for) et tant que (while).

Mais certains problèmes se résolvent simplement en résolvant un sous problème de même nature, mais plus simple…

Cette méthode de résolution s’appelle la récursivité.

2.1.1. Exemple 1 : factorielle

On souhaite calculer \(n!\). On rappelle que pour tout entier \(n \geq 0\)

\[n!=1 \times 2 \times 3 \times \ldots \times (n-1) \times n.\]

On peut déduire de cette définition une propriété importante

\[\forall n\geq 1,\ \ n!=n\times (n-1)!\]

qui prouve que si on sait calculer \((n-1)!\) alors on sait calculer \(n!\).

Par ailleurs, on sait que \(0!=1\). On sait donc calculer \(1!\) puis \(2!\), et par récurrence on peut établir qu’on sait calculer \(n!\) pour tout entier \(n\geq 0\).

2.1.2. Exemple 2 : dérivation d’une fonction numérique

Lorsqu’on doit dériver une fonction numérique d’une variable , on a à notre disposition un ensemble de règles de dérivation qu’on peut appliquer.

  • \((u+v)'=u'+v'\)
  • \((u-v)'=u'-v'\)
  • \((uv)'=u'v+uv'\)
  • \(\left(\frac{u}{v}\right)'=\frac{u'v-uv'}{v^2}\)
  • etc …

Néanmoins pour appliquer ces règles il faut savoir dériver. Heureusement, on connait les dérivées des fonctions élémentaires. Par conséquent, on sait calculer la dérivée de toutes les fonctions dérivables. Encore une fois, le calcul est récursif.

2.1.3. Exemple 3 : les tours de Hanoï

On dispose de trois tours côte à côte sur lesquelles on peut empiler des disques de diamètre croissant.

Initialement, seule la tour la plus à gauche contient des disques, les deux autres sont vides.

On ne peut déplacer qu’un disque à la fois et on ne doit pas poser un disque plus large sur un disque plus étroit.

Le problème des tours de Hanoï est de trouver la suite de déplacements qui permet de placer tous les disques sur la tour la plus à droite en respectant les contraintes imposées aux déplacements.

Pour voir plus précisément le problème consultez ce document.

2.2. Algorithme récursif

2.2.1. Définition

Un algorithme de résolution d’un problème \(P\) sur une donnée \(a\) est dit récursif si parmi les opérations utilisées pour le résoudre, on trouve la résolution du même problème \(P\) sur une donnée \(b\). Dans un algorithme récursif, on nomme appel récursif toute étape de l’algorithme résolvant le même problème sur une autre donnée.

2.2.2. Exemple 1 : factorielle

L’algorithme récursif de calcul de la factorielle distingue deux cas. Le premier cas ne nécessite aucun calcul, le second utilise la fonction fact pour calculer \((n-1)!\).

Calcul de la factorielle d’un entier naturel

Entrée : \(n\in\mathbb{N}\)

Sortie : \(n!\)

  1. si \(n = 0\)
  2. \(\quad\) Renvoyer 1
  3. sinon
  4. \(\quad\) Renvoyer \(n\times \mathtt{fact}(n-1)\)
  5. fin si

2.2.3. Exemple 2 : Dérivation

Voici (une esquisse) de l”algorithme d’une fonction récursive de dérivation (nommée ici derivee).

Calcul de la fonction dérivée d’une fonction dérivable

Entrée : \(f\) une fonction dérivable

Sortie : \(f'\) la fonction dérivée

  1. si \(f\) est une fonction élémentaire de base
  2. \(\quad\) Renvoyer sa dérivée
  3. sinon si \(f = u+v\)
  4. \(\quad\) Renvoyer \(\mathtt{derivee}(u)+\mathtt{derivee}(v)\)
  5. sinon si \(f = uv\)
  6. \(\quad\) Renvoyer \(\mathtt{derivee}(u)\times v + u\times\mathtt{derivee}(v)\)
  7. sinon si

2.2.4. Exemple 3 : Les tours de Hanoï

Et voici un algorithme récursif pour résoudre le problème des tours de Hanoi. Cet algorithme est celui d’une fonction nommée hanoi à trois paramètres

  • le nombre de disques à déplacer
  • la tour de départ où se trouvent ces disques
  • la tour d’arrivée où les disques doivent être placés.

Résolution du problème des tours de Hanoi

Entrée : \(n\in\mathbb{N}\) le nombre de disques à déplacer, \(d\) la tour où ils se trouvent, \(a\) la tour où on doit les mettre.

Action : les déplacements des disques pour les amener sur le

  1. si \(n > 0\)
  2. \(\quad aux \leftarrow\) le piquet différent de \(d\) et \(a\)
  3. \(\quad \mathtt{hanoi}(n-1,d,aux)\)
  4. \(\quad \mathtt{deplacer\_dique} (d,a)\)
  5. \(\quad \mathtt{hanoi}(n-1,aux,a)\)
  6. fin si

Note

on peut remarquer que dans cet algorithme il n’y a pas de sinon. Ceci s’explique par le fait que lorsque \(n=0\), il n’y a rien à faire.

2.2.5. Exécutions d’algorithmes récursifs

Voici le déroulement du calcul récursif de \(4!\) :

\[\begin{split}\begin{aligned} \label{math:algorec-calc-fact} \mathtt{fact}(4) &\rightarrow& 4\times \mathtt{fact}(3)\\ &\rightarrow& 4\times 3 \times \mathtt{fact}(2)\\ &\rightarrow&4\times 3 \times 2 \times \mathtt{fact}(1)\\ &\rightarrow&4\times 3 \times 2 \times 1\times \mathtt{fact}(0) \\ &\rightarrow&4\times 3 \times 2 \times 1\times 1 \\ &\rightarrow& 24 \\\end{aligned}\end{split}\]

On note que des calculs restent en attente, jusqu’à ce qu’on atteigne le cas où il ne reste plus d’appel à la fonction \(\mathtt{fact}\) dans l’expression à calculer.

2.2.6. Règles de conception

Avertissement

Il existe des algorithmes récursifs qui ne produisent aucun résultat.

En voici un exemple

Calcul (sans succès) de la factorielle d’un entier naturel

Entrée : \(n\in\mathbb{N}\)

Sortie : \(n!\)

  1. Renvoyer \(n\times \mathtt{fact2}(n-1)\)

L’évaluation de \(\mathtt{fact2}(1)\) conduit à un calcul infini:

\[\begin{split}\begin{aligned} \mathtt{fact2}(1) &\rightarrow& 1\times \mathtt{fact2}(0)\\ &\rightarrow&1\times 0 \times \mathtt{fact2}(-1)\\ &\rightarrow& ...\\ \end{aligned}\end{split}\]

D’où la première régle de conception d’un algorithme récursif :

Règle 1 :

Tout algorithme récursif doit distinguer plusieurs cas dont l’un au moins ne doit pas contenir d’appels récursifs. sinon il y a risque de cercle vicieux et de calcul infini.

Les cas non récursifs d’un algorithme récursifs sont appelés cas de bases. Les conditions que doivent satisfaire les données dans ces cas de bases sont appelées conditions de terminaison

Même avec un cas de base un algorithme récursif peut ne produire aucun résultat. En voici un exemple :

Calcul (sans succès) de la factorielle d’un entier naturel

Entrée : \(n\in\mathbb{N}\)

Sortie : \(n!\)

  1. si \(n = 0\)
  2. \(\quad\) Renvoyer 1
  3. sinon
  4. \(\quad\) Renvoyer \(\frac{\mathtt{fact3} (n+1)}{n+1}\)
  5. fin si

Là encore, le calcul de \(\mathtt{fact3}(1)\) donne lieu à un calcul infini, malgré la présence d’un cas de base. Mais cette fois le calcul infini est dû à des appels récursifs sur des données s’éloignant du cas de base.

D’où la seconde règle de conception d’un algorithme récursif :

Règle 2 :

Tout appel récursif doit se faire avec des données plus proches de données satisfaisant les conditions de terminaison.

La remarque suivante est assez utile, lorsqu’on souhaite prouver qu’un algorithme récursif s’arrête.

Théorème

Il n’existe pas de suite infinie strictement décroissante d’entiers positifs ou nuls.

2.3. Type de récursivité

2.3.1. Récursivité simple ou linéaire

Un algorithme récursif est simple ou linéaire si chaque cas qu’il distingue se résout en au plus un appel récursif. Ainsi l’algorithme [algo:algorec-factorielle] de calcul de \(n!\) est récursif simple.

2.3.2. Récursivité terminale

Un algorithme récursif simple est terminal lorsque l’appel récursif est la dernière chose effectuée. Généralement ce genre d’algorithme peut facilement être transformé en une boucle. D’ailleurs certains compilateurs sont capables de détecter ce genre de situation et de transformer automatiquement le code pour supprimer la récursivité.

Le schéma d’algorithme qui suit décrit le schéma le plus général qui soit d’un algorithme récursif terminal. Les fonctions/instructions \(p(x)\), \(b(x)\), \(c(x)\) auxquelles il fait appel ne font pas appel directement ou non à \(A\).

Schéma général d’un algorithme récursif terminal \(A\)

Entrée : \(x\) la donnée que doit traiter \(A\)

  1. si \(p(x)\)
  2. \(\quad b(x)\)
  3. sinon
  4. \(\quad A(c(x))\)
  5. fin si

2.3.3. Récursivité multiple

Un algorithme récursif est multiple si l’un des cas qu’il distingue se résout avec plusieurs appels récursifs.

L’exemple des tours de Hanoï, ou encore celui de la dérivation sont des exemples de récursivité multiple.

Note

un algorithme à récursivité multiple ne peut pas être terminal.

2.3.4. Récursivité croisée ou mutuelle

La définition des algorithmes récursifs donnée plus haut qui les caractérise comme étant les algorithmes faisant appel à eux mêmes masque le phénomène des algorithmes mutuellement récursifs.

Deux algorithmes sont mutuellement récursifs si l’un fait appel à l’autre et l’autre à l’un. On peut étendre cette définition à un nombre quelconque d’algorithmes.

En voici un exemple. Deux fonctions nommées pair et impair déterminant la parité ou l’imparité d’un entier.

Prédicat de parité

Entrée : \(n\in\mathbb{N}\)

Sortie : Vrai si \(n\) est pair, Faux sinon

  1. si \(n=0\)
  2. \(\quad\) Renvoyer Vrai
  3. sinon
  4. \(\quad\) Renvoyer \(\mathtt{impair} (n-1)\)
  5. fin si

Prédicat d’imparité

Entrée : \(n\in\mathbb{N}\)

Sortie : Vrai si \(n\) est impair, Faux sinon

  1. si \(n=0\)
  2. \(\quad\) Renvoyer Faux
  3. sinon
  4. \(\quad\) Renvoyer \(\mathtt{pair} (n-1)\)
  5. fin si

2.4. Récursivité en Python

Python permet très simplement l’écriture de fonctions récursives.

2.4.1. Factorielle en Python

def fact(n):
    if n == 0:
       return 1
    else:
       return n * fact(n-1)

2.4.2. Prédicats de parité en Python

def pair(n):
    if n == 0:
       return True
    else:
       return impair(n-1)

def impair(n):
    if n == 0:
       return False
    else:
       return pair(n-1)

2.4.3. Limitation de la récursivité en Python

Dans sa configuration par défaut, le langage Python limite le nombre d’appels récursifs.

Par exemple, le calcul de fact(1000) n’est pas possible. Il se termine par une exception RecursionError [1] :

>>> fact(1000)
...
...
RecursionError: maximum recursion depth exceeded in comparison

La fonction sys.getrecursionlimit donne la profondeur maximale des calculs récursifs :

>>> import sys
>>> sys.getrecursionlimit()
1000

Si on veut augmenter cette profondeur on peut utiliser la fonction sys.setrecursionlimit (cependant il faut rester raisonnable).

>>> sys.setrecursionlimit(1500)
>>> fact(1000)
40238 ... 000
>>> len(str(fact(1000)))
2568

2.5. Conclusion

La récursivité offre au programmeur un autre moyen, souvent élégant et concis, de résoudre des problèmes.

Par exemple,

  • dans la programmation des jeux solitaires du type Sudoku, labyrinthes, …

  • dans la programmation des jeux à deux joueurs du type Échecs, Dames, Othello, …

  • et dans bien d’autres domaines encore …

    … comme le point de croix en broderie (cf ici)

2.6. Notes

[1]L’exception ̀`RecursionError`` est apparue dans la version 3.5 de Python. Pour les versions antérieures, l’exception était RuntimeError.