TP : Recursivité

Un exemple : la fonction Factorielle

La fonction factorielle est définie sur les entiers par $$n!=n\times (n-1)\times ... \times 1$$

le factorielle de n est le produit des n premiers entiers entre eux

Par exemple $4! = 4\times 3\times 2\times 1 = 24$

On peut programmer cette fonction de deux manières:

Recopiez le programme ci-dessous et testez le pour différentes valeurs 1,3,4, 5 et 17


def factorielleIteratif( n):
  produit = 1;
  for i in range(1,n+1):
      produit *= i
  
  return produit

#----------------------------------
def factorielleRecursif( n):
#Cas de base n = 1
  if n == 0 :
      return 1
  
#n! = n * (n-1)!
  else:
      return n*factorielleRecursif(n-1)
  
  

#-------------Programme principal----------------

print("le factorielle de 5 (itératif) est ",factorielleIteratif(5))
print("le factorielle de 5 (récursif) est ",factorielleRecursif(5))


La programmation d'une fonction récursive est basée sur deux idées

Exercices

  1. Construire deux fonctions, l'une itérative et l'autre récursive permettant d'ajouter les n premiers entiers entre eux
  2. Construire deux fonctions, l'une itérative et l'autre récursive permettant d'ajouter les inverses des n premiers entiers entre eux

Arbre des appels de fonctions

Lorsqu'on appelle la fonction factorielle(2), avant qu'elle n'ait retournée de valeur elle appelle à son tour la fonction factorielle(1) qui à son tour appelle la fonction factorielle(0)

La fonction factorielle(0) retourne la valeur 1 qui prend la place de factorielle(0) dans le corps de factorielle(1) qui va donc se terminer à son tour et retourner 1*1 = 1

Cette valeur 1 va prendre la place de factorielle(1) dans le corps de factorielle(2) qui va donc se terminer en retournant 2*1 = 2

Avantage et inconvénient de la programmation récursive

  1. Traduction quasiment immédiate d'un algorithme
  2. Appels répétés de la fonction pour les mêmes valeurs (ralentissement du programme)

Regardons cela sur l'exemple de la suite de Fibonnacci:

$u_n =u_{n-1}+u_{n-2}$ avec $u_0=0$ et $u_1=1$



def fibonnacci(n):
#Cas de base n = 1 ou n = 0
    print("début de fibonnacci pour n = ",n)
    if n == 0 :
        print("fin de fibonnacci pour n = ",n) 
        return 0
    elif n == 1:
        print("fin de fibonnacci pour n = ",n)
        return 1
    else:
        s =  fibonnacci(n-1) + fibonnacci(n-2)
        print("fin de fibonnacci pour n = ",n) 
        return s
  
    print("fin de fibonnacci pour n = ",n)

#-------------Programme principal---------------

print("Fibonnacci de 5 vaut ",fibonnacci(5))
    



Recopiez et testez le programme ci-dessus

On constate (voir arbre ci-dessous) qu'on appelle plusieurs la fonction fibonnacci pour les mêmes valeurs, par exemple fibonnacci(2) est appelée 3 fois

Pour éviter cela on va stocker dans un tableau les valeurs calculées et si une valeur est déjà stockée on retourne cette valeur (mémoïsation)


import time
#------------------Variables Globales--------------
TAILLE_MAX = 50
tableValeurs =[0]*TAILLE_MAX
#------------------Fonctions-----------------------
def fibonnacci(n):
#Cas de base n = 1 ou n = 0
    if n == 0 :
        return 0
    elif n == 1:
        return 1
    else:
        s =  fibonnacci(n-1) + fibonnacci(n-2)
        return s
#--------------------------------------------------
def fibonnacciMemo(n):
#Cas de base n = 1 ou n = 2
    
    if n == 1 or n == 2 :
        return 1
    elif(tableValeurs[n] != 0):
        return tableValeurs[n]   
    else:
        s =  fibonnacciMemo(n-1) + fibonnacciMemo(n-2)
        #memoïsation
        tableValeurs[n] = s
        return s
#-------------Programme principal----------------
debut = time.time()
print("Fibonnacci de 40  vaut avec memoisation",fibonnacciMemo(40))
duree = time.time() - debut  

print('Durée en secondes:', duree) 


##debut = time.time()
##print("Fibonnacci de 40  vaut sans memoisation",fibonnacci(40))
##duree = time.time() - debut  
##
##print('Durée en secondes:', duree) 

Recopiez et testez le programme ci-dessus pour calculer la valeur de la suite de Fibonnacci pour n = 20

Comparez les temps d'exécution des deux programmes en utilisant une fonction Python appropriée

Programmation collective

Tours de Hanoï

8 disques sont empilés du plus grand au plus petit autour d'une tige verticale.Il s'agit de les déplacer sur une autre des deux autres tours en utilisant une tour intermédiaire

Plus d'informations ici

Une simulation en ligne ici

  1. Pour comprendre le problème et trouver la nature récursive de ce problème, essayer avec 3 tours, noter les déplacements des disques et observer bien

    De la gauche vers la droite on notera les axes 1,2 et 3 on notera les diamètres arbitraires des disques 6, 5 et 4

    Supposons que l'on veuille déplacer les trois disques de l'axe 2 vers l'axe 1

    On peut commencer par déplacer le sommet de la pile , le disque 4 vers l'axe 1, ce que l'on note 2 --> 1

    Puis on peut faire 2 --> 3 , etc... Terminer

    Regarder la suite des déplacements comme le parcours dans un arbre en profondeur, ce qui va nous aider à programmer la solution à ce problème de manière récursive

  2. Créer une fonction récursive hanoi( a, b, n) où a et b peuvent prendre les valeurs 1 ou 2 ou 3 et n est le nombre de disques

    Il faudra peut être mettre au point une fonction qui à partir de a et b donne l'axe auxiliaire c par exemple (1,2) --> 3 et (2,3) --> 1

Mini-projet personnel (avant J+7)