COURS INFORMATIQUE : RÉCURSIVITÉ - PC

COURS INFORMATIQUE : RÉCURSIVITÉPC

PICON

PICON COURS INFORMATIQUE : RÉCURSIVITÉ 1 / 43

1 Définition de la récursivité

2 Exemples de suites définies par récurrenceRécurrence simpleRécurrence double

3 Des exemples non numériques

4 Exemple de recherche

5 Lire des fonctions récursives

6 Rappels théoriques sur l’algorithmiqueUn algorithme doit être fini !L’algorithme donne le résultat attenduComplexitéTerminaison et correction d’une fonction récursive.Complexité d’une fonction récursive.

7 Avantages et inconvénients de la récursivité

8 Les tours de Hanoï


Sommaire


2 Exemples de suites définies par récurrence




6 Rappels théoriques sur l’algorithmique




Un programme qui fait appel à fonctions extérieures, des boucles etdes tests est appelé itératif.Un programme qui s’appelle lui même dans une des branches d’untest est appelé récursifPour que ce soit possible le langage utilisé doit posséder une pile dite"pile système" qui garde l’état de chaque variable et de chaqueprocédure rendue active à un moment donné, c’est à dire que lecontexte est mis en pile dès qu’on appelle une procédure. À la sortiede la procédure, le système retrouve l’état initial qu’il avait lors del’appel à l’exception des modification faites par la procédureelle-même.L’existence de cette pile rend possible qu’une procédure s’appelleelle-même.


La récursivité permet de résoudre un problème complexe en un ouplusieurs sous-problèmes de structure identique qui sont plus simplesà résoudre.L’expression, célèbre en informatique, pour décrire ce processus est

DIVISER POUR REGNER


Un exemple concret

Une association doit collecter en liquide les cotisations de ses 1000adhérents, cotisations qui s’élèvent à 1 echacune.Décrivons une procédure itérative et une procédure récursive pour lefaire.


Le problème qu’on veut résoudre par récursivité doit avoir quelquescaractéristiques

On doit pouvoir le décomposer en instances plus simples dumême problème.

On doit pouvoir recomposer la solution du problème initial àpartir des solutions des instances plus simples

Les instances doivent devenir à la fin assez simples pour ne plusavoir besoin de diviser.

Si ces conditions sont réalisées, il est raisonnable de tenter unerésolution récursive.


Conditions pour qu’une procédure récursive soit valide :

La procédure doit comporter au moins un test avec deux cas.

L’un des cas doit donner obligatoirement un résultat direct

L’autre cas doit s’appeler elle-même avec d’autres paramètresen principe plus simples.

Donc la procédure doit avoir un ou plusieurs paramètres

Si on ne respecte pas cela, on risque de boucler indéfiniment


Un autre exemple

On dispose d’une pile de 16 pièces. L’une est une contrefaçon et pèseun peu moins que les autres. A l’aide d’une balance à deux plateaux,trouver la pièce contrefaite en 4 pesées par stratégie "diviser pourrégner".

Et en trois pesées ?


Sommaire


2 Exemples de suites définies par récurrenceRécurrence simpleRécurrence double






8 Les tours de HanoïPICON COURS INFORMATIQUE : RÉCURSIVITÉ 10 / 43

Considérons une suite définie par récurrence par une formuleexprimant un+1 en fonction de un et par une valeur initiale u0.Pour N donné, calculer uN.Soit on travaille de façon inductive : on part de u0, on calcule tous lestermes jusqu’à uN.Soit on travaille de façon récursive : on programme un calcul U qu’onlance pour avoir uN. Le programme a besoin de uN−1, qu’il ne connaîtpas. La machine empile le contexte et relance U pour calculer uN−1.Mais cette valeur n’est pas connue. La machine empile le contexteetc...Le programme étant bien fait, au bout d’un certain temps, U vademander à calculer u1 et pour cela il a besoin de u0 qu’il connaît.Il calcule donc u1.La machine dépile alors le contexte précédent et lance le calcul de u2

puisque u1 est connu.Elle dépile le contexte précédent et lance le calcul de u3.jusqu’à uN.


Application plus que classique : Calcul de factorielle n.n = 10.

Application : Soit la suite définie par récurrence par un+1 = 12(un + 1

un)

et u0 = 1.Calcul de u25.


1202 LIBER ABBACI.

On suppose qu’un couple de lapin produit unnouveau couple de lapins tous les mois, que les lapins sont fertiles àpartir de la second mois de vie et que dans la periode considérée, leslapins ne meurent jamais.Calculer à partir d’un simple couple introduit fin Janvier, quelle sera lapopulation à la fin de l’année ?Suite de Fibonacci définie par :u0 = u1 = 1 et un+2 = un+1 +un.


RemarqueFibonacci a introduit en Europe des connaissances acquises lors deses voyages en tant que marchand.La suite a une origine indienne et il en prit connaissance par sesvoyages au Magreb.Parmi les progrès mathématiques qu’il contribua à faire connaître enEurope, on lui doitl’introduction des chiffres arabes ...euh, indo-arabes.


Décomposons les calculs effectués par la première version de ceprogramme.Et si on adoptait une version itérative.


Sommaire










Écrire un programme récursif permettant d’inverser une chaîne decaractère.


On donne des lettres sous forme d’une chaîne de caractères. Générertoutes les combinaisons possibles des lettres données


On donne une chaîne de caractères.1) Convertir tous les caractères en minuscules,2) Supprimer de cette chaîne les espaces, les chiffres et tout ce quin’est pas l’alphabet3) Tester si la chaîne est un palindrome.


Sommaire










Recherche binaire ou recherche par dichotomie.

On donne une liste ordonnée de nombres. On veut atteindre unnombre dont on sait qu’il est dans la liste mais on ne sait pas sonindice.L’idée de l’algorithme est de demander le nombre d’incide médian.Si ce nombre est trop grand, on cherche avant lui, si ce nombre esttrop petit, on cherche après lui et si c’est le nombre cherché, on atrouvé.


La programmation de la version itérative est au programme de sup.

A vos marques, prêts, partez ! Et il nous faudra ensuite une versionrécursive


Sommaire










Que font les fonctions suivantes ?


def devi1(L,M=[]):"""L est une liste"""if not(L) :

return Ma=L.pop(0)if a not in M:

M.append(a)return devi1(L,M)


def devi2(L):if len(L)==1:

return L[0]if L[0]<L[1]:

L.pop(1)else:

L.pop(0)return(devi2(L))


def devi3(a,b):"""a et b sont deux entiers naturels non nuls"""if b==1 :

return areturn a+devi3(a,b-1)


Sommaire






6 Rappels théoriques sur l’algorithmiqueUn algorithme doit être fini !L’algorithme donne le résultat attenduComplexitéTerminaison et correction d’une fonction récursive.Complexité d’une fonction récursive.




Si on veut montrer qu’un procédé est un algorithme, on doit montrerqu’au bout d’un nombre fini d’étapes, le procédé s’arrête. C’est cequ’on appelle la TERMINAISONUne façon de prouver la terminaison est de trouver une variable quicontient un nombre entier positif et dont les valeurs sont strictementdécroissantes. Par propriété des nombres naturels, la suite est finie etle programme s’arrête.


Prenons un exemple : Division euclidienne d’un entier naturel par unautre.

def divEucl(a,b):q=0r=awhile r>=b :

r=r-bq=q+1

return q, r

A chaque passage dans la boucle, r décroit de b> 0 tandis que b estinchangé. Donc la condition r >= b finit par ne plus être satisfaite.On sort donc de la boucle et le résultat est retourné.En faisant un test sur b> 0 on améliore la terminaison en évitant leserreurs d’utilisation.


La variable qui sert au contrôle de la terminaison est parfois appelée"VARIANT DE BOUCLE"On peut se demander si une boucle for échappe à ce problème ? Enthéorie oui, le variant de boucle étant l’indice de boucle.Mais on peut faire n’importe quoi....comme changer la valeur de l’indice dans la boucle (sans problèmeen Python)ou plus subtil, changer l’ensemble où l’on prend des indices


Pour prouver que le résultat calculé est le résultat attendu on utilisedans les boucles for et while un INVARIANT DE BOUCLE.La méthode permet de prouver la correction de l’algorithme.Il s’agit d’une propriété (qui est en fait un booléen) qui est vraie avantl’entrée de la boucle et qui reste vraie à chaque passage de la boucle.Elle est donc vraie en sortie de boucle.Reprenons la division euclidienne


Il existe plusieurs notions de complexité. Nous utiliserons celle encoût ou en temps d’exécution qui dépend de la taille des données.On considère que l’affectation d’une variable, la comparaison et lecalcul d’une opération arithmétique est une unité de coût.Si on enchaîne deux séquences d’instructions, les coûts s’ajoutent.Si il y a un test, le coût est inférieur ou égal au plus grand des coûtsde chacune des branches. On devrait ajouter le coût de l’évaluationde la condition du test.Dans une boucle for, si les instructions de la boucle ont un coût qui nedépend pas de l’indice de boucle, il suffit de multiplier le coût d’uneexécution par le nombre d’exécutions.Si les instructions dans la boucle dépendent de l’indice de boucle, onajoute le coût pour chaque valeur de l’indice ou on calcule un simplemajorant.Enfin pour une boucle while où le nombre de répétitions n’est pasconnu, on majore le nombre de répétions (par une méthode analogueà celle pour la terminaison).


Enfin, on exprime la complexité en O ce qui permet d’avoir un ordrede grandeur cohérent moins dépendant des performances machineset asymptotiquement parlant.


Ce modèle possède de nombreuses imperfections :l’accès aux données, les opérations arithmétiques sur de grandsnombres n’ont pas un coût unitaire.les données peuvent avoir des comportements "moyens", ou aucontraire des comportements particulièrement favorables oudéfavorables.on est parfois interessé par des analyses plus précises et on introduitdes notations en Θ ou Ω pour les exprimer.on peut s’interesser à la place mémoire utilisée plutôt qu’au tempsd’exécution.


On retiendra qu’une complexité en O(ln(n)) est optimale, en O(n)

interessante O(n ln(n)) et O(n2) encore gérable, en O(n3) et plus(exponentielle) ingérable sur des données larges.On se fait une bonne idée en comparant les fonctions log2(n),

√n, n,

n log2(n), n2 et n3 2n et n! pour n = 106 et en considérant qu’uneunité de temps fait 10−9s et en calculant le temps d’exécutiondonnée par la fonction : on va de quelques nanosecondes a desheures voire.... des siècles pour n3 et ne parlons pas de n!. Etpourtant une taille de données de cet ordre n’est pas exceptionnelle.


Attention : la complexité est une mesure asymptotique. Unalgorithme en O(n3) peut être plus performant qu’un algorithme enO(n2) pour de petites valeurs de n.


Exemple de Factorielle.On va montrer par récurrence sur n≥ 0 que la propriété suivante estvraie :Pn : "le programme fact(n) termine et donne la valeur n!.Cette démonstration est facile et rendue possible car on sait qu’onfait un appel à tous les entiers positifs précédents n.Il existe des fonctions récursives dont on ne sait pas démontrer laterminaison, par exemple la suite de Syracuse.


Exemple de Factorielle.Les problèmes "Diviser pour régner"La conception d’un tel algorithme suppose qu’on divise un problèmeen a problèmes de taille n/b, et chaque sous-problème est résolurécursivement.La phase de division et combinaison des résultats partiels a unecomplexité donnée par f(n).C(1) est une constanteC(n) = aC(n/b) + f(n) est la relation de récurrence. La résolution deces suites récurrentes est non triviale.


Sommaire










Avantages :Facilité de compréhension et d’écritureFacilité de preuve

InconvénientsTaile de la pile de récursivité : limitée à 1000 en Python. Espaceoccupé grand.


Sommaire










Crée en 1883 par Edouard Lucas qui fut professeur en ces murs.Il s’agit de déplacer des disques de diamètres différents d’une tour de« départ » à une tour d’« arrivée » en passant par une tour «intermédiaire », et ceci en un minimum de coups, tout en respectantles règles suivantes :on ne peut déplacer plus d’un disque à la fois ;on ne peut déplacer qu’un disque situé au sommet d’une pile ;on ne peut placer un disque que sur un autre disque plus grand quelui ou sur un emplacement vide.On suppose que cette dernière règle est également respectée dans laconfiguration de départ.On va travailler dans la configuration de départ : tous les disquessont empilés par ordre décroissants dans la tour de départ.


Documents

COURS INFORMATIQUE : RÉCURSIVITÉ - PC