Récursivité
Numérique et Sciences Informatiques
Récursivité :
La récursivité est un concept qui est très proche de la notion mathématiques de la récurrence. On dit qu’une fonction est récursive si elle s’appelle elle-même.
Pour résoudre un problème ou effectuer un calcul, on se ramène à la résolution d’un problème similaire mais de complexité moindre. On recommence ainsi jusqu’à obtenir un problème élémentaire que l’on sait résoudre.
Activités débranchées : Nombre de calculatrices
On place des élèves en ligne. Pour cet exercice, comptent comme calculatrices :
- toutes les calculatrices classiques de poche
- tous les téléphones portables
Chaque élève joue le rôle d'un appel de fonction.
Combien de calculatrices y a-t-il avec toi et après toi ?
- S'il y n'a personne après,
- on répond sa quantité personnelle.
- Sinon,
- on pose la même question au suivant,
- on ajoute à la réponse sa quantité personnelle,
- puis on répond.
La plus-part des langages de programmation actuels permettent de mettre en œuvre directement cette réduction du problème, en autorisant une fonction à s’appeler elle-même : on parle alors de fonction récursive. On trouvera souvent deux versions possibles d'un même programme : itérative et récursive.
Cependant deux éléments sont indispensables à la terminaison d’une fonction récursive :
- il est nécessaire qu’il y ait une condition d’arrêt ;
- il ne doit pas y avoir de suite infinie d’appels récursifs.
Exemple :
def compte(n):
if n >= 0:
print(n)
compte(n-1)
returnUn sous-programme est dit récursif s’il fait appel à lui-même, comme ici.
Détaillons la procédure compte :
- le test n ≥ 0 est une condition d’arrêt, obligatoire sinon le sous-programme peut boucler indéfiniment;
- la valeur de n est affichée si n est un nombre positif ou nul puis il y a un appel à la procédure elle-même en passant par le paramètre n −1, cet appel est dit récursif; la valeur n −1 passée en paramètre permet de faire décroître la valeur de n pour que le sous-programme ne boucle pas indéfiniment;
- la valeur de n −1 est affichée si n −1 est un nombre positif ou nul puis il y a un appel à la procédure elle-même en passant le paramètre n −2;
- les appels récursifs continuent jusqu’à ce que le paramètre passé à la procédure prenne la valeur −1;
- la dernière valeur affichée est donc 0.
Affichage de "4", appel de compte(3),
Affichage de "3", appel de compte(2),
Affichage de "2", appel de compte(1),
Affichage de "1", appel de compte(0),
Affichage de "0", appel de compte(−1) ### Le test n’est plus vérifié, c’est terminé.Entraînement 1 :
Rappelons tout d'abord que n! = 1 × 2 × 3 × .. .× n et que cette fonction vérifie la relation de récurrence n! = n × (n−1)!.
- Implémenter de manière récursive en python cette fonction
- En déduire sa complexité
A noter que l'algorithme itératif calculant cette factorielle a la même complexité. Le voici en Python :
def factorielle_iterative(n):
"""
Entrée : n - entier positif
Sortie : entier - produit des entiers de 1 à n
"""
resultat = 1
for i in range(2,n+1):
resultat *= i
return resultatLa multiplication du paysan russe
La méthode du paysan russe est un très vieil algorithme de multiplication de deux nombres entiers déjà décrit (sous une forme légèrement différente) sur un papyrus égyptien rédigé vers 1650 av. J.-C. Il s’agissait de la principale méthode de calcul en Europe avant l’introduction des chiffres arabes, et les premiers ordinateurs l’ont utilisé avant que la multiplication ne soit directement intégrée dans le processeur sous forme de circuit électronique.
Cet algorithme repose sur les relations :
On pourra trouver deux versions possibles d'un même programme : itérative et récursive.
def multiply(x, y):
"""
entrée : x, y - entier positif
sortie : entier - produit de x et y
"""
p = 0
while x > 0:
if x % 2 == 1:
p += y
x = x // 2
y = y + y
return pdef multiply_recursive(x, y):
"""
entrée : x, y - entier positif
sortie : entier - produit de x et y
"""
if x <= 0:
return 0
elif x % 2 == 0:
return multiply_recursive(x//2, y+y)
else:
return multiply_recursive(x//2, y+y) + yDans le cas de la multiplication paysanne, la condition d’arrêt correspond à x <= 0 et le nombre d’appels récursifs est fini puisque lorsque x > 0 la suite définie par x0 = x et la relation xn+1 = xn / 2 est une suite qui stationne en 0. On peut même calculer le nombre exact d’appels récursifs : il y en a log(x) + 1.
Entraînement 2 :
Compléter le tableau suivant en réalisant sur le papier du produit 199 * 106 en utilisant la version itérative de l'algorithme:
| p | x | y |
|---|---|---|
| 0 | 199 | 106 |
| 106 | 99 | 212 |
| 318 | 49 | 424 |
| .. | .. | .. |
| .. | .. | .. |
| .. | .. | .. |
| .. | .. | .. |
| .. | .. | .. |
| 21094 | 0 | .. |
Les tours de Hanoï
Il n’existe pas de réponse définitive à la question de savoir si un algorithme récursif est préférable à un algorithme itératif ou le contraire. Il a été prouvé que ces deux paradigmes de programmation sont équivalents ; autrement dit, tout algorithme itératif possède une version récursive, et réciproquement
Le choix d’écrire une fonction récursive ou itérative peut dépendre du problème à résoudre : certains problèmes se résolvent particulièrement simplement sous forme récursive, et le plus emblématique de tous est sans conteste le problème des tours de Hanoï inventé par le mathématicien français Édouard Lucas. Ce jeu mathématique est constitué de trois tiges sur lesquelles sont enfilés n disques de diamètres différents. Au début du jeu, ces disques sont tous positionnés sur la première tige (du plus grand au plus petit) et l’objectif est de déplacer tous ces disques sur la troisième tige, en respectant les règles suivantes :
- un seul disque peut être déplacé à la fois ;
- on ne peut jamais poser un disque sur un disque de diamètre inférieur.
On arrive vite à la conclusion que la résolution du problème pour toute valeur de n est récursive :
Le cas de base étant le déplacement d'un seul disque. Vous pouvez vérifier tout cela avec la simulation
def hanoi(n, i = 1, j = 2, k = 3):
"""
Entrée : entier - n le nombre de disque, i,j et k les tiges
Sortie : affiche les déplacements pour meilleur solution de hanoï
"""
if n == 0:
return None
hanoi(n - 1, i, k, j)
print("Déplacer le disque",n,"de la tige",i,"vers la tige",k)
hanoi(n - 1, j, i, k)
Venons-en maintenant au calcul de la complexité de cette procédure qui n'est composée que d'une structure conditionnelle.
Si n > 1 , une opération élémentaire (une comparaison) est effectuée lors du test, une autre lors de l'affichage, et on a deux appels récursifs. On a ainsi T(n) = 2T(n−1) + 2.
Si n = 1, seule la comparaison a lieu donc T(1) = 1.
La complexité T est donc une suite arithmético-géométrique associée aux constantes a = 2 et b = 2.
On a alors T(n) = Θ(2n). Cet algorithme est donc de complexité exponentielle.
Entraînement 3 :
- Tester le programme hanoi() dans plusieurs cas pour bien le comprendre.
- Quelle est la condition d'arrêt de votre fonction récursive ?
Récursivité multiple
Un appel récursif est dit multiple si la fonction contient plusieurs appels récursifs à elle-même.
Un exemple classique de récursivité multiple est celui de la fonction de Fibonacci définie mathématiquement par :
def fibonacci(n):
"""
Entrée : n - entier positif
Sortie : entier - valeur de la suite de fibonacci(n)
"""
if n < 2:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)Dans la version récursive, pour calculer fibonacci(5), on calcule d’abord fibonacci(4) et fibonacci(3). Pour calculer fibonacci(4), on calcule fibonacci(3) et fibonacci(2). Pour calculer fibonacci(3), on calcule fibonacci(2) et fibonacci(1)... Le déroulement du processus est arborescent comme le montre la figure ci-dessous.
Dans cet arbre, on constate par exemple que le calcul de fibonacci(3) est développé intégralement 2 fois : une fois pour le calul de fibonacci(4) et une fois pour lui-même. En fait, il n’est pas très difficile de montrer que le nombre de fois où la fonction calcule fibonacci(1) ou fibonacci(0) (ie. le nombre de feuilles dans l’arbre) est précisément un (fibonacci(n)). Or la valeur de un croît de manière exponentielle avec n; ainsi, avec cette version récursive, le processus de calcul de fibonacci(n) prend un temps qui croît de façon exponentielle avec n.
Il existe plusieurs solutions pour obtenir un coût plus raisonnable.
La solution que nous allons adopter consiste à mémoriser le résultat des calculs une fois qu’ils auront été
calculés de manière à ne pas refaire deux fois le même calcul. La structure de données qui s’impose ici est
la structure de dictionnaire, qui est constituée de paires associant une clé à une valeur. Dans le cas qui nous
intéresse, la clé est l’entier n et la valeur, l’entier fn.
fibMem = {0: 1, 1: 1}
"""
Entrée : n - entier positif
Sortie : entier - valeur de la suite de fib(n)
"""
def fib(n):
if n not in fibMem:
fibMem[n] = fib(n-1) + fib(n-2)
return fibMem[n]Pile d’exécution d'une fonction
La Pile d’exécution du programme en cours est un emplacement mémoire destiner à mémoriser les paramètres, les variables locales ainsi que les adresses de retour des fonctions en cours d’exécution.
Elle fonctionne selon le principe LIFO (Last-In-First-Out) : dernier entré premier sorti.
La pile d’exécution de la fonction factorielle évolue comme suit :
On constate qu’après un appel récursif, la pile contient un élément de plus. La taille de celle-ci va donc croître linéairement avec le nombres d’appels imbriqués, ce qui peut éventuellement occasionner un débordement de la capacité de la pile, cette dernière ayant une taille majorée.
Entraînement 4 :
Rendre récursive la fonction
def somme(n, m):
"""
Entrée : n, m - entier positif
Sortie : entier - somme de n et de m
"""
resultat = m
for i in range(n):
resultat += 1
return resultatEntraînement 5 :
Écrire une fonction récursive puissance(x,n) qui calcule le nombre xn pour n entier strictement positif.
Entraînement 6 :
Écrire une fonction récursive puissance_rapide(x,n) qui calcule le nombre xn pour n entier strictement positif.
Entraînement 7 :
Reproduire le dessin suivant, à l'aide du module turtle.
Entraînement 8 :
Le flocon de von Koch est l'une des premières courbes fractales à avoir été décrite (bien avant l'invention du terme « fractal(e) »). Elle a été inventée en 1906 par le mathématicien suédois Helge
von Koch.
La courbe de von Koch d'un segment de droite, en modifiant récursivement chaque segment de droite de la façon suivante :
- On divise le segment de droite en trois segments de longueurs égales.
- On construit un triangle équilatéral ayant pour base le segment médian de la première étape.
- On supprime le segment de droite qui était la base du triangle de la deuxième étape.
Le flocon de von Koch s'obtient de la même façon que la fractale précédente, en partant d'un triangle équilatéral au lieu d'un segment de droite, et en effectuant les modifications en orientant les triangles vers l'extérieur.
import turtle
def koch(l,n): # # Fractacle de Koch
if n<=0:
turtle.forward(l)
else:
koch(l/3,n-1)
turtle.left(60)
koch(l/3,n-1)
turtle.right(120)
koch(l/3,n-1)
turtle.left(60)
koch(l/3,n-1)
def flocon(l,n): ## Flocon de Koch
#speed(10) ## speed du traceur au maximum
koch(l,n)
turtle.right(120)
koch(l,n)
turtle.right(120)
koch(l,n)
# programme principal
etape = int(input("Entrez l'ordre de l'etape du flocon de Von Koch "))
taille = float(input("Entrez la taille du cote du triangle initial "))
flocon(taille,etape)
- tester le programmer ci-dessus Aide Turtle Masquer
| Étape n | Nombre de côtés | Longueur de chaque côté | Périmètre P(n) |
|---|---|---|---|
| 0 | 3 | 9 | 27 |
| 1 | ? | ? | ? |
| 2 | ? | ? | ? |
| 3 | ? | ? | ? |
| 4 | ? | ? | ? |
| 5 | ? | ? | ? |