MP, PSI et la TSI

La Récursivité, Souplesse et Complexité

I. Récursivité

De l’art et la manière d’élaborer des algorithmes pour résoudre des problèmes qu’on ne sait pas résoudre soi-même !

1. Définition

Une définition récursive est une définition dans laquelle intervient ce que l’on veut définir.

Un algorithme est dit récursif lorsqu’il est défini en fonction de lui-même.

2. Récursivité simple

la fonction puissance x -> xpeut être définie récursivement :


L’algorithme correspondant s’écrit :

def puissance(x,n) :
          if n==0 :
                      return 1
          else :
                      return  x*puissance(x,n-1)

3. Récursivité multiple

Une définition récursive peut contenir plus d’un appel récursif.

Exemple 1 : Nombre de Combinaisons 

On se propose de calculer le nombre de combinaisons C(n,p) en se servant de la relation de Pascal  : 


L’algorithme correspondant s’écrit :

def Combinaison (n, p) :
          if  p == 0 or p== n :
                      return  1 
          else :
           return (Combinaison (n-1, p) + Combinaison (n-1, p-1))

Exemple 2 : Suite de Fibonacci

def Fibonacci(n,) :
          if  n == 0 or n== 1 :
                      return  1 
          else :
           return (Fibonacci (n-2) + Fibonacci (n-1))

4. Récursivité mutuelle

Des définitions sont dites mutuellement récursives si elles dépendent les unes des autres. Ça peut être le cas pour la définition de la parité :


Les algorithmes correspondants s’écrivent :

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)

5. Récursivité imbriquée

La fonction d’Ackermann est définie comme suit :


D’où l’algorithme :

def Ackermann (m, n) :
          if m==0 :
                      return n+1
          elif n==1 :
                      return Ackermann (m-1,1)
          else :
                      return Ackermann (m-1, Ackermann (m,n-1))

6. Principe et dangers de la récursivité

6.1. Principe  et intérêt :

Ce sont les mêmes que ceux de la démonstration par récurrence en mathématiques. On doit avoir :

Un certain nombre de cas dont la résolution est connue, ces «cas simples» formeront les cas d’arrêt de la récursivité

Un moyen de se ramener d’un cas « compliqué » à un cas « plus simple».

La récursivité permet d’écrire des algorithmes concis et élégants.

6.2. Difficultés  :

La définition peut être dénuée de sens :

Algorithme A(n)
          renvoyer A(n)

Il faut être sûr qu’on retombera toujours sur un cas connu, c’est-à-dire sur un cas d’arrêt ; il nous faut nous assurer que la fonction est complètement définie, c’est-à-dire, qu’elle est définie sur tout son domaine d’applications.

Moyen : existence d’un ordre strict tel que la suite des valeurs successives des arguments invoqués par la définition soit strictement monotone et finit toujours par atteindre une valeur pour laquelle la solution est explicitement définie.

Exemple : L’algorithme ci-dessous teste si est un diviseur de b.

def Diviseur (a,b) :
     If (<=0) :
                      return False
          elif a>=b :
                      return (a==b)
          else :
                       return Diviseur (a,b-a)

La suite des valeurs b, b-a, b-2a, etc. est strictement décroissante, car est strictement positif, et on finit toujours par aboutir à un couple d’arguments (a,b) tel que b-a  est négatif, cas défini explicitement.

6.3. Importance  de l’ordre des appels récursifs

Fonction qui affiche les entiers par ordre décroissant, de jusqu’à 1 :

def Décroissant (n)
     if (= 0 ) :
            print(‘’)
     else :
            print(n)
            Décroissant (n-1)
def Croissant (n)
     if (= 0 ) :
            print(‘’)
     else :
               Croissant (n-1)
               print(n)

Décroissant(2)-> affiche :2 suivi de 1

Croissant(2) -> affiche : 1 suivi de 2

7. Exemple d’algorithme récursif : les tours de Hanoï

Le problème 

Le jeu est constitué d’une plaquette de bois où sont plantées trois tiges numérotées 1, 2 et 3. Sur ces tiges sont empilés des disques de diamètres tous différents. Les seules règles du jeu sont que l’on ne peut déplacer qu’un seul disque à la fois, et qu’il est interdit de poser un disque sur un disque plus petit.

Au début, tous les disques sont sur la tige 1 (celle de gauche), et à la fin ils doivent être sur celle de droite.

Résolution : 

Principe : On suppose que l’on sait résoudre le problème pour (n-1) disques. Pour déplacer disques de la tige 1 vers la tige 3, on déplace les (n-1) plus petits disques de la tige 1 vers la tige 2, puis on déplace le plus gros disque de la tige 1 vers la tige 3, puis on déplace les (n-1) plus petits disques de la tige 2 vers la tige 3.

Validité : il n’y a pas de viol des règles possible puisque le plus gros disque est toujours en « bas » d’une tige et que l’hypothèse (de récurrence) nous assure que nous savons déplacer le « bloc » de (n-1) disques en respectant les règles.


def hanoi(n,depart, intermediaire, destination) :
          if n>0 :
                      hanoi(n-1,depart,destination,intermediare)
                      print(‘ deplacer un disque de ’,depart,’ vers ’, destination)
                      hanoi(n-1,intermediaire, depart, destination)

L’appel à hanoi(3,1,2,3) entraîne l’affichage de :

Déplace un disque de la tige 1 vers la tige 3
Déplace un disque de la tige 1 vers la tige 2
Déplace un disque de la tige 3 vers la tige 2
Déplace un disque de la tige 1 vers la tige 3
Déplace un disque de la tige 2 vers la tige 1
Déplace un disque de la tige 2 vers la tige 3
Déplace un disque de la tige 1 vers la tige 3

Complexité  

On compte le nombre de déplacements de disques effectués par l’algorithme Hanoi invoqué sur disques.



et on en déduit facilement (démonstration par récurrence) que :

C(n)=(2^n)-1

En supposant que le déplacement d’un disque nécessite 1 minute (il faut réfléchir et déplacer un disque qui peut être lourd puisqu’il est en or), et si on dispose de 64 disques, il faudrait :

C(n)=(2^64)-1=3.50965 (10^13)= 35096,5 milliards d’années

II. Dérécursivation

Dérécursiver, c’est transformer un algorithme récursif en un algorithme équivalent ne contenant pas d’appels récursifs.

1. Exemples :

Exemple 1 : Est-ce que a est diviseur de b ? 

Version récursive

Version dérécursivée

def Diviseur (a,b) :
     If (<=0) :
                      return False
          elif a>=b :
                      return (a==b)
          else :
                       return Diviseur (a,b-a)
def Diviseur (a,b) :
     If (<=0) :
                      return False
          while b>a :
                      b-=a
          return (a==b)

Exemple 2 : Factoriel (N) ? 

Version récursive

Version dérécursivée

def Factoriel (N) :
     If N==0 :
                      return 1
          else :
                       return N* Factoriel (N-1)
def Factoriel (N) :
     F=1
          for i in range(N,0,-1) :
                  F*=i
          return F

Les programmes itératifs sont souvent plus efficaces, mais les programmes récursifs sont plus faciles à écrire. Il est toujours possible de dérécursiver un algorithme récursif.

2. Remarques

Les programmes itératifs sont souvent plus efficaces, mais les programmes récursifs sont plus faciles à écrire. Il est toujours possible de dérécursiver un algorithme récursif.


Partager ce cours avec tes amis :
Rédigé par Mostafa Sedoki
Computer science teacher and the founder of the e-learning platform "developpement-informatique.com", my mission is to provide high-quality courses for free to all computer science students and teachers

Cours Similaires :