To understand recursion, you must first understand recursion.
La récurrence est un raisonnement mathématique courant et parmi les plus puissants pour démontrer des théorèmes ou construire des objets. Par exemple, on l’utilise dans un cours de mathématique de lycée pour montrer que :
Pour tout entier n⩾0, on a : 1+2+3+…+n=2n(n+1) ;
Un entier naturel n’est autre que 0 ou le successeur d’un entier naturel (0 est 0, 1 est le successeur de 0, 2 est le successeur de 1, …).
En programmation, on peut raisonner de façon identique, nous allons construire des fonctions et des structures de données (listes chaînées, arbres, etc.) à l’aide d’une hypothèse de récurrence et d’un point de départ. Le déroulement de la récurrence sera quant à lui pris en charge par la machine.
Avertissement
La récursion est une approche plus descriptive que constructive. On « dit » quoi faire à l’ordinateur mais pas comment.
À retenir
La récursion est un mécanisme puissant permettant d’exprimer la répétition des opérations dans un programme sans utiliser de structure itérative (boucles while ou for). C’est un mode de pensée qui permet de concevoir des fonctions ou des structures de données (listes chaînées, arbres, etc.) dont l’écriture condense en peu de lignes l’exécution de calculs éventuellement très longs.
Ce chapitre traite de la récursion sur les nombres entiers.
La fonction factorielle indique le nombre de permutations dans un ensemble comportant n éléments. Par exemple, il existe 3!=6 façons d’arranger les 3 caractères ‘a’, ‘b’, ‘c’ :
‘abc’, ‘acb’, ‘bac’, ‘bca’, ‘cab’ et ‘cba’.
On peut exprimer de plusieurs façons la définition de cette fonction :
Une définition implicite : n!=1×2×3×…×n
Une définition explicite :
n!={1n×(n−1)! si n=0 si n≥1
La première définition est particulièrement ambigüe :
Que signifie l’ellipse … ?
Est-il possible de calculer la factorielle d’un nombre inférieur à 3 ?
La factorielle de 0 existe-t-elle ?
Les réponses à toutes ces questions sont évidentes pour une personne ayant suivi un cours de mathématique mais inaccessibles à un ordinateur.
La définition explicite, qui se réfère à elle-même, est dite récursive : la valeur de la fonction en n s’exprime au moyen de la valeur de la fonction en n−1.
Une fonction définie de façon récursive est calculable.
Élévation à la puissance
On peut exprimer de plusieurs façons la définition de cette fonction :
Une définition implicite : xn=x×x×…×xnfois
Une définition explicite1 :
xn={1x×x(n−1) si n=0 si n>0
La définition implicite présente les mêmes ambiguïtés que dans le cas du calcul de la factorielle d’un entier naturel, tandis que la définition explicite, qui se réfère elle-aussi à elle-même et est donc récursive, permet de calculer la valeur de xn.
Mise en œuvre d’un raisonnement récursif : le jeu de Bowling
La disposition des quilles de Bowling permet d’illustrer la mise en œuvre d’un raisonnement récursif :
Combien de quilles composent l’arrangement présenté ?
Réponse
10
On veut ajouter une cinquième ligne à l’arrangement présenté. Combien de quilles supplémentaires devront être disposées si l’on souhaite respecter la logique présente ?
Réponse
5
De combien de quilles sera alors constitué l’arrangement ?
Réponse
10+5=15
Nombre de lignes
Nombre de quilles
Calcul du nombre de quilles
1
1
arrangement(1)
2
3
2 + arrangement(1)
3
6
3 + arrangement(2)
4
10
4 + arrangement(3)
5
15
5 + arrangement(4)
Nombre de quilles en fonction du nombre de lignes. La fonction arrangement reçoit en argument le nombre de lignes et retourne le nombre de quilles dans un arrangement de ce nombre de lignes.
Combien de quilles contient un arrangement de 11 lignes ?
On déduit rapidement du tableau ci-dessus que le nombre de quilles est égal à : 11 + arrangement(10), c’est à dire à 11 plus le nombre de quilles présentes dans un arrangement à 10 lignes.
Obtient-on directement la réponse ?
Non, il faut tout d’abord calculer le nombre de quilles dans un arrangement à 10 lignes. Le calcul est facile, c’est : 10 + arrangement(9), etc.
Quand faut-il s’arrêter ?
On sait que arrangement(1) = 1. On s’arrête donc lorsque l’on est parvenu à un arrangement à 1 ligne.
Info
Le raisonnement précédent est un raisonnement récursif. On a découpé le problème en deux parties :
Si l’arrangement comporte une seule ligne, la réponse est : arrangement(1) = 1.
Si l’arrangement comporte N lignes, la réponse est : N + arrangement(N - 1).
Calcul effectif du nombre de quilles dans un arrangement à 5 lignes
Un algorithme est simplement récursif s’il s’appelle lui-même pour effectuer son traitement.
Il est impératif de veiller à ce qu’un algorithme récursif se termine sous peine d’engendrer un processus infini !
Implémentation de l’algorithme en Python
defarrangement(n:int)->int:"""
Détermination du nombre de quilles dans un
arrangement à n lignes.
HYPOTHÈSE : n entier naturel.
"""ifn==1:# cas de basereturn1else:returnn+arrangement(n-1)# appel récursifassertarrangement(5)==15
Retour sur le calcul de la factorielle d’un entier naturel
On reprend ici le calcul de la factorielle de l’entier naturel n. La définition récursive de la fonction factorielle est donc :
n!={1n×(n−1)! si n=0 si n≥1
Application : calcul de la factorielle de 5
En prenant exemple sur le calcul effectif du nombre de quilles en fonction du nombre de ligne dans l’arrangement, calculer la valeur de 5! en détaillant toutes les étapes.
Réponse
L’arbre des appels est une représentation arborescente faisant apparaître les appels récursifs jusqu’au cas de base.
Implémentation de l’algorithme récursif en Python
deffactorielle(n:int)->int:"""
Définition récursive de la fonction factorielle.
HYPOTHÈSE : n entier naturel.
"""ifn==0:# cas de basereturn1else:returnn*factorielle(n-1)# appel récursifassertfactorielle(5)==120
La définition récursive d’une fonction doit être formée :
d’un ou plusieurs cas de base, qui ne doivent contenir aucun appel récursif ;
d’un ou plusieurs appel(s) récursif(s) au cours desquels la fonction s’appelle elle-même.
Remarques
Il est impératif que le cas de base soit réalisé à une étape du processus, sous peine d’obtenir une récursion infinie.
Les appels récursifs n’apparaissent pas de façon évidente dans le cas de la récursivité croisée (cf. exercices).
Ensembles bien fondés
La récursion sur les entiers naturels consiste à transformer un problème sur un entier naturel n en un ou plusieurs problèmes sur des nombres plus petits. Comme il n’existe pas de suite infinie strictement décroissante dans l’ensemble des entiers naturels, la récursion finit par atteindre un cas de base comme 0 (ou 1, ou …) pour lequel une solution directe au problème est fournie.
L’ensemble des entiers naturels est dit « bien fondé ».
Récursivité vs itération
La récursivité et l’itération sont deux paradigmes[^2] différents ayant le même objectif : faire effectuer des traitements répétitifs à un ordinateur.
Récursivité, Itération
Un algorithme itératif décritcomment doivent être transformées les données pour parvenir à résoudre le problème.
À chaque « tour de boucle » des affectations sont réalisées.
Un algorithme récursif définit, au sens mathématique du terme, le traitement à mettre en œuvre pour parvenir à résoudre le problème.
Cet algorithme ne s’appuie généralement pas sur la notion d’affectation (Nous reviendrons sur cette partie lorsque nous parlerons des différents paradigmes de programmation).
Tout problème dont la résolution s’appuie sur un algorithme récursif peut aussi être résolu à l’aide d’un algorithme itératif (plus ou moins simplement).
Tout problème dont la résolution s’appuie sur un algorithme itératif peut aussi être résolu à l’aide d’un algorithme récursif.
Les algorithmes récursifs sont généralement plus simples à comprendre que les algorithmes itératifs correspondant.
Avertissement
La version récursive d’un algorithme ne dit pas comment atteindre l’état final d’un traitement, elle donne une définition de ce résultat.
Exemple
L’algorithme récursif du calcul de la factorielle d’un nombre définit cette factorielle.
L’algorithme itératif indique qu’il faut multiplier 1 par 2, stocker le résultat de ce calcul dans une variable, multiplier le contenu de cette variable par 3, …, jusqu’à n.
Info
Certains langages informatiques appelés langages fonctionnels, ne possèdent ni instruction d’affectation ni structure itérative !
Les langages qui privilégient les structures itératives (et l’affectation) sont dits impératifs.
Python est un langage mutli-paradigme : il permet de programmer de façon impérative, objet ou fonctionnelle (même si les appels récursifs, par exemple, ne sont pas aussi bien optimisés en Python que dans les langages fonctionnels).
Pourquoi ne pas toujours utiliser la récursivité ?
Un algorithme récursif est généralement plus facile à comprendre que l’équivalent itératif. On peut donc se demander pourquoi on ne privilégie pas toujours les traitements récursifs.
Généralement, les appels récursifs successifs nécessitent plus d’espace mémoire et de traitements — sachant que les processeurs ont, eux, un fonctionnement fondamentalement itératif — que les processus itératifs.
Les langages fonctionnels modernes possèdent des compilateurs ou des interpréteurs suffisamment « intelligents » pour palier à ces inconvénients.
Si l’on devait résumer l’idée générale de la récursivité
À retenir
Si un problème est facile à résoudre, le résoudre immédiatement.
C’est le cas de base.
Si un problème n’est pas facile à résoudre, le découper en problèmes plus petits. Résoudre les plus petits problèmes.
Ce sont les appels récursifs.
Exercices du chapitre
Penser à écrire, pour chacune des fonctions ci-dessous, sa spécification ainsi qu’un jeu de tests.
Un corrigé partiel se trouve en ligne à cette adresse :
https://repl.it/join/qaeylksn-dlatreyte
. Ce corrigé comporte des exemples d’utilisation de l’instruction assert.
Exercice 1 : Factorielle
Écrire la définition itérative de la fonction factorielle.
Solution
deffactorielle_iter(n:int)->int:"""
Calcule la factorielle de n.
Algortihme itératif.
HYPOTHÈSE : n est un entier naturel
"""fact=1foriinrange(1,n+1):fact=fact*ireturnfactdeffactorielle_rec(n:int)->int:"""
Calcule la factorielle de n.
Algortihme récursif.
HYPOTHÈSE : n est un entier naturel
"""ifn==0:return1else:returnn*factorielle_rec(n-1)
Exercice 2 : Compte à rebours
Écrire une fonction récursive qui, à partir d’un argument entier, affiche un compte à rebours.
En modifiant seulement la position de la fonction print, faire en sorte que le comptage se fasse dans l’ordre croissant.
Solution
defcompte_a_rebours(n:int)->None:"""
Affiche un compte à rebours à l'écran.
"""ifn==0:print(n)returnNoneelse:print(n,end=" ")compte_a_rebours(n-1)returnNonedefcompte(n:int)->None:"""
Affiche un comptage à l'écran.
"""ifn==0:print(n,end=" ")returnNoneelse:compte(n-1)print(n,end=" ")returnNone
Exercice 3 : Somme des N premiers entiers
Écrire les versions itérative et récursive d’une fonction qui calcule la somme des N premiers entiers. La tester pour N=15.
Solution
defsomme_entiers_rec(n:int)->int:"""
Calcule la somme des n premiers entiers.
Algorithme récursif.
HYPOTHÈSE : n entier naturel
"""ifn==0:return0else:returnn+somme_entiers_rec(n-1)defsomme_entiers_iter(n:int)->int:"""
Calcule la somme des n premiers entiers.
Algorithme itératif.
HYPOTHÈSE : n entier naturel
"""somme=0foriinrange(n+1):somme=somme+ireturnsomme
Exercice 4 : Multiplication récursive
Écrire une fonction récursive qui calcule le produit de deux nombres entiers positifs en utilisant des additions.
Le principe est le suivant :
a×b={0(a−1)×b+b si a=0 si a>0
Exécuter la fonction pour a=4 et b=5 (pour cela, présenter les appels récursifs successifs sous forme d’un arbre), puis pour a=5 et b=4.
Pour quel appel l’arbre est-il le plus grand ?
Noter sur quel argument porte la récursion.
Que peut-on en conclure ?
Solution
defmultiplication(a:int,b:int)->int:"""
Réalise la multiplication de deux entiers naturels a et b.
"""ifa==0:return0else:returnmultiplication(a-1,b)+b
Exercice 5 : Calculs de puissances
Écrire une fonction récursive qui calcule xn sachant que :
xn={1xn−1×x si n=0 si n>0
Écrire une fonction récursive qui calcule xn sachant que :
xn=⎩⎨⎧1(xn/2)2(x(n−1)/2)2×x si n=0 si n>0 pair si n>0 impair
Comparer les exécutions (avec arbre des appels) des deux fonctions ci-dessus pour n=11 et x=2. Quel est l’arbre le plus court ? Que peut-on en conclure ?
Solutions
defpuissance_01(x:float,n:int)->float:"""
Premier calcul de la puissance n du nombre x.
HYPOTHÈSE : n entier naturel.
"""ifn==0:return1else:returnpuissance_01(x,n-1)*xdefpuissance_02(x:float,n:int)->float:"""
Second calcul de la puissance n du nombre x.
HYPOTHÈSE : n entier naturel.
"""ifn==0:return1elifn%2==0:inter=puissance_02(x,n/2)# mise en mémoire du résultat de l'appel récursifreturninter*interelse:inter=puissance_02(x,(n-1)/2)# mise en mémoire du résultat de l'appel récursifreturninter*inter*x
Exercice 6 : Suite de Fibonacci
Écrire une fonction récursive qui calcule le nieˋme terme de la « suite de Fibonacci » définie par :
u0u1un=0=1=un−1+un−2pour n⩾2
Exécuter la fonction pour n=5
L’arbre des appels est représenté sur la figure ci-dessous. Expliquer pourquoi cette fonction est très peu efficace.
Solution
deffibonacci(n:int)->int:"""
Calcule le terme n de la suite de Fibonacci.
HYPOTHÈSE : n entier naturel
"""ifn==0:return0elifn==1:return1else:returnfibonacci(n-1)+fibonacci(n-2)
Exercice 7 : Formule de Viète
On peut obtenir une valeur approchée du nombre π grâce à la formule de Viète :
π≈2k2−2+2+…2+2
où k est le nombre de racines carrées. Plus la valeur de k est grande, meilleure est l’approximation.
On constate que la partie s=2+2+…2+2 est récursive.
Écrire une fonction récursive nommée calcul_inter, qui, à partir d’un entier positif k, calcule la valeur de la partie s.
Écrire une fonction nommée calcul_pi, qui, à partir d’un entier positif k, calcule la valeur approchée de π.
Cette fonction doit appeler la fonction calcul_inter.
Depuis la fonction main, appeler la fonction calcul_pi avec plusieurs valeurs de k (essayer 5, 10, 15). Comparer au résultat retourné par l’attribut pi du module math.
Exercice 8 : Plus grand diviseur commun
Écrire une fonction récursive qui retourne le plus grand diviseur commun de deux entiers passés comme arguments. On se servira de l’algorithme d’Euclide :
pgcd(m,n)=⎩⎨⎧mpgcd(n,m)pgcd(n,mmodn) si n=0 si m<n sinon
Solution
defpgcd(m:int,n:int)->int:"""
Calcule le pgcd de m et n. La récursivité est terminale.
HYPOTHÈSE : n et m entiers naturels
"""ifn==0:returnmelifm<n:returnpgcd(n,m)else:returnpgcd(n,m%n)
Exercice 9 : Ackermann-Péter
La fonction d’Ackermann-Péter est définie récursivement comme suit :
A(m,n)=⎩⎨⎧n+1A(m−1,1)A(m−1,A(m,n−1)) si m=0 si m>0 et n=0 si m>0 et n>0
Écrire une fonction qui, à partir de deux arguments m et n, calcule A(m,n). La tester avec les valeurs m=3, n=4.
Remarques
La fonction d’Ackermann croît extrêmement rapidement : A(4,2) a déjà 19729 chiffres !
La fonction d’Ackermann demandant beaucoup de calculs même pour de petites entrées, elle est parfois utilisée comme programme de test d’une implémentation d’un langage de programmation : en particulier, elle utilise de façon très exigeante la récursivité (cf. Fonction d’Ackermann, Wikipédia).
Solution
defackermann(m:int,n:int)->int:"""
Définition de la fonction d'Ackermann.
HYPOTHÈSE : m, n entiers naturels
"""ifm==0:returnn+1elifm>0andn==0:returnackermann(m-1,1)else:returnackermann(m-1,ackermann(m,n-1))
Exercice 10 : Récursivité croisée
On considère deux suites u(n) et v(n) définies, pour n≥0 par :
Ces deux suites ont pour particularité que : v(n)−u(n)=1 pour tout n.
Écrire un programme qui, à l’aide de fonctions récursives, donne les valeurs de ces deux suites pour un n donnée (tester avec n=3) et qui vérifie que la différence entre ces deux valeurs est égale à 1.
Établir les arbres des appels.
Solution
defu(n:int)->int:"""
Calcul de la valeur de u(n).
"""ifn==0:return1else:return3*u(n-1)+2*v(n-1)defv(n:int)->int:"""
Calcul de la valeur de v(n)
"""ifn==0:return2else:return2*u(n-1)+3*v(n-1)defmain():n=int(input("Entrer la valeur de n : "))u_=u(n)v_=v(n)print("u({}) = {}".format(n,u_))print("v({}) = {}".format(n,v_))print("v({}) - u({}) = {}".format(v_,u_,v_-u_))main()
Exercice 10 : Fonctions mutuellement récursives
Le but de cet exercice consiste à écrire les fonctions récursives est_pair et est_impairsans utiliser le modulo.
La fonction est_pair (resp. est_impair) retourne True si son argument entier est pair (resp. impair).
n∈N est impair si n−1 est pair.
n∈N est pair si n−1 est impair.
0 est pair.
0 n’est pas impair.
Solution
defest_pair(nbre:int)->bool:"""
Détermine si un nombre nbre est pair.
HYPOTHÈSE : nbre entier naturel
"""ifnbre==0:returnTrueelse:returnest_impair(nbre-1)defest_impair(nbre:int)->bool:"""
Détermine si un nombre nbre est impair.
HYPOTHÈSE : nbre entier naturel
"""ifnbre==0:returnFalseelse:returnest_pair(nbre-1)defmain():"""Fonction principale"""n=int(input("Entrer le nombre à tester : "))print("Est-il pair ? {}".format(est_pair(n)))main()
Exercice 11 : Conjecture de Syracuse
On appelle suite de Syracuse une suite d’entiers naturels définie de la manière suivante : On part d’un nombre entier plus grand que zéro. S’il est pair, on le divise par 2 ; s’il est impair, on le multiplie par 3 et on ajoute 1. En répétant l’opération, on obtient une suite d’entiers positifs dont chacun ne dépend que de son prédécesseur.
Par exemple, à partir de 14, on construit la suite des nombres :
C’est ce qu’on appelle la suite de Syracuse du nombre 14. Une fois le nombre 1 atteint, la suite des valeurs (1,4,2,1,4,2,…) se répète indéfiniment en un cycle de longueur 3 (appelé cycle trivial).
La conjecture de Syracuse (encore appelée conjecture de Collatz, ou conjecture d’Ulam) est l’hypothèse mathématique selon laquelle la suite de Syracuse de n’importe quel entier strictement positif atteint 1.
Écrire la fonction syracuse à un paramètre entier qui retourne la longueur de la suite de Syracuse de cet entier pour obtenir 1.
Solution
defsyracuse_01(n:int)->int:"""Retourne la longueur de la suite de Syracuse, c'est à
dire le nombre de termes avant que la valeur soit égale à 1.
Récursivité enveloppée.
"""ifn==1:return1elifn%2==0:return1+syracuse_01(n/2)else:return1+syracuse_01(n*3+1)
Ce n’est pas la seule définition possible et c’est loin d’être la plus efficace une fois implémentée. ↩︎
Physique, Chimie et Informatique > Terminales Spé. NSI > Récursivité
La récursivité appliquée aux chaînes de caractères et aux listes
Introduction
Une chaîne de caractère est une structure de données qui permet de rassembler en un unique objet une succession ordonnée de caractères. Ainsi, une définition récursive d’une chaîne de caractères pourrait être :
Définition récursive d’une chaîne de caractères
Une chaîne de caractères est :
soit la chaîne de caractères vide ;
soit constituée de son premier caractère et du reste des caractères qui forment aussi une chaîne de caractères (éventuellement vide).
Une liste est une structure de données qui permet de rassembler en un unique objet une succession ordonnée d’objets (ou de valeurs). Ainsi, une définition récursive d’une liste pourrait être :
Définition récursive d’une liste
Une liste est :
soit la liste vide ;
soit constituée de son premier élément et du reste des éléments qui forment aussi une liste (éventuellement vide).
Exercices
Penser à écrire, pour chacune des fonctions ci-dessous, sa spécification ainsi qu’un jeu de tests.
Recherche dans une chaîne de caractères
Écrire une fonction récursive nommée est_dans, qui, à partir d’un caractère e et d’une chaîne de caractères c, détermine si ce caractère appartient à la chaîne.
Tester cette fonction.
Remarque : la fonction est_dans est un prédicat.
Solution
defest_dans(e:str,c:str)->bool:"""
Détermine si le caractère e est dans la chaîne c.
Version utilisant une sous-chaîne.
Récursivité terminale.
"""ifc=="":returnFalseelifc[0]==e:returnTruereturnest_dans(e,c[1:])defest_dans_02(e:str,c:str,i:int)->bool:"""
Détermine si le caractère e est dans la chaîne c.
Version utilisant un indice et toujours la même chaîne.
Il s'agit toujours d'une récursivité terminale.
"""ifi==len(c):returnFalseelife==c[i]:returnTrueelse:returnest_dans_02(e,c,i+1)defmain():"""Fonction principale."""chaine=input("Entrer la chaîne : ")car=input("Entrer le caractère à recherche : ")print("{} est-il dans {} : {}".format(car,chaine,est_dans(car,chaine)))print("{} est-il dans {} : {}".format(car,chaine,est_dans_02(car,chaine,0)))main()
Recherche de la position d’un caractère dans une chaîne de caractères
Écrire une fonction récursive nommée rang, qui, à partir d’un caractère e et d’une chaîne de caractères c, détermine la (première) position de ce caractère dans la chaîne. Si le caractère n’est pas présent, retourner un nombre négatif.
Tester cette fonction dans un programme.
Solution
defrang(e:str,c:str,i:int)->int:"""
Retourne l'indice de la première position du caractère e dans la
chaîne c ou -1 si le caractère n'est pas présent dans la chaîne.
Remarque : l'indice n'est pas réellement le rang. Faire débuter i
à 0 pour obtenir l'indice, à 1 pour obtenir le rang.
Remarque : récursivité terminale
"""ifc=="":return-1elifc[0]==e:returnielse:returnrang(e,c[1:],i+1)defrang_2(c:str,e:str)->int:"""
Retourne le rang de la première position du caractère e dans la
chaîne c ou un nombre négatif si le caractère n'est pas présent
dans la chaîne.
Récursivité enveloppée.
"""ifc=="":return-float("inf")elifc[0]==e:return1else:return1+rang(c[1:],e)defmain():"""Fonction principale."""chaine=input("Chaîne ? ")car=input("Caractère ? ")indice=rang(car,chaine,0)ifindice>=0:print("Position du carcatères :",indice)else:print("Caractère pas présent dans la chaîne.")main()
Copie d’une chaîne de caractères
Écrire une fonction récursive nommée copie, qui, à partir d’une chaîne de caractères c, retourne une nouvelle chaîne copie de c.
Tester cette fonction.
Solution
defcopie(c:str)->str:"""
Retourne une copie de la chaîne c.
Algorithme récursif.
"""ifc=="":return""else:returnc[0]+copie(c[1:])assertcopie("abcd")=="abcd"assertcopie("a")=="a"assertcopie("")==""
Inversion d’une chaîne de caractères
Écrire une fonction récursive nommée inversion, qui, à partir d’une chaîne de caractères c, retourne la chaîne « mirroir », c’est à dire la chaîne égale à celle passée en argument quand on la lit de droite à gauche.
Tester cette fonction dans un programme.
Solution
definversion(c:str)->str:"""
Inverse une chaîne de caractères.
Version avec sous-chaîne et récursivité enveloppée.
"""ifc=="":return""else:returninversion(c[1:])+c[0]definversion_02(c:str,c_inv:str)->str:"""
Inverse une chaîne de caractères.
Version avec sous-chaîne et récursivité terminale.
"""ifc=="":returnc_invelse:returninversion_02(c[1:],c[0]+c_inv)definversion_03(c:str,i:int)->str:"""
Inverse une chaîne de caractères.
Version sans sous-chaîne et récursivité enveloppée.
"""ifi==len(c):return""else:returninversion_03(c,i+1)+c[i]definversion_04(c:str,c_inv:str,i:int)->str:"""
Inverse une chaîne de caractères.
Version sans sous-chaîne et récursivité terminale.
"""ifi==len(c):returnc_invelse:returninversion_04(c,c[i]+c_inv,i+1)defmain():"""Fonction principale."""chaine=input("Chaîne ? ")chaine_inversee_01=inversion(chaine)print(chaine_inversee_01)chaine_inversee_02=inversion_02(chaine,"")print(chaine_inversee_02)chaine_inversee_03=inversion_03(chaine,0)print(chaine_inversee_03)chaine_inversee_04=inversion_04(chaine,"",0)print(chaine_inversee_04)main()
Détecteur de palindrome
Un palindrome est un mot (ou une phrase) qui se lit aussi bien de la gauche vers la droite que de la droite vers la gauche : par exemple « radar », « kayak », ou bien la phrase « esope reste et se repose » (si l’on ne tient pas compte des espaces).
Écrire une fonction récursive nommée est_palindrome qui reçoit comme argument une chaîne de caractères contenant le mot (ou la phrase). Cette fonction doit tester si les deux caractères opposés sont identiques, puis appeler récursivement la fonction sur la partie de la chaîne qui ne contient pas ces deux caractères (les espaces sont ignorés).
Solution
defest_palindrome(c:str)->bool:"""
Détecte si la chaîne de caractères est un palindrome.
Utilisation d'une sous-chaïne. La récursivité est terminale.
Hypothèse : la chaîne c n'est pas vide.
"""ifc=="":returnTrueelifc[0]!=c[-1]:returnFalseelse:returnest_palindrome(c[1:-1])defest_palindrome_02(c:str,i:int,j:int)->bool:"""
Détecte si la chaîne de caractères est un palindrome.
i est le premier indice de la chaîne, j le dernier.
Utilisation d'une sous-chaîne. La récursivité est terminale.
Hypothèse : la chaîne c n'est pas vide.
"""ifi==j:returnTrueelifc[i]!=c[j]:returnFalseelse:returnest_palindrome_02(c,i+1,j-1)defmain():"""Fonction principale."""chaine=input("Chaîne à tester : ")print("Est un palindrome 01 ? {}".format(est_palindrome(chaine)))print("Est un palindrome 02 ?",est_palindrome_02(chaine,0,len(chaine)-1))main()
Travail sur les listes
Écrire une fonction nommée longueur_liste, récursive, qui, à partir d’une liste passée en argument, détermine sa longueur.
Écrire une fonction nommée somme_elements, récursive, qui, à partir d’une liste de nombres passée en argument, calcule la somme de tous les nombres.
2bis. Écrire une fonction nommée produit_elements, récursive, qui, à partir d’une liste de nombres passée en argument, calcule le produit de tous les nombres.
Écrire une fonction nommée plus_grand_element, récursive, qui, à partir d’une liste d’entiers passée en argument, détermine quel est l’entier le plus grand.
Écrire une fonction nommée plus_petit_element, récursive, qui, à partir d’une liste d’entiers passée en argument, détermine quel est l’entier le plus petit.
Écrire une fonction nommée somme_listes_imbriquees, récursive, qui additionne tous les entiers des listes.
Exemple de listes imbriquées :
l1=[1,[2,[3,4],5],6,[7,8]]l2=[1,[2,[3,[4,[5]]]]]
Remarque.
Cette question peut illustrer, par exemple, la recherche de l’occupation disque de tous les fichiers dans la structure arborescente d’un système de fichiers à partir d’un point de cette structure.
Écrire une fonction nommée duplique, récursive, qui, à partir d’un élément e et d’un entier n, retourne une liste qui contient l’élément e un nombre de fois égal à n.
assertduplique(5,3)==[5,5,5]
Écrire une fonction nommée extrait, récursive, qui, à partir d’une liste l et d’un entier n, retourne une liste constituée par les n premiers éléments de l.
assertextrait([5,4,3,2,1],3)==[5,4,3]
Écrire une fonction nommée renverse, récursive, qui, à partir d’une liste, retourne une liste dans laquelle les éléments sont renversés (les derniers apparaissent en premier).
Écrire une fonction nommée creation_liste_filtree, qui, à partir de deux entiers i et j passés en argument retourne une liste d’entiers compris entre i et j multiples de 3 ou de 5.
assertcreation_liste_filtree(1,10)==[3,5,6,9,10]
Modifier la fonction précédente afin que le filtre « entiers multiples de 3 ou de 5 » soit passé en argument.
Solutions
defplus_grand_element(liste:list)->float:"""
Retourne le plus grand éléments de la liste.
"""ifliste==[]:raiseException("La liste est vide.")eliflen(liste)==1:returnliste[0]else:val_max=plus_grand_element(liste[1:])returnliste[0]ifliste[0]>val_maxelseval_maxdefplus_petit_element(liste:list)->float:"""
Retourne le plus petit élément de la liste.
"""ifliste==[]:raiseException("La liste est vide")eliflen(liste)==1:returnliste[0]else:val_min=plus_petit_element(liste[1:])returnliste[0]ifliste[0]<val_minelseval_mindeflongueur_liste(l:List)->int:"""
Retourne le nombre d'éléments dans une liste.
Récursivité enveloppée.
"""ifl==[]:return0else:return1+longueur_liste(l[1:])deflongueur_liste_02(liste:list,l:int=0)->int:"""
Retourne le nombre d'éléments dans une liste.
Récursivité terminale.
"""ifliste==[]:returnlelse:returnlongueur_liste_02(liste[1:],l+1)defsomme_elements(l:List[float])->float:"""
Retourne la somme des éléments de la liste.
Récursivité enveloppée.
"""ifl==[]:return0else:returnl[0]+somme_elements(l[1:])defsomme_elements_2(l:List[float],s:int=0)->float:"""
Retourne la somme des éléments de la liste.
Récursivité terminale.
"""ifl==[]:returnselse:returnsomme_elements_2(l[1:],s+l[0])defsomme_listes_imbriquees(liste:list,s:float=0)->float:"""
Retourne la somme des éléments de listes imbriquées.
"""iflen(liste)==0:returnselse:ifnotisinstance(liste[0],list):returnsomme_listes_imbriquees(liste[1:],s+liste[0])else:somme_avec_sous_listes=somme_listes_imbriquees(liste[0],s)returnsomme_listes_imbriquees(liste[1:],somme_avec_sous_listes)defsomme_listes_imbriquees(l:List)->float:"""
Retourne la somme de tous les éléments d'une liste,
même si elle contient des sous-listes imbriquées.
"""ifl==[]:return0elifisinstance(l[0],list):returnsomme_listes_imbriquees(l[0])+somme_listes_imbriquees(l[1:])else:returnl[0]+somme_listes_imbriquees(l[1:])defproduit_elements(l:List[float])->float:"""
Retourne le produit de tous les éléments de la liste.
Récursivité enveloppée.
"""ifl==[]:raiseException("La liste est vide.")eliflen(l)==1:returnl[0]else:returnl[0]*produit_elements(l[1:])defproduit_elements_2(l:List[float],p:float=1)->float:"""
Retourne le produit de tous les éléments de la liste.
Récursivité terminale.
"""ifl==[]:raiseException("La liste est vide.")eliflen(l)==1:returnl[0]*pelse:returnproduit_elements_2(l[1:],l[0]*p)defrecherche_element(liste:list,val_rech:int,i:int)->int:"""Ne se contente pas de déterminer si la valeur cherchée est
présente, retourne son indice (on ne cherche que la première
valeur) si possible (sinon -1)."""ifi==len(liste):return-1elifliste[i]==val_rech:returnielse:returnrecherche_element(liste,val_rech,i+1)defmain():l=[-128,-23,123,213,9,2891]nbre_max=plus_grand_element(l)nbre_min=plus_petit_element(l)longueur=longueur_liste(l)somme=somme_elements(l)produit=produit_elements(l)l2=[[1,[1,[1,[1]],1]],1]somme2=somme_listes_imbriquees(l2,0)print("Recherche élément")print(recherche_element(l,12,0))print("Recherche nombre max")print(nbre_max)print(nbre_min)print(longueur)print(somme)print(produit)print(somme2)main()
Physique, Chimie et Informatique > Terminales Spé. NSI > Récursivité
Recherche d'un élément dans un tableau : algorithmes itératifs et récursifs
Recherche d’un élément dans un tableau
La recherche d’éléments dans un tableau a déjà été évoquée en classe de première. Les deux algorithmes mis en œuvre à cette occasion, la recherche linéaire et la recherche dichotomique, utilisaient des boucles.
L’objectif de cette séance est de rapidement revoir ces algorithmes et de mettre en œuvres des algorithmes récursifs de même complexité. Quatre algorithmes de recherche vont donc être implémentés :
La recherche linéaire itérative ;
La recherche linéaire récursive ;
La recherche dichotomique itérative ;
La recherche dichotomique récursive.
Travail à faire
Implémenter en Python les cinq algorithmes suivants et répondre aux questions.
Avertissement
Penser à donner la spécification de chacune des fonctions et écrire une série des tests pour chacune d’elles.
Recherche séquentielle (ou linéaire)
À retenir
La recherche séquentielle (ou linéaire) consiste à
comparer la valeur recherchée à toutes les valeurs présentes dans le tableau.
Recherche séquentielle itérative
Algorithme 1
Fonction : recherche(tab, valeur) Action : recherche la valeur « valeur » dans le tableau « tab » Début i ⟵ 0 i_val ⟵ -1 nb ⟵ Longueur(tab) TantQue i < nb Faire Si tab[i] = valeur Alors i_val ⟵ i FinSi i ⟵ i + 1 FinTantQue Renvoyer i_val Fin
Décrire le fonctionnement de l’algorithme pour les valeurs tab = [1, 8, 3, 5, 9] et val = 3.
Réponse
Démontrer que l’algorithme se termine.
Réponse
Pour démontrer que l’algorithme se termine il faut définir un variant de boucle car c’est au niveau
de la boucle TantQue qu’un problème peut intervenir.
La fonction dont l’expression est f(i)=nb−i est-elle un variant de boucle ?
i et nb sont des entiers naturels. De plus la boucle « tourne » tant que i<nb.
f(i) est donc un entier naturel.
f(ik+1)−f(ik)=nb−ik+1−(nb−ik)=ik−ik+1. Comme
ik+1=ik+1, f(ik+1)−f(ik)=ik−(ik+1)=−1. La fonction
est décroissante.
f est une fonction qui retourne forcément un entier naturel et qui est décroissante ;
elle est donc bornée par la valeur 0, c’est un variant de boucle.
L’algorithme se termine.
Démontrer que l’algorithme est correct.
Réponse
Pour déterminer qu’un algorithme qui comporte une boucle est correct, il faut trouver
un invariant de boucle.
On peut par exemple dire que « La valeur recherchée n’est pas présente dans les éléments du tableau d’indices 0 à i-1, où i est l’indice courant. »
Initialisation : Avant la première itération, i=0, donc l’invariant est vrai trivialement car aucun élément n’a encore été examiné.
Conservation : À chaque itération, on vérifie si l’élément à l’indice i est la valeur recherchée. Si ce n’est pas le cas, on passe à l’élément suivant (i+1). Ainsi, on sait que la valeur recherchée n’est pas dans les éléments précédents.
Terminaison : La boucle se termine soit quand on trouve la valeur (auquel cas l’invariant n’est plus nécessaire), soit quand on a parcouru tout le tableau sans la trouver (auquel cas l’invariant assure que la valeur n’est pas dans le tableau).
Démontrer que l’algorithme est en O(N).
Réponse
L’algorithme contient une boucle dont le nombre de tours est, dans le pire des cas,
égal au nombre d’éléments dans la liste. La complexité est donc linéaire, O(n).
Comment pourrait-on améliorer l’efficacité de cet algorithme ?
Réponse
Il faudrait quitter la boucle dès l’instant où la valeur a été trouvée, si elle
est bien présente dans la liste.
Algorithme 2
Fonction : recherche(tab, valeur) Action : recherche de la valeur « valeur » dans le tableau « tab » Début trouvé ⟵ Faux i ⟵ 0 TantQue i < nb et (Non trouvé) Faire Si tab[i] = valeur Alors trouvé ⟵ Vrai Sinon i ⟵ i + 1 FinSi FinTantQue Si trouvé = Vrai Alors Renvoyer i Sinon Renvoyer -1 Fin
Expliquer pourquoi l’algorithme 2 est plus efficace que l’algorithme 1.
Réponse
On quitte la boucle dès l’instant où la valeur a été trouvée, si elle
est bien présente dans la liste.
Recherche séquentielle récursive
Algorithme 3
Fonction : recherche(tab, valeur, i) Action : recherche la valeur « valeur » dans le tableau « tab » à l’aide de l’indice i. Début nb ⟵ Longueur(tab) Si i == nb Alors Renvoyer -1 Sinon Si tab[i] = valeur Alors Renvoyer i Sinon Renvoyer recherche(tab, valeur, i + 1) FinSi FinSi Fin
Décrire le fonctionnement de l’algorithme pour les valeurs tab = [1, 8, 3, 5, 9], i = 0 et val = 3.
Établir, en particulier, l’arbre des appels.
Recherche dichotomique
Dès que le nombre de données devient important, la recherche séquentielle n’est plus envisageable. Sa complexité en O(N) pénalise les autres traitements qui l’utilisent. Il faut diminuer le temps de traitement par l’emploi d’algorithmes plus performants, comme celui de la recherche dichotomique.
À retenir
La recherche dichotomique est basée sur le principe de « diviser pour régner ». On divise l’ensemble de recherche en deux sous-ensembles égaux. On détermine ensuite dans quel sous-ensemble doit se trouver la valeur recherchée, puis on poursuit la recherche dans ce sous-ensemble.
Avertissement
Le préalable à la méthode de recherche dichotomique est de disposer d’un ensemble trié de données, car la détermination du sous-ensemble dans lequel se poursuit la recherche se fait par comparaison entre la valeur recherchée et les valeurs de début et de fin du sous-ensemble.
À retenir
La division par deux de l’ensemble de données de recherche à chaque appel indique que la complexité est en O(logN).
Recherche dichotomique itérative
Algorithme 4
Fonction : recherche(tab, valeur) Action : recherche la valeur « valeur » dans le tableau « tab » Débuttrouvé ⟵ FAUX résultat ⟵ -1 gauche ⟵ 0 droite ⟵ Longueur(tab) - 1 TantQue (gauche <= droite) ET (NON trouvé) Faire milieu ⟵ (droite + gauche) // 2 Si tab[milieu] = valeur Alors resultat ⟵ milieu trouvé ⟵ VRAI SinonSi tab[milieu] < valeur Alors gauche ⟵ milieu + 1 Sinon droite ⟵ milieu - 1 FinSi FinTantQue Renvoyer résultat Fin
Décrire le fonctionnement de l’algorithme pour les valeurs tab = [1, 3, 5, 8, 9] et val = 3.
Réponse
Démontrer que l’algorithme se termine.
Réponse
Variant de boucle :f(g,d)=d−g+1 où d signifie « droite » et g « gauche ».
Au début, g=0 et d=n−1 (où n est la taille du tableau).
Le variant initial est donc n, qui est un entier naturel.
À chaque itération, on a trois cas :
Si l’élément est trouvé, la boucle se termine.
Si l’élément cherché est plus grand que le milieu, on met à jour g=m+1
Si l’élément cherché est plus petit que le milieu, on met à jour d=m−1
Dans les deux derniers cas, la taille de l’intervalle est réduite de moitié (ou presque).
Donc, le variant diminue strictement à chaque itération.
Puisque le variant est initialement positif, diminue strictement à chaque itération, et que la boucle se termine quand il atteint 0 ou 1, on peut conclure que l’algorithme se termine toujours en un nombre fini d’étapes.
Démontrer que l’algorithme est correct.
Réponse
Invariant de boucle : À chaque itération de la boucle, l’élément recherché, s’il est présent dans le tableau, se trouve dans la sous-section de l’intervalle [gauche, droite], où :
gauche est l’indice de début de l’intervalle actuel,
droite est l’indice de fin de l’intervalle actuel.
Initialisation (avant la première itération)
Initialement, les indices gauche et droite sont positionnés de telle sorte que :
gauche = 0, qui représente le premier indice du tableau.
droite = n - 1, qui représente le dernier indice du tableau.
Ainsi, avant la première itération, l’élément recherché se trouve potentiellement dans l’intervalle entier du tableau [0, n - 1], ce qui respecte bien l’invariant de boucle.
Conclusion : L’invariant est vérifié avant la première itération.
Conservation (pendant l’itération)
Supposons que l’invariant soit vrai au début d’une itération, c’est-à-dire que si l’élément recherché est présent, il se trouve dans l’intervalle [gauche, droite].
L’algorithme calcule ensuite l’indice médian : milieu
Il compare l’élément à l’indice milieu avec l’élément recherché x :
Si l’élément au milieu est égal à x : L’algorithme s’arrête, et l’élément est trouvé, ce qui n’est pas en contradiction avec l’invariant.
Si l’élément au milieu est strictement inférieur à x : L’algorithme met à jour la borne gauche : gauche = milieu + 1
Cela signifie que x ne peut pas se trouver dans la sous-partie gauche du tableau (de l’indice gauche à milieu), car les éléments dans cette partie sont tous inférieurs à x. Par conséquent, l’élément recherché, s’il existe, se trouve dans le nouvel intervalle [gauche, droite], et l’invariant est préservé.
Si l’élément au milieu est strictement supérieur à x : L’algorithme met à jour la borne droite : droite = milieu − 1
Cela signifie que x ne peut pas se trouver dans la sous-partie droite du tableau (de milieu à droite), car les éléments dans cette partie sont tous supérieurs à x. Par conséquent, l’élément recherché, s’il existe, se trouve dans le nouvel intervalle [gauche, droite], et l’invariant est préservé.
Conclusion : L’invariant est préservé à chaque itération.
Terminaison
La boucle se termine lorsque l’intervalle devient vide, c’est-à-dire lorsque gauche > droite. Cela signifie que l’élément recherché n’existe pas dans le tableau (sinon, il aurait été trouvé lors des itérations précédentes).
Ainsi, lorsque l’algorithme se termine :
Soit il a trouvé l’élément recherché, ce qui est cohérent avec l’invariant.
Soit l’intervalle est vide, et donc l’élément n’est pas présent dans le tableau, ce qui est également conforme à l’invariant, car l’invariant stipule seulement que si l’élément est présent, il se trouve dans l’intervalle.
Conclusion : À la fin de l’algorithme, l’invariant reste valide et garantit que le résultat final est correct.
Démontrer que l’algorithme est en O(log2N).
Réponse
L’algorithme fonctionne en divisant l’intervalle de recherche par 2 à chaque itération. Ainsi, si le tableau contient n éléments, après une itération, la taille de l’intervalle est réduite à n/2, puis n/4, et ainsi de suite. En général, après k itérations, la taille de l’intervalle est réduite à n/2k.
L’algorithme se termine lorsque l’intervalle ne contient plus qu’un seul élément, ce qui se produit lorsque :
2kn=1
En résolvant cette équation, on obtient :
k=log2(n)
Cela signifie que l’algorithme effectue au plus log2(n) itérations pour un tableau de taille n.
Recherche dichotomique récursive
Algorithme 5
Fonction : recherche(tab, valeur, gauche, droite) Action : recherche la valeur « valeur » dans le tableau « tab » DébutSi gauche > droite Alors Renvoyer -1 Sinon milieu ⟵ (droite + gauche) // 2 Si tab[milieu] = valeur Alors Renvoyer milieu SinonSi tab[milieu] < valeur Renvoyer recherche(tab, valeur, milieu + 1, droite) Sinon Renvoyer recherche(tab, valeur, gauche, milieu - 1) FinSi FinSi Fin
Décrire le fonctionnement de l’algorithme pour les valeurs tab = [1, 3, 5, 8, 9], gauche = 0, droite = 4, et val = 3.
Réponse
Application
Exercice
Écrire un programme de devinette : l’utilisateur choisit un nombre au hasard (compris entre 1 et 50) et l’ordinateur doit découvrir ce nombre. Faire en sorte que le nombre de tentatives de l’ordinateur lui permette de trouver la bonne valeur à coup sur (choisir de façon pertinente ce nombre).
Physique, Chimie et Informatique > Terminales Spé. NSI > Récursivité
Un algorithme est une suite finie et non ambiguë
d’opérations ou d’instructions à réaliser afin de résoudre un problème.
En informatique, pour qu’un algorithme puisse être implémenté, il est
nécessaire de s’assurer que la « suite finie et non ambiguë d’opérations ou
d’instructions à réaliser » s’effectue en une durée finie .
À retenir
Lorsqu’on élabore ou étudie un algorithme, il est donc nécessaire de
vérifier :
Sa finitude : Il doit se terminer en un temps fini.
Sa correction : Il doit (généralement) donner le bon résultat.
Sa performance : Plusieurs algorithmes peuvent permettre de résoudre une même
classe de problèmes. Ils ne nécessiteront cependant pas tous l’utilisation de
la même quantité de mémoire ou le même nombre d’étapes de calcul, donc la
même durée.
Remarques
Ce n’est pas toujours une mauvaise nouvelle si certains algorithmes ont besoin d’un « temps infini » pour résoudre un problème : certains choix en cryptographie reposent sur l’idée que « casser » la protection nécessite une durée de calcul trop grande, pour le matériel dont on dispose aujourd’hui.
Pour certains problèmes on doit se contenter d’une solution approchée et pas d’une solution exacte.
À retenir
La performance d’un algorithme porte sur deux aspects : la durée du
calcul et la quantité de mémoire nécessaires à la résolution du
problème. Malheureusement ces deux points s’opposent . Il est souvent
nécessaire d’occuper davantage de mémoire pour gagner en temps de calcul, ou
d’écrire plus d’instructions, et donc faire plus de calculs, pour aboutir à
une gestion de la mémoire optimale.
Conformément au programme, on limite la performance algorithmique à la complexité algorithmique.
Notion de complexité algorithmique
Introduction
À retenir
La complexité algorithmique donne des informations
sur la durée du calcul nécessaire à la résolution du problème. Plus
la complexité algorithmique est petite, moins de calculs sont effectués et
plus l’algorithme est performant (sous réserve que la gestion de l’espace
mémoire utilisé par l’implémentation de l’algorithme ne constitue pas un
problème).
Avertissement
On exprime la complexité d’un algorithme en fonction de la taille (nombre)
des données qu’il manipule en considérant que chaque instruction
élémentaire s’effectue en temps constant.
Il existe plusieurs méthodes pour analyser la complexité d’un algorithme,
comme :
L’analyse moyenne : Il s’agit d’évaluer comment varie la durée moyenne des
calculs à effectuer en fonction du nombre de données manipulées.
L’analyse optimiste Il s’agit d’évaluer comment varie le nombre de calculs à
effectuer, dans le scénario le plus favorable, en fonction du nombre de
données manipulées.
Par exemple, on cherche une valeur dans une liste et c’est la première qui apparaît lors de cette recherche.
L’analyse pessimiste (ou du pire cas) : Il s’agit d’évaluer comment varie le
nombre de calculs à effectuer, dans le scénario le moins favorable, en
fonction du nombre de données manipulées.
Par exemple, on cherche une valeur dans une liste alors qu’elle n’est pas présente dans la liste.
Lorsqu’on utilise le résultat de l’analyse du « pire cas », aucune
mauvaise surprise ne peut intervenir, le pire cas à été envisagé à
l’avance.
Les complexités des différents algorithmes varient beaucoup. On peut
néanmoins regrouper les algorithmes en quelques grandes familles :
Complexité constante : Leur notation est de la forme O(1). Ces algorithmes sont indépendants du nombre de données à traiter.
Info
La complexité constante apparaît dans la recherche par index dans un tableau. La complexité constante est la plus « performante ».
Les algorithmes logarithmiques : Leur notation est de la forme O(logN). Ces
algorithmes sont très performants en temps de traitement. Le nombre de calculs
dépend du logarithme du nombre de données à traiter.
Sur la Figure ci-dessous, on peut constater que, plus le nombre de données N à
traiter est important, moins le nombre de calcul à effectuer augmente
rapidement — la valeur de la dérivée est de moins en moins grande.
La fonction logarithme à utiliser dépend du problème étudié mais, comme
la complexité est définie à un facteur près, la base du logarithme n’a pas
d’importance.
Info
La complexité logarithmique apparaît dans les problèmes dans lesquels
l’ensemble des données peut être décomposé en deux parties égales, qui
sont elles-mêmes décomposées en 2 (recherche par dichotomie, recherche dans un arbre binaire, etc.). La complexité logarithmique est très « performante ».
Avertissement
Le logarithme à utiliser est alors
la fonction réciproque de f:x⟼2x, c’est à dire log2
(aussi appelé logarithme entier).
Le logarithme entier d’un nombre x supérieur ou égal à 1 est le nombre de fois qu’il faut le diviser par deux pour obtenir un nombre inférieur ou égal à 1.
Les algorithmes linéaires : Leur notation est de la forme O(N). Ces
algorithmes sont rapides. Le nombre de calculs dépend, de manière linéaire,
du nombre de données initiales à traiter.
Info
La complexité linéaire apparaît dans les problèmes dans lesquels on
parcourt séquentiellement l’ensemble des données pour réaliser une
opération (recherche d’une valeur, par exemple). La complexité linéaire est considérée comme « efficace ».
Les algorithmes linéaires et logarithmiques (quasi-linéaire) : Leur notation est de la forme O(NlogN).
Info
La complexité linéaire et logarithmique apparaît dans des problèmes dans lesquels on découpe répétitivement les données en deux parties, que l’on parcourt
séquentiellement ensuite (tri Quicksort par exemple). La complexité quasi-linéaire est considérée comme « assez efficace ».
Les algorithmes de type polynomiale : Leur notation est de la forme O(Nk) où
k est la puissance.
Info
Une complexité quadratique apparaît, par exemple, lorsqu’on parcourt un
tableau à deux dimensions, lorsqu’on effectue un tri par comparaison, etc. La complexité polynomiale est considérée comme « moyennement efficace ».
Les algorithmes exponentiels ou factoriels : Leur notation est de la forme O(eN) ou O(N!). Ce sont les algorithmes les plus complexes.
Le nombre de calculs augmente de façon exponentielle ou factorielle en
fonction du nombre de données à traiter. Un algorithme de complexité
exponentielle traitera, dans le pire des cas, un ensemble de 10 données en
effectuant 22026 calculs ; un ensemble de 100 données en effectuant 2,688⋅1043 calculs !!!
On dit généralement que les problèmes produisant ce type d’algorithmes sont
« non calculables ».
Info
On rencontre les algorithmes de type exponentiels ou factoriels dans les problématiques liées à la
programmation de fonctions humaines comme la vision, la reconnaissance des
formes ou l’intelligence artificielle.
Complexité
Durée pour N=106
Logarithmique : O(logN)
10 ns
Linéaire : O(N)
1 ms
Quadratique : O(N2)
1/4 heure
Polynomiale : O(Nk)
30 ans si k=3
Exponentielle : O(2N)
plus de 10300000 milliards d’années
Ordres de grandeur des durées d’exécution d’un problème de taille 106 sur un ordinateur à un milliard d’opérations par seconde (« Informatique pour tous en CPGE », éditions Eyrolles).
Quelques règles simples permettant de déterminer la complexité d’un algorithme
Nous allons introduire, dans cette partie, quelques règles simples qui permettent de se faire une idée de l’efficacité d’un algorithme :
Une affectation ou l’évaluation d’une expression ont un temps d’exécution petit. Cette durée constitue souvent l’unité de base dans laquelle on mesure le temps d’exécution d’un algorithme.
Le temps pris pour exécuter une séquence d’instrutions p q est la somme des temps pris pour exécuter les instructions p puis q.
Le temps pris pour exécuter un test Si (b) Alors p Sinon q FinSi est inférieur ou égal au maximum des temps pris pour exécuter les instructions p et q, plus une unité qui correspond au temps d’évaluation de l’expression b.
Le temps pris pour exécuter une boucle Pour i variant de 1 à m par pas de 1 Faire p FinPour est m fois le temps pris pour exécuter l’instruction p si ce temps ne dépend pas de la valeur de i.
En particulier, quand deux boucles sont imbriquées, le corps de la boucle interne est répété à cause de cette boucle, mais aussi parce qu’elle-même est répétée dans son intégralité. Ainsi, si les deux boucles sont répétées respectivement m et m′ fois, alors le corps de la boucle interne est exécuté m×m′ fois en tout.
Quand le temps d’exécution du corps de la boucle dépend de la valeur de l’indice i, le temps total d’exécution de la boucle est la somme des temps d’exécution du corps de la boucle pour chaque valeur de i.
Le cas des boucles Tantque est plus complexe puisque le nombre d’itérations n’est en général pas connu à priori. Il doit être évalué au cas par cas.
Exercice
Pour chacun des programmes suivants, dire en fonction de n quel est le nombre d’opérations op que le programme effectue. Justifier votre résultat.
Pour i de 1 à n Faire
op
Pour i de 1 à n Faire
op; op
Pour i de 1 à n Faire
Pour j de 1 à n Faire
op
Pour i de 1 à n Faire
Pour j de 1 à n Faire
Pour k de 1 à n Faire
op
Pour i de 1 à n Faire
op; op
Pour j de 1 à n Faire
op
Pour k de 1 à n Faire
op
Pour i de 1 à n Faire
Pour j de 1 à i Faire
op
i ⟵ 1
j ⟵ 1
TantQue (i ≤ m) et (j ≤ n) Faire
op
i ⟵ i + 1
j ⟵ j + 1
i ⟵ 1
j ⟵ 1
TantQue (i ≤ m) ou (j ≤ n) Faire
op
i ⟵ i + 1
j ⟵ j + 1
Tant que n > 0 Faire
op
n ⟵ n // 2
Comment illustrer l’influence du nombre d’éléments passés en entrée
Quelques complexités à tout de suite identifier
En utilisant la fonction time du module time, écrire le code de fonctions qui :
montre que le temps d’accès à un élément d’une liste est en O(1) ;
montre que la recherche linéaire dans une liste est en O(N) ;
met en évidence la complexité de l’opérateur Python in ;
montre que la recherche linéaire dans une liste à deux dimensions est en O(N2) ;
montre que la recherche dichotomique dans une liste triée est en O(log(N)).
Terminaison d’un algorithme itératif : variant de boucle
La structure qui généralement doit retenir l’attention lors de l’analyse de
la terminaison d’un algorithme est la structure de boucle.
À retenir
On appelle variant d’une boucle une fonction qui a
pour variables les variables du problème, qui retourne une valeur entière positive et
qui décroît à chacune des itérations de la boucle, jusqu’à s’annuler ou
prendre une valeur constante négative qui dépend de la condition d’arrêt de
la boucle.
La découverte d’un variant de boucle permet de conclure que la boucle se
termine puisqu’il n’existe aucune suite infinie strictement décroissante d’entiers naturels.
Exemple 1 : Calcul de la plus petite puissance de deux supérieure ou égale à un entier n
Algorithme 1
Fonction :plusPetitePuissance(n) Entrée :entier naturel n Sortie :entier naturel p dont la valeur est égale à la plus petite
puissance de deux supérieure ou égale à n. Début p⟵1 TantQuep<nFaire p⟵2p FinTantQue Fin
Info
La fonction f d’expression f(p)=n−p est-elle un variant de boucle ?
f(p) est un entier positif.
Tant que p<n, f(p)>0
f décroît sur l’ensemble des valeurs de p puisque
f(pi+1)−f(p)=n−pi+1−n+pi=pi−pi+1=pi−2pi=−pi<0
Condition d’arrêt :pmax⩾n, donc f(pmax)⩽0.
La fonction f est un variant de boucle et la boucle se termine donc bien.
Exemple 2 : Palindrome
Algorithme 2
Fonction :palindrome(m) Entrée :chaîne de caractères m Sortie :booléen Vrai si la chaîne de caractères m est un palindrome, Faux sinon Début i⟵0 j⟵longueur(m)−1 TantQuei⩽jFaire Sim[i]=m[j]Alors i⟵i+1 j⟵j−1 Sinon Renvoyer Faux FinSi FintantQue Renvoyer Vrai Fin
Décrire au moyen d’un tableau indiquant l’évolution des valeurs des
variables le fonctionnement de l’algorithme 2 pour la chaîne de caractères
« sauras » puis pour la chaîne de caractères « radar ». Remarque : Le premier élément d’une chaîne a pour indice 0.
Réponse
Pour l’entrée « sauras » : i : 0, 1, 2 j : 5, 4, 3
La fonction retourne Faux.
Pour l’entrée « radar » : i : 0, 1, 2, 3 j : 4, 3, 2, 1
La fonction retourne Vrai.
Montrer que f(i,j)=j−i est un variant de la boucle TantQue.
Réponse
f(i,j)=j−i est-elle un variant de boucle ?
Tant que j>i, f(i,j) est un entier positif et f(i,j)=j−i>0.
f(i+1,j−1)=j−1−(i+1)=j−1−i−1=j−i−2=f(i,j)−2<f(i,j).
La fonction est donc décroissante sur l’ensemble des valeurs de i et de j.
Condition d’arrêt :i>j, donc f(i,j)=j−i<0
En déduire que la boucle TantQue se termine.
Réponse
La fonction f est un variant de boucle. La boucle se termine donc bien.
Correction d’un algorithme itératif : invariant de boucle
À retenir
On appelle invariant d’une boucle une propriété qui,
si elle est vraie avant l’exécution d’une itération, le demeure après
l’exécution de l’itération.
Un invariant de boucle doit être vrai avant de commencer la boucle et est
alors garanti de rester correct après chaque itération de la boucle. En
particulier, l’invariant sera toujours vrai à la fin de la boucle.
Les boucles et la récursivité étant fondamentalement similaire, il y a peu de
différence entre démontrer un invariant de boucles et prouver qu’un programme
est correct en utilisant un raisonnement par récurrence.
Exemple 3 : Calcul de 2n
Algorithme 3
Fonction :calculPuissanceDeux(n) Entrée :entier naturel n Sortie :entier naturel p dont la valeur est égale à 2n Début p⟵1 Pourkallant de 1 à nfaire p⟵2p FinPour Fin
Info
La propriété « À chaque tour de boucle p est une puissance de 2 » est un invariant de
boucle. En effet :
Initialisation : Avant d’entrer dans la boucle : p=1=20.
Conservation : On suppose l’invariant vérifié au tour i de la boucle : p=2i. Au tour i+1, pi+1=pi×2=2i×2=2i+1.
Terminaison : La boucle réalise n tours ; au dernier tour p=2n−1×2=2n
La proposition est donc bien un invariant de boucle et on peut conclure que l’algorithme est correct.
Exemple 4 : Quotient et reste de la division euclidienne d’un entier positif par un entier strictement
Algorithme 4
Fonction :division(a, b) Entrée :entiers naturels a et b Sortie :Quotient q et reste r de la division euclidienne
de l’entier naturel a par l’entier naturel b Début q⟵0 r⟵a TantQuer⩾bFaire q⟵q+1 r⟵r−b FinTantQue Renvoyerq,r Fin
Décrire le fonctionnement de l’algorithme pour l’entrée (a = 17, b = 5) au moyen d’un tableau indiquant l’évolution des valeurs des variables
au fil des itérations.
Réponse
abqr1750171751121752717532
Montrer que la boucle TantQue se termine en utilisant un variant de
boucle.
Réponse
La fonction f(r)=r−b peut-elle être un variant de boucle ?
f(r)=r−b est un entier.
Pour n’importe quel tour de boucle r⩾b, donc f(r)=r−b⩾0.
Soit r2=r1−b. f(r2)=r2−b=r1−b−b=f(r1)−b⩽f(r1).
La fonction f est décroissante.
Condition d’arrêt :r<b, donc f(r,b)=r−b<0.
La fonction f est bien un variant de boucle et cette boucle se termine.
Montrer que la propriété a=bq+r est un invariant de la
boucle TantQue, en déduire que l’algorithme produit le résultat
attendu.
Réponse
Si la propriété a=bq+r est un invariant de boucle, elle doit être vraie avant d’entrer dans la boucle, à chaque tour de boucle et une fois la boucle terminée.
Initialisation : Avant d’entrer dans la boucle, q=0 et r=a. Donc on a bien a=0×b+a.
Conservation : On suppose la propriété vraie au rang k quelconque de la boucle : a=bqk+rk.
Au rang k+1, qk+1=qk+1 et rk+1=rk−b. Donc a=bqk+1+rk+1=bqk+b+rk−b=bqk+rk.
Terminaison : La boucle s’arrête lorsque r<b. Au dernier tour de la boucle on a donc bien a=bq+r.
La propriété a=bq+r est bien un invariant de boucle et le programme est correct.
Écrire le code Python implémentant l’algorithme 4. La spécification de la fonction est la suivante :
defdivision_euclidienne(a:int,b:int)->tuple[int,int]:"""
Calcule la division euclidienne de l'entier naturel a par l'entier naturel b.
Retourne les entiers naturels q et r, quotient et reste de cette division.
"""
Réponse
defdivision_euclidienne(a:int,b:int)->tuple[int,int]:"""
Calcule la division euclidienne de l'entier naturel a par l'entier naturel b.
Retourne les entiers naturels q et r, quotient et reste de cette division.
"""q=0r=awhiler>=b:q=q+1r=r-breturnq,r
Écrire un jeu de tests pour la fonction division_euclidienne.
Réponse
Existe-t-il un ou des algorithmes qui réalisent la même opération plus efficacement ?
Réponses
la fonction trouve le plus grand élément dans la liste passée en argument.
f(i)=i−1 avec i=len(s) est-il un variant de boucle ?
f(i0)=len(s)−1 est un entier naturel si la liste s n’est pas vide.
f(ik+1)−f(ik)=len(s[1:])−1−len(s)+1=len(s[1:])−len(s)<0
La fonction f est strictement décroissante.
ider=1, f(ider)=1−1=0. f est un variant de boucle et la boucle se termine.
Invariant de boucle :
Exercice
On considère la fonction somme_premiers_entiers qui implémente l’algorithme :
Algorithme 5
Fonction :somme_premiers_entiers(n) Entrée :entier naturel n Sortie :somme des n premiers entiers naturels Début somme⟵0 i⟵1 TantQuei⩽nFaire somme⟵somme+1 i⟵i+1 FinTantQue Renvoyer somme Fin
Implémenter en Python l’algorithme proposé. Ne pas oublier la spécification de la fonction.
Écrire un jeu de test pour cette fonction.
Prouver que la boucle se termine à l’aide du variant de boucle f(n,i)=n−i où i est le compteur de la boucle.
Prouver que la proposition : « au début du tour du kième tour de la boucle, la variable somme est égale à la somme des k−1 premiers entiers naturels » est un invariant de boucle. En déduire que l’algorithme est correct.
Quelle est la complexité de cet algorithme ?
Réponses
defsomme_premiers_entiers(n:int)->int:"""
Calcule la somme des n premiers entiers.
HYPOTHÈSE : n entier naturel
"""somme=0i=0whilei<=n:somme=somme+ii=i+1returnsomme
Pour n’importe quel tour de boucle, on a i⩽n. Donc f(n,i)=n−i⩾0 ;
Au rang k+1, ik+1=ik+1 donc f(n,ik+1)=n−ik+1=n−ik−1=f(n,ik)−1<f(n,ik). La fonction f décroit lorsque la boucle progresse.
condition d’arrêt :i>n, donc f(n,i)=n−i<0.
La fonction f est positive, décroissante lorsque la boucle « tourne » et finalement prend une valeur négative lorsque la boucle est terminée ; c’est un variant de boucle. La présence d’un variant de boucle nous assure que la boucle se termine.
Initialisation : Avant d’entrer dans la boucle, somme=0.
Conservation : On suppose que somme=0+1+…+k−1 au début de la kième boucle.
Pendant la kième boucle, on a somme=somme+k=0+1+…+k−1+k.
Au début de la k+1ième boucle, on a donc bien somme=0+1+…+k.
Terminaison : La boucle s’arrête dès que i>n. Donc au début du n+1ième tour (tour de boucle qui n’aura jamais lieu), on a bien somme=0+1+…+n.
La proposition est bien un invariant de boucle, elle nous assure que le programme est corret.
Physique, Chimie et Informatique > Terminales Spé. NSI > Récursivité
Le mot fractale vient du latin fractus qui signifie brisé. En effet, une
figure fractale est un objet géométrique infiniment morcelé des détails
sont observables à une échelle arbitrairement choisie.
En zoomant sur une partie de la figure, on peut retrouver toute la
figure, on dit qu’elle est auto similaire.
Dans le code suivant (qu’il faudra étudier et exécuter) :
Quel est le cas de base de l’algorithme récursif ?
Où s’effectue l’appel récursif ?
Pourquoi le cas de base est-il toujours réalisé ?
importturtleimportmathasmdefdessine_etoile(t:turtle,pt:tuple,long:int)->None:iflong<=2:returnNoneforiinrange(6):x_ext=pt[0]+int(long*m.cos((2*m.pi/6)*i))y_ext=pt[1]+int(long*m.sin((2*m.pi/6)*i))pt_ext=(x_ext,y_ext)# Extrémité du segmentt.penup()t.setposition(pt)t.pendown()t.setposition(pt_ext)dessine_etoile(t,pt_ext,long/3)defmain():t=turtle.Turtle()t.speed(0)t.hideturtle()segment=300centre=(0,0)dessine_etoile(t,centre,segment)turtle.mainloop()main()
Le flocon de von Koch
La première courbe à tracer a été imaginée par le mathématicien suédois
Niels Fabian Helge von Koch, afin de montrer que l’on pouvait tracer des
courbes continues en tout point, mais dérivables en aucun.
Le principe est le suivant : on divise un segment initial en trois morceaux,
et on construit un triangle équilatéral sans base au-dessus du morceau
central. On réitère le processus n fois, n étant appelé l’ordre.
Ordres 0, 1, 2 et 3 de la fractale.
Si on trace trois fois cette figure, on obtient successivement un
triangle, une étoile, puis un flocon de plus en plus complexe.
Figures successives (ordre 0, 1, 2 et 4).
Principe de la construction
Info
La méthode de construction utilise un algorithme récursif :
À l’ordre 0, il suffit d’appeler une fois la méthode forward pour tracer un segment. C’est le cas de base.
À l’ordre 1, il faut appeler la méthode forward (4 fois), les méthodes left et right pour découper le segment en 4 parties (de même longueur).
À l’ordre n≥1, le code ressemble à celui de l’ordre 1, si ce
n’est qu’on remplace l’appel de chacune des méthodes forward par le tracé de
segments à l’ordre n−1. C’est l’appel récursif, on découpe chaque
partie de segment en sous-parties.
Travail
Définir la fonction de signature
koch_1(t:turtle,l:int)->None
qui dessine un segment de Koch à l’ordre 1, de longueur l, à l’aide de l’objet de type Turtle t. Les sous-segments de la figure sont de longueur l/3 et les angles
sont de 60 ou 120 degrés.
Définir la fonction main permettant de tester la fonction koch_1.
Remarque.
Les futurs tracés vont nécessiter beaucoup de calculs et
l’affichage de nombres points à l’écran. De façon à améliorer la
performance,
régler la vitesse de la tortue au maximum : t.speed(0) ;
cacher le symbole représentant la tortue à l’écran : t.hideturtle.
Définir la fonction de signature
koch(t:turtle,n:int,l:int)->None
qui dessine à l’écran un segment de
Koch d’ordre 0 ou 1, de longueur l, à l’aide de l’objet de type
Turtle t.
Le corps de la fonction doit uniquement gérer les deux cas : n=0
et n=1 (le cas n≥1 sera traité dans l’une des prochaines
questions.
Modifier la fonction main de façon à tester la fonction koch.
Cette partie généralise la fonction koch au cas n≥2. Il faut
découper chaque segment de droite en sous-parties ; il faut donc
remplacer chaque appel de la méthode forward dans koch par un appel de la
fonction koch elle-même : koch(t, n-1, ...).
Trouver par quoi remplacer les … et modifier la fonction.
Tester koch la nouvelle fonction pour une longueur de 300 pixels et
n∈[0,5] (au delà de cette dernière valeur, on ne voit plus
trop de différences).
Définir la fonction de signature qui dessine à l’écran
un flocon de von Koch, d’ordre n et dont chaque segment à une
longueur l.
Solution
"""
Tracé du flocon de Von Koch
"""importturtledefkoch_0(t,l):"""
koch_0 : Objet[turtle] * Entier/>0/ -> None
koch_0(t, l) trace à l'écran un segment de longueur l.
"""t.forward(l)defkoch_1(t,l):"""
koch_1: Objet[turtle] * Entier/>0/ -> None
koch_1(t, l) dessine une branche de longueur l du flocon de Von Koch à
l'ordre 1.
"""t.forward(l/3)t.left(60)t.forward(l/3)t.right(120)t.forward(l/3)t.left(60)t.forward(l/3)defkoch(t,n,l):"""
koch : Objet[turtle] * Entier/>0/ * Entier/>0/ -> None
koch(t, n, l) dessine une branche du flocon de Von Koch à
l'ordre n.
"""ifn==0:t.forward(l)else:koch(t,n-1,l/3)t.left(60)koch(t,n-1,l/3)t.right(120)koch(t,n-1,l/3)t.left(60)koch(t,n-1,l/3)defdessine_flocon(t,n,l):"""
dessine_flocon : Objet[turtle] * Entier/>0/ * Entier/>0/
-> None
dessine_flocon(t, n, l) dessine un flocon de Von Koch à
l'ordre n.
"""ifnott.isdown():t.pendown()koch(t,n,l)t.right(120)koch(t,n,l)t.right(120)koch(t,n,l)t.right(120)defmain():fen=turtle.Screen()fen.bgcolor("black")t=turtle.Turtle()t.color("white")t.speed(0)t.hideturtle()t.penup()t.goto(-150,150)t.pendown()dessine_flocon(t,5,400)# koch(t, 4, 300)# koch_1(t, 200)fen.exitonclick()main()
Arbre fractal
On peut appliquer le même principe pour construire d’autre fractales
visuellement différentes, mais construites sur le même principe.
Présentation
> Arbre fractal.
Par exemple, pour construire un arbre, on part d’un segment, et on
applique la transformation présentée ci-dessus à
chaque segment de la construction (on refait la transformation n fois
pour obtenir un arbre d’ordre n) :
> Base de la construction d'un arbre.
Les portions dessinées en pointillées sont celles sur lesquelles on
appliquera la transformation à l’ordre suivant (on les appelle les
segments non-terminaux). Les portions dessinées en trait plein sont
des segments qui ne seront pas transformés (on les appellera les
segments terminaux).
Pour transformer un segment non-terminal de longueur l, on trace un
segment terminal de longueur l/3, puis deux segments non-terminaux de
longueur 2l/3 à un angle θ du premier segment.
Travail
Suivre la même démarche que pour le flocon de Koch pour écrire une
fonction de signature qui trace l’arbre, et repositionne la tortue à
son point de départ.
Dans un premier temps, gérer les ordres 0 et 1 (utiliser la méthode
et aucun appel récursif), et tester la fonction. Vérifier en
particulier que la tortue est bien revenue à son point de départ à
la fin de l’exécution de la fonction dans les deux cas (n = 0 et n =
1).
Pour chaque tracé de segment non-terminal, remplacer l’appel à la
méthode par un appel récursif à la fonction , et vérifier le
comportement de la fonction à différents ordres. Cette fois-ci, une
profondeur 10 ou 11 donne un résultat assez joli.
Solution
"""
Programme qui dessine un arbre fractal.
"""importturtleimportmathasmdefarbre(t:turtle,n:int,longueur:int,theta:int)->None:ifn==0:t.color("red")t.forward(longueur)t.backward(longueur)t.color("black")else:t.width(n)t.forward(longueur/3)t.left(theta)arbre(t,n-1,longueur/3*2,theta)t.right(2*theta)arbre(t,n-1,longueur/3*2,theta)t.left(theta)t.backward(longueur/3)defmain():t=turtle.Turtle()t.hideturtle()t.speed(0)t.setheading(90)longueur=300theta=35n=11arbre(t,n,longueur,theta)# enregistrement de l'imagets=turtle.getscreen()ts.getcanvas().postscript(file="arbre.pdf")turtle.mainloop()main()