Récursivité

Numérique et Sciences Informatiques

donnees

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.

Récurcivité
Dessins récursifs de triangles
Création de l'artiste visuel Polonais Feliks Tomasz Konczakowski

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)
	return

Un 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.
Par exemple l’instruction compte(4) donne :
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 resultat

La 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 :

Graphe

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) + y

Dans 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:

x y p
199 106 0
99 212 106
49 424 318
.. .. ..
.. .. ..
.. .. ..
.. .. ..
.. .. ..
0 .. 21094
Voir une solution


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.

Graphe
Configuration initiale et finale

On arrive vite à la conclusion que la résolution du problème pour toute valeur de n est récursive :

  • On déplace n − 1 disques de la tour initiale à la tour intermédiaire en passant par la tour finale.
  • On déplace le plus grand disque de la tour initiale vers la tour finale.
  • On déplace n − 1 disques de la tour intermédiaire à la tour finale en passant par la tour initiale.
Le cas de base étant le déplacement d'un seul disque. Vous pouvez vérifier tout cela avec la simulation

pour déplacer n disques de la tige A vers la tige C, on déplace les (n−1) plus petits disques de la tige A vers la tige B, puis on déplace le plus gros disque de la tige A vers la tige C, puis on déplace les (n−1) plus petits disques de la tige B vers la tige C.
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 :

  1. Tester le programme hanoi() dans plusieurs cas pour bien le comprendre.
  2. Quelle est la condition d'arrêt de votre fonction récursive ?
Voir une solution

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 :

Fibonacci
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.

Fibonacci
On remarque que les branches de l’arbre se divise en deux à chaque niveau (sauf en bas de l’arbre, ie. à droite sur la figure), ce qui traduit le fait que la fonction fibonacci s’appelle elle-même deux fois à chaque fois qu’elle est invoquée avec n > 1. ce qui fait (en tout) 15 appels à la fonction fibonacci au lieu des 6 appels attendus.
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 :

Pile d'éxécution

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 somme suivante

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 resultat

Entraî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.

Factoriel

Entraînement 7 :

Reproduire le dessin suivant, à l'aide du module turtle.

Fibonacci

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 :

  1. On divise le segment de droite en trois segments de longueurs égales.
  2. On construit un triangle équilatéral ayant pour base le segment médian de la première étape.
  3. On supprime le segment de droite qui était la base du triangle de la deuxième étape.
flocon de koch
Au bout de ces trois étapes, l'objet résultant a une forme similaire à une section transversale d'un chapeau de sorcière. La courbe de von Koch est la limite des courbes obtenues, lorsqu'on répète indéfiniment les étapes mentionnées ci-avant.
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)
  1. tester le programmer ci-dessus Aide Turtle

  2. Compléter le tableau suivant :
É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 ? ? ?

Un dernier exemple

En informatique une fonction qui contient un appel à elle-même est appelé récursif.

from turtle import *

angle = 30
color('#3f1905')

def arbre(n,longueur):
    if n==0:
        color('green')
        forward(longueur) # avance
        backward(longueur) # recule
        color('#3f1905')
    else:
        width(n)
        forward(longueur/3) #avance
        left(angle) # tourne vers la gauche de angle degrés
        arbre(n-1,longueur*2/3)
        right(2*angle) # tourne vers la droite de angle degrés
        arbre(n-1,longueur*2/3)
        left(angle) # tourne vers la gauche de angle degrés
        backward(longueur/3) # recule

hideturtle() # cache la tortue
up() # lève le stylo
right(90) # tourne de 90 degrés vers la droite 
forward(300) # avance de 300 pixels
left(180) # fait un demi-tour
down() # pose le stylo
arbre(11,700) # exécute la macro
showturtle() # affiche la tortue
mainloop()

Savoir faire

  • Écrire un programme récursif.
  • Analyser le fonctionnement d’un programme récursif.

Fiche de cours