Chapitre 05

La récursivité en Python

Introduction

La conception des algorithmes étudiés jusque-là s'appuie sur la méthode itérative, basée sur les boucles, et qui décrit le calcul pas à pas. La récursivité propose une autre approche des traitements, à la fois plus séduisante, plus simple à écrire, mais souvent plus complexe à concevoir.

La description d'un calcul basé sur la méthode itérative définit un traitement élémentaire qui progresse grâce à une boucle, du premier jusqu'au dernier calcul. À la fin de la boucle, le dernier traitement donne le résultat final. Ainsi, le calcul de xN se résume à calculer x1, puis x2, x3, … N fois. Il progresse à chaque nouvelle itération de la boucle, en réutilisant le résultat de l'itération précédente et en le multipliant par x, ce qui correspond au calcul suivant :

xN = (…(((((x)*x)*x)*x)*x)*…)*x          N fois

La récursivité propose une approche opposée. Le calcul final est exprimé en fonction du calcul précédent, ce qui donne : xN = x · xN-1. Avec cette méthode, le calcul se définit par lui-même : c'est la notion de récursivité. Ce formalisme mathématique donne l'impression de ne pas avancer dans la recherche de la solution, car si on connaît la valeur de x, on ne connaît pas celle de xN-1. En poursuivant le raisonnement, on peut exprimer xN-1 comme égal à x · xN-2, et ainsi de suite, jusqu'à obtenir x1 = x. Ainsi, de proche en proche, le calcul devient :

xN = x · xN-1 = x · (x · xN-2) = x · (x · (x · xN-3)) = x · (x · (x · (… · (x · x1)…)))

La méthode itérative utilise clairement une boucle. La valeur initiale (en dehors de la boucle) est 1, soit x0.

La méthode récursive ne peut pas utiliser de boucle, puisque le calcul est exprimé en fonction d'un autre qui n'est pas encore connu, sauf pour la récursion terminale (x1) dont on peut connaître la valeur (la récursion terminale est la dernière étape du traitement récursif).

Le traitement est donc formalisé par une fonction qui décrit le calcul plutôt que de le faire. On parle de fonction récursive car elle s'appelle elle-même. Le fonctionnement d'une telle fonction se passe en deux phases : la descente en profondeur par appels récursifs, puis la remontée du résultat de chaque appel. Voici le détail de ce fonctionnement sur l'exemple du calcul de la puissance d'un nombre.

Python 
def puissance (x,N):
    if N ==0 :
        return 1
    else :
        return x* puissance (x,N -1)

Le premier appel de la fonction puissance(x,N) effectue le calcul de x*puissance(x, N-1). Ce calcul reste en attente, car il déclenche l'appel à la fonction puissance(x,N-1) qui effectue le calcul de x*puissance(x, N-2). Ce calcul reste lui-même en attente du résultat du nouvel appel de la fonction puissance(x,N-2). On voit que, s'il n'y a pas de boucle, il y a bien une répétition de calculs par une suite d'appels en cascade de la même fonction avec des exposants de plus en plus petits. Chaque appel est suspendu par un nouvel appel, dont il attend le résultat. Si l'enchaînement des appels n'est pas contrôlé, on aboutit à une fonction récursive infinie qui provoque un arrêt brutal du programme. Il faut donc prévoir le cas de la récursion terminale, c'est-à-dire de l'appel dont le résultat est obtenu de manière itérative. Dans notre exemple, cela se produit quand la puissance est égale à 1. Alors le résultat de la fonction est x. La condition terminale peut aussi correspondre à l'exposant 0, qui donne le résultat 1. Quand le « fond » des appels récursifs est atteint (la récursion terminale donne un résultat et ne fait plus d'appel), l'appel le plus profond se termine et retourne son résultat à l'appel précédent. Cet appel, qui était en attente d'un résultat, reçoit la valeur de retour, poursuit son calcul, et retourne son résultat à l'appel précédent, qui reprend le traitement suspendu et retourne son résultat, et ainsi de suite. Cette phase constitue la remontée du résultat de chaque appel. Enfin, le premier appel reçoit le résultat final.

L'élégance de cette méthode de programmation tient au fait que le calcul s'effectue de lui-même avec, comme seules informations, la valeur de la récursion finale et la description du calcul.

Définition

Une fonction récursive est une fonction dont la définition contient un (ou plusieurs) appel à elle-même.

Remarques

Pour définir une fonction de façon récursive, il faut :

  • prévoir les "cas de base", c'est-à-dire ceux qui ne nécessitent pas d'appel récursif de la fonction,
  • s'assurer que, dans les appels récursifs, les arguments sont plus "simples" que ceux avec lesquels la fonction a été appelée (ce qui signifie essentiellement qu'ils « évoluent vers le cas de base »),
  • reconstituer correctement la valeur de retour de la fonction à partir du résultat du ou des appels récursifs.

Exemples

Les suites récurrentes sont des exemples classiques

On considère la suite Un définie par :

U0 = 1,    Un+1 = (1/2) · (Un + 2/Un)

La suite Un converge vers √2.

Solution itérative :

Python 
def U(n):
    x=1
    for i in range(1, n+1):
        x=1/2*(x+2/x)
    return(x)

print(U(10))
# Résultat: 1.414213562373095

Solution récursive :

Python 
def V(n):
    if n==0:
        return(1)
    else:
        return(1/2*(V(n-1)+2/V(n-1)))

print(V(10))
# Résultat: 1.414213562373095

Le calcul de la factorielle

Pour n ≥ 0,    n! = ∏i=1n i

Une autre définition mathématique de la factorielle se fait par récurrence :

n! = 1 si n = 0,    n · (n-1)! sinon

Solution itérative :

Python 
def fact(n):
    f=1
    for i in range(1,n+1):
        f=f*i
    return(f)
    
print(fact(10))
# Résultat: 3628800

Solution récursive :

Python 
def fact(n):
    if n==0:
        return(1)
    else:
        return(n*fact(n-1))
    
print(fact(10))
# Résultat: 3628800

Exercices avec corrigés

Énoncés

Exercice 1

Écrire une fonction récursive pour saisir une liste de n entiers positifs.

Exercice 2
Python 
def f (a,b) :
    """a et b sont deux entiers naturels non nuls."""
    if b==1:
        return( a)
    return( a+f (a ,b-1))

print(f(3,6))
  1. Quel est le résultat affiché par ce programme ?
  2. Quel est le cas de base dans cette fonction récursive ?
  3. Qu'est-ce qui garantit dans les appels récursifs que le programme finira par s'arrêter ?
  4. Que retourne f(a,b) (a et b étant des entiers naturels non nuls) ?
Exercice 3

Écrire une fonction NbChiffres(n) prenant en paramètre un entier naturel n (écrit en décimal) et retournant le nombre de chiffres de cet entier n en base 10. Cette fonction sera définie récursivement, en langage Python.

Exercice 4

Écrire une fonction récursive en Python reste(a,b) prenant en arguments deux entiers naturels non nuls a et b et retournant le reste de la division euclidienne de a par b.

Exercice 5

À l'aide des deux propriétés suivantes :

  • pour tous entiers a et b, on a pgcd(a;b) = pgcd(a-b;b).
  • pour tout entier a, on a pgcd(a;0) = a.

Écrire une fonction Python récursive pgcd(a,b) retournant le pgcd des entiers naturels a et b.

Exercice 6

L'objectif de cet exercice est de calculer le PGCD de deux nombres a, b à l'aide de la méthode d'Euclide :

  • PGCD(a, 0) = a
  • PGCD(a, b) = PGCD(b, a mod b) si b ≠ 0

Écrire une fonction Python récursive pgcd(a,b) retournant le pgcd des entiers naturels a et b selon la méthode d'Euclide.

Exercice 7

Écrire une fonction récursive Dec2Bin(n) prenant en paramètre un entier naturel n (écrit en décimal) et retournant la représentation binaire de n sous forme d'une chaîne de caractères.

Exercice 8

Écrire une fonction récursive en Python taille(L) prenant en argument une liste de mots L, et retournant une liste de tuples formés de chacun des mots et de sa taille respective.

Ainsi, taille(['Python','C++']) renvoie [('Python',6),('C++',3)].

Exercice 9

Écrire une fonction Python récursive cleValeur(dico) qui échange les clés et les valeurs du dictionnaire dico. On supposera que le dictionnaire entré ne contient pas de valeurs identiques.

Ainsi, cleValeur({'computer':'ordinateur','keyboard':'clavier'}) renvoie le dictionnaire {'ordinateur':'computer','clavier':'keyboard'}.

Exercice 10

On numérote chaque point du plan de coordonnées (x; y) (où x et y sont des entiers naturels) par le procédé du diagonal de Cantor.

Écrire une fonction numero(x, y), définie de façon récursive, qui retourne le numéro du point de coordonnées (x; y).

Exercice 11
  • La fonction Python compte ci-dessous est telle que :
    • input : chaine une chaîne de caractères et car un caractère
    • output : le nombre de caractère car dans la chaîne.
  • Retrouver ce qui a été effacé (pointillés) :
Python 
def compte( chaine,car ):
    if len( chaine ) ==1:
        if chaine[0]==car:
            return(1)
        else:
            return(0)
    if chaine[0]== car:
        . . . . . . . . . . . . .
    else:
        . . . . . . . . . . . . .

print (compte( 'blablaa' ,'a'))# affiche 3
Exercice 12

Soit la fonction Python suivante :

Python 
def ed(L ,M=[ ] ):
    """ L est une liste """
    if not (L):
        return( M)
    a=L.pop(0)
    if a not in M:
        M.append( a )
    return ed(L ,M)
  • Que renverra l'appel ci-dessous :
Python 
L=[2 ,3 ,2 ,6 ,8 ,9 ,9 ,10 ,9 ,3 ,6 ,7 ,8 ,9]
M=ed(L)
print( M)
  • Proposer une solution itérative.
Exercice 13

Soit une fonction f donnée. En supposant que l'on connaisse un intervalle [a, b] sur lequel la fonction change de signe, c'est-à-dire que f(a) · f(b) < 0. Si la fonction f est continue et strictement monotone, nous savons que cet intervalle contient alors une racine α de f.

La méthode de dichotomie propose de découper l'intervalle [a, b] en deux sous-intervalles [a, c] et [c, b] en posant : c = (a + b)/2. Trois cas sont possibles :

  • Si f(c) est du signe de f(a), la racine appartient à l'intervalle [c, b],
  • Si f(c) est du signe opposé à f(a), la racine appartient à l'intervalle [a, c],
  • Si f(c) = 0, la racine de f est c.

Il suffit de répéter le processus jusqu'à ce que la précision ε demandée soit atteinte. Cette précision est atteinte lorsque |f(c)| ≤ ε.

Écrire une fonction Python récursive implémentant la méthode de dichotomie pour la recherche d'une valeur approchée de la racine d'une fonction f dans un intervalle [a, b].

Tester votre fonction sur f(x) = x² - 2 pour chercher une valeur approchée de √2 dans l'intervalle [0, 2].

Exercice 14

Soit une fonction f donnée. En supposant que l'on connaisse un intervalle [a, b] sur lequel la fonction change de signe, c'est-à-dire que f(a) · f(b) < 0. Si la fonction f est continue et strictement monotone, nous savons que cet intervalle contient alors une racine α de f.

La méthode de Newton consiste à calculer une suite de valeurs (xn) convergeant vers la racine α de l'équation f(x) = 0. Cette méthode est applicable à la double condition : la fonction doit être dérivable et la dérivée ne doit pas s'annuler au voisinage de α.

Partant d'un point x0, on calcule successivement :

x1 = x0 - f(x0)/f'(x0)

x2 = x1 - f(x1)/f'(x1)

⋮

xn = xn-1 - f(xn-1)/f'(xn-1)

Le processus s'arrête lorsque la différence |xn - xn-1| ≤ ε ou bien |f(xn-1)/f'(xn-1)| ≤ ε ; xn est alors une valeur approchée de α.

Écrire une fonction récursive newton(f, df, x0) qui prend une fonction f, sa dérivée df, une valeur de départ x0 = (a + b)/2 et qui retourne l'approximation de la racine lorsque la précision demandée 10-6 soit atteinte.

Tester votre fonction sur f(x) = x² - 2 pour chercher une valeur approchée de √2 dans l'intervalle [0, 2].

Exercice 15

Parties d'un ensemble fini

Le but du problème est d'engendrer l'ensemble 𝒫(𝔼) des parties d'un ensemble fini donné. Les éléments d'un ensemble 𝔼 de cardinal n (le nombre d'éléments de 𝔼) seront stockés dans une liste Python LE de longueur n, donc indexée de 0 à n-1. De plus, une partie de 𝔼 sera représentée par une liste de longueur comprise entre 0 et n et contenant un sous-ensemble de 𝔼. L'ensemble des parties de 𝔼, noté par 𝒫(𝔼), sera représenté par une liste de listes PE (liste de parties de 𝔼) de longueur 2n.

Soit 𝔼 = {a, b, c} un ensemble de 3 éléments. Les sous-ensembles (parties) de 𝔼 sont :

  • ∅
  • {a}
  • {b}
  • {c}
  • {a, b}
  • {a, c}
  • {b, c}
  • 𝔼

L'ensemble des parties de 𝔼 est donc :

𝒫(𝔼) = {∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}

Pour caractériser un sous-ensemble 𝔸 d'un tel ensemble 𝔼, on propose d'utiliser une chaîne de caractères p de longueur n, dont les éléments valent '0' ou '1' et sont définis de la façon suivante : pour tout k entre 0 et n-1, LE[k] est élément de 𝔸 si et seulement si p[k] = '1'.

Par exemple, si 𝔼 = {3, 5, 7} alors LE = [3, 5, 7], n = 3 et :

  • p = '100' correspond à la partie {3}
  • p = '101' correspond à la partie {3, 7}, etc.
  1. Écrire une fonction d'en-tête Partie(LE, p) renvoyant sous forme de liste la partie de l'ensemble 𝔼, stocké dans la liste LE, définie par la chaîne p.
  2. Génération de 𝒫(𝔼) de façon itérative : Lorsqu'un entier j varie de 0 à 2n-1, son écriture en base 2 fournit toutes les chaînes correspondant aux 2n parties d'un ensemble à n éléments.

    Par exemple, pour n = 3 et LE = [3, 5, 7], les écritures en base 2 des entiers de 0 à 7 sont :

    • '000' correspond à la partie ∅ représentée par la liste vide [ ],
    • '001' correspond à la partie {7} représentée par la liste [7],
    • '010' correspond à la partie {5} représentée par la liste [5],
    • '011' correspond à la partie {5, 7} représentée par la liste [5, 7],
    • '100' correspond à la partie {3} représentée par la liste [3],
    • '101' correspond à la partie {3, 7} représentée par la liste [3, 7],
    • '110' correspond à la partie {3, 5} représentée par la liste [3, 5],
    • '111' correspond à la partie {3, 5, 7} représentée par la liste [3, 5, 7].
    1. Écrire une fonction d'en-tête Ajoute1(p) recevant une chaîne p contenant l'écriture en base 2 d'un entier j et renvoyant une chaîne contenant la représentation binaire de l'entier j+1 (en supposant que j < 2l-1, où l est la longueur de p). Pour cette fonction, vous pouvez choisir entre version itérative ou récursive.
    2. Écrire une fonction itérative d'en-tête EnsPartiesI(LE) pour calculer et retourner la liste de toutes les parties de l'ensemble 𝔼 (stocké dans la liste LE).
  3. Génération de 𝒫(𝔼) de façon récursive : En supposant que la fonction Ajoute1(p) est déjà définie, écrire une fonction récursive d'en-tête EnsPartiesR(LE, p) qui renvoie la liste de toutes les parties de l'ensemble 𝔼 (stocké dans la liste LE).
Exercice 16

Calcul de la racine carrée entière d'un entier positif

Pour calculer la racine carrée entière d'un entier positif nous proposons d'effectuer des soustractions successives des nombres impairs. En effet, si p est l'entier solution de la double inéquation :

Σi=1p (2i-1) ≤ n < Σi=1p+1 (2i-1)

alors

p ≤ √n < p+1

et donc p est la racine carrée entière de n.

Exemple : Pour calculer la racine carrée entière de 43, on procède de la manière suivante :

43-1=42, 42-3=39, 39-5=34, 34-7=27, 27-9=18, 18-11=7

La prochaine soustraction 7-13 donnerait un résultat négatif. Au total nous avons effectué 6 soustractions, donc la racine carrée entière de 43 est 6.

Écrire en Python une fonction récursive renvoyant la racine carrée entière d'un entier positif n passé en paramètre.

Exercice 17

Écrire en Python une fonction itérative d'en-tête dict_ch(chaine) renvoyant le dictionnaire du nombre d'occurrences des caractères pour la chaîne passée en paramètre.

  • Exemple :

L'appel dict_ch('programme') retourne le dictionnaire suivant :

{'a': 1, 'r': 2, 'm': 2, 'e': 1, 'o': 1, 'p': 1, 'g': 1}

Exercice 18

Le nombre de combinaisons Cnp représente le nombre de sous-ensembles de cardinal p d'un ensemble de cardinal n. Il est défini par :

Cnp = 1 si p = 0 ou p = n, sinon (n · Cn-1p-1) / p

Soit la fonction combRec(n, p) où n et p sont deux entiers positifs tels que p < n.

Python 
def combRec ( n , p ) :
    if( p  ==  0 or n  ==  p ) :
        return(1)
    else:
        return(n* combRec ( n-1,p-1)//p)

Faire le tournage à la main de la fonction combRec pour l'appel suivant : combRec(6, 4).

Exercice 19

Soit la fonction Python suivante :

Python 
def consecR(L,c,m):
    if len(L)==0:
        return(m)
    if L[0]==0:
        return(consecR(L[1:],c+1,max(m,c+1)))
    else:
        return(consecR(L[1:],0,max(m,c)))
  1. Que renverra l'appel suivant :
    Python 
    print(consecR([1,0,0,2,0,0,0,0,3,0],0,0))
  2. Proposer une version itérative consecI(L) de la fonction consecR.
Exercice 20

Problème proposé dans The USA Computing Olympiad

John le fermier a engagé un photographe professionnel pour prendre en photo certaines de ses vaches. Comme les vaches de John appartiennent à différentes races, il souhaiterait que la photo contienne au moins une vache de chaque race présente dans son troupeau.

Les N vaches de John sont rangées sur une ligne à différentes positions, chacune est décrite par une coordonnée entière (son abscisse sur l'axe des x) ainsi qu'une valeur entière représentant la race. John a prévu de faire une photo d'un ensemble contigu de vaches sur cette ligne. Le prix de la photo est égal à sa taille (c'est-à-dire la différence entre la coordonnée la plus grande et la coordonnée la plus petite des vaches présentes sur la photo).

Vous devez aider John à trouver le prix le plus petit d'une photo où il y a au moins une vache de chaque race appartenant au troupeau de John.

EXEMPLE D'ENTRÉE :

On suppose qu'il y a 6 vaches aux positions 25, 26, 15, 22, 20, 30, dont les races sont respectivement 7, 1, 1, 3, 1, 1.

LA SORTIE :

Le coût le plus petit d'une photographie contenant une vache de chaque race est égal à 4.

DÉTAILS DE LA SORTIE :

La photographie couvrant les coordonnées x = 22 à x = 26 (d'une taille totale de 4) contient chacune des trois races présentes dans le troupeau de John (1, 3 et 7).

Proposer en Python une fonction récursive pour résoudre ce problème.

Exercice 21

L'exponentiation rapide est une méthode utilisée pour calculer rapidement de grandes puissances entières. On peut le formuler de façon récursive ainsi :

xn = 1 si n = 0

xn = (x · x)n/2 si n est pair

xn = x · (x · x)(n-1)/2 si n est impair

Écrire une fonction fastExponentiation qui prend en entrées deux entiers x et n et qui calcule xn de façon récursive selon la méthode ci-dessus.

Exercice 22

Écrivez une fonction Python récursive pour détecter les mots palindromes. Un palindrome est un mot qui se lit aussi bien à l'envers qu'à l'endroit : par exemple, les mots "radar" et "kayak" sont des palindromes. Le programme récursif travaillera sur une chaîne de caractères contenant le mot. Il testera si les deux caractères opposés sont identiques, puis appellera récursivement la fonction sur la partie de la chaîne qui ne contient pas ces deux caractères.

Exercice 23

Les Tours de Hanoï sont un jeu constitué de trois tours symbolisées par des piquets, sur lesquels sont enfilés des disques de tailles différentes, qui forment une pyramide cylindrique. Le nombre de disques est défini au début de la partie, et il est de trois minimum. Le but du jeu est de déplacer la pyramide située initialement sur la tour A vers la tour C.

Chaque phase de jeu ne déplace qu'un seul disque à la fois, d'une tour vers une autre en respectant l'ordonnancement des disques, du plus petit (en haut) vers le plus grand (en bas), sur chaque piquet. Il est donc interdit de déplacer un disque plus grand vers une tour contenant en haut de la pile un disque plus petit.

Voici un exemple de début du jeu : déplacer le premier disque de la tour A vers la tour C, déplacer le deuxième disque de la tour A vers la tour B, déplacer le premier disque de la tour C vers la tour B. Cette suite d'actions équivaut à déplacer les deux premiers disques de la tour A vers la tour B, en respectant les règles indiquées précédemment.

Écrivez une fonction Python récursive de déplacement d'une pile de disques hanoi(nbDisques, depart, intermediaire, arrivee), où nbDisques est le nombre de disques à déplacer, depart le numéro de la tour où se trouvent des disques, arrivee le numéro de la tour cible, et intermediaire le numéro de la tour restante.

Exercice 24

L'objectif de l'exercice est d'écrire une fonction Python pour calculer le maximum d'une liste de nombres. L'idée pour résoudre cette question est de calculer récursivement le maximum de la première moitié de la liste et celui de la seconde, puis de les comparer. Le plus grand des deux sera le maximum de toute la liste. La condition d'arrêt à la récursivité sera l'obtention d'une liste à un seul élément, son maximum étant bien sûr la valeur de cet élément.

Corrigés

Corrigé Exercice 1
Python 
def saisieListe (n,L =[]) :
    try :
        if n ==0 :
            A=L.copy ()
            L.clear ()
            return A
        x= int ( input ())
        if x >0:
            L.append (x)
            return saisieListe (n-1,L)
        else :
            print ('Choisir un entier positif ')
            return saisieListe (n,L)
    except ValueError :
        print ('Veuillez saisir un entier ')
        return saisieListe (n,L)
Corrigé Exercice 2
Python 
def f (a,b) :
    """a et b sont deux entiers naturels non nuls."""
    if b==1:
        return( a)
    return( a+f (a ,b-1))

print(f(3,6))
  1. Quel est le résultat affiché par ce programme ?
    Python 
    >>> print(f(3,6))
18
  2. Quel est le cas de base dans cette fonction récursive ?
    Python 
    if b==1:
    return( a)
  3. Qu'est-ce qui garantit dans les appels récursifs que le programme finira par s'arrêter ?
    Python 
    #la variable b diminue de valeur dans chaque appel récursif
return( a+f (a ,b-1))
  4. Que retourne f(a, b) (a et b étant des entiers naturels non nuls) ?
    Python 
    a*b #le produit de a par b
Corrigé Exercice 3
Python 
def NbChiffres(n):
    if n<10:
        return(1)
    return(1+NbChiffres(n//10))

print(NbChiffres(1284)) # Affiche 4
Corrigé Exercice 4
Python 
def reste(a,b):
    if a-b<0:
        return(a)
    return(reste(a-b,b))

print(reste(10,3))  # affiche 1
Corrigé Exercice 5
Python 
def pgcd(a,b):
    if b==0:
        return(a)
    if a<b:
        a,b=b,a
    return(pgcd(a-b,b))

print(pgcd(10,4)) # Affiche 2
Corrigé Exercice 6
Python 
def pgcd (a,b):
    if b ==0 :
        return (a)
    return ( pgcd (b,a%b))

print ( pgcd (10 ,4)) # Affiche 2
Corrigé Exercice 7
Python 
def Dec2Bin(n):
    if n//2==0:
        return(str(n%2))
    else:
        return(Dec2Bin(n//2)+str(n%2))

print('bin=',Dec2Bin(9)) # Affiche 1001
Corrigé Exercice 8
Python 
def Taille(L,R=[]):
    if len(L)==0:
        return(R)
    x=L.pop(0)
    R.append((x,len(x)))
    return(Taille(L,R))

# ou bien
def Taille1(L):
    if len(L)==0:
        return([])
    x=L.pop(0)
    return([(x,len(x))]+Taille(L))
        
print(Taille(['Python','C++'])) # Affiche [('Python',6),('C++,3)]
Corrigé Exercice 9
Python 
def CleValeur(dico,dico2={}):
    if len(dico)==0:
        return(dico2)
    L=list(dico)
    dico2[dico[L[0]]]=L[0]
    del(dico[L[0]])
    return(CleValeur(dico,dico2))

print(CleValeur({'computer':'ordinateur','keyboard':'clavier'}))
Corrigé Exercice 10
Python 
def numero(x,y):
    if x==0 and y==0:
        return(0)             
    if y==0:
        return(1+numero(0,x-1))
    else:
        return(1+numero(x+1,y-1))

print(numero(1,3)) # Retourne 13
Corrigé Exercice 11
Python 
def compte( chaine,car ):
    if len ( chaine ) ==1:
        if chaine[0]==car:
            return(1)
        else:
            return(0)                       
    if chaine[0]== car:
        return(1+compte(chaine[1:],car))
    else:
        return(compte(chaine[1:],car))

print (compte ('blablaaa','a')) # affiche 4
Corrigé Exercice 12
  • L'appel retourne dans M la liste des éléments distincts de L dans leur ordre d'apparition.
  • Une solution itérative :
    Python 
    def ed(L ):
    M=[ ]
    while 1:
        if not (L):
            return( M)
        a=L.pop(0)
        if a not in M:
            M.append( a )
    return M
Corrigé Exercice 13
Python 
def f(x):
    return x**2 -2

def racineDichoRec (f,a,b) :
    c=(a+b)/2
    if abs (f(c)) <10**( -6) :
        return (c)
    if f(c)*f(a) <0:
        return racineDichoRec (f,a,c)
    else :
        return racineDichoRec (f,c,b )

print ( racineDichoRec (f ,0 ,2))
# Résultat = 1.4142136573791504
Corrigé Exercice 14
Python 
def newton (f, df , x0):
    if abs (f(x0)/df(x0)) <10**( -6) :
        return x0
    else :
        return newton (f, df , x0 - f(x0)/df(x0))

a,b=0 ,2
x0 =(a+b)/2
print ( newton ( lambda x:x**2 -2 , lambda x:2*x, x0))
#Résultat = 1.4142135623746899
Corrigé Exercice 15
Python 
def partie(E,p):
    r=[]
    for i in range(len(p)):
        if p[i]=='1':
            r.append(E[i])
    return(r)

def ajout1(p):
    q=p[::-1]
    for i in range(len(q)):
        if q[i]=='0':
            q=q[0:i]+'1'+q[i+1:]
            break
        if q[i]=='1':
            q=q[0:i]+'0'+q[i+1:]
    return(q[::-1])


def EnsPartiesI(E):
    p='0'*len(E)
    PE=[partie(E,p)]
    for i in range(2**len(p)-1):
        p=ajout1(p)
        PE.append(partie(E,p))
    return(PE)

def EnsPartiesR(E,p):
    if p=='1'*len(p):
        return([E])
    return([partie(E,p)]+EnsPartiesR(E,ajout1(p)))

def EnsPartiesR1(E,p,PE=[]):
    if len(PE)==2**len(p):
        return(PE)        
    PE.append(partie(E,p))
    return(EnsPartiesR1(E,ajout1(p),PE))
    
# programme principal
E=[1,2,3]
p='0'*len(E)

print('itérative')
print(EnsPartiesI(E))
print('récursive')
print(EnsPartiesR(E,p))

print('récursive (autre version)')
print(EnsPartiesR1(E,p))
Corrigé Exercice 16
Python 
def racine(n,i=1):
    if n-(2*i-1)<0:
        return(0)
    return(1+racine(n-(2*i-1),i+1))

print(racine(43)) # Affiche 6

# ou bien
def racine1(n,p=1):
    if n-p<0:
        return(0)
    return(1+racine1(n-p,p+2))

print(racine1(43)) # Affiche 6

# ou bien
def racine2(n,p):
    if n-p<0:
        return(p//2)
    return(racine2(n-p,p+2))

print(racine2(43,1)) # Affiche 6
Corrigé Exercice 17
Python 
def dict_ch(chaine):
    d={}
    for i in range(len(chaine)):
        d[chaine[i]]=chaine.count(chaine[i])
    return(d)

print(dict_ch('programme'))
# Affiche {'a': 1, 'm': 2, 'p': 1, 'r': 2, 'o': 1, 'g': 1, 'e': 1}

#ou bien
def dict_ch1(chaine):
    d={}
    for x in chaine:
        if x not in d:
            d[x]=chaine.count(x)
    return(d)

print(dict_ch1('programme'))
Corrigé Exercice 18
Trace 
combRec(6,4)=6*combRec(5,3)//4
combRec(5,3)=5*combRec(4,2)//3
combRec(4,2)=4*combRec(3,1)//2
combRec(3,1)=3*combRec(2,0)//1
avec combRec(2,0)=1 alors
combRec(3,1)=3*1//1=3
combRec(4,2)=4*3//2=6
combRec(5,3)=5*6//3=10
combRec(6,4)=6*10//4=15
Corrigé Exercice 19

Q1 : print(consecR([1,0,0,2,0,0,0,0,3,0],0,0)) retourne 4 qui correspond à la taille de la plus longue suite de zéros consécutifs.

Q2 : Version itérative

Python 
def consecI(L):
    c=0
    m=0
    for x in L:
        if x==0:
            c=c+1
        else:
            c=0
        m=max(m,c)
    return(m)
print(consecI([1,0,0,2,0,0,0,0,3,0]))

def consecI1(L):
    c=0
    m=0
    for i in range(len(L)):
        if L[i]==0:
            c=c+1
        else:
            c=0
        m=max(m,c)
    return(m)

print(consecI1([1,0,0,2,0,0,0,0,3,0]))
Corrigé Exercice 20
Python 
def Olympiad(V,n,d={},sol=[]):
    if len(V)==0:
        return(min(sol))
        
    d[V[0][1]]=V[0][0]
    V.pop(0)
    if len(d)==n:
        L=list(d.values())
        sol.append(max(L)-min(L))

    return (Olympiad(V,n,d,sol))

# V est une liste de listes
# chaque liste est composée de deux valeurs 
# représentant la position et la race d'une vache

V=[[10,3],[25,7],[ 26,1],[ 15,1],[ 22,3],[ 20,1],[ 30, 1],[31,3],[32,7]]
V.sort()
n=3 # nombre de races
print(Olympiad(V,n))
Corrigé Exercice 21
Python 
def fastExponentiation (x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return fastExponentiation (x*x, n/2)
    else :
        return x * fastExponentiation (x*x, (n -1) /2)

print (" 2^24 = {} (opérateur Python )".format (2**24) )
print (" 2^24 = {} ( fastExponentiation )".format(fastExponentiation (2 ,24)))
Corrigé Exercice 22
Python 
def palindrome (ch):
    if len (ch) <=1:
        return True
    if ch [0]!= ch [-1]:
        return False
    return palindrome (ch [1:len (ch)-1])
Corrigé Exercice 23
Python 
def hanoi ( nbDisques , depart ='A', intermediaire ='B',arrivee ='C'):
    if ( nbDisques > 0):
        hanoi ( nbDisques -1, depart , arrivee , intermediaire )
        print ("Déplace ",depart ,"sur",arrivee )
        hanoi ( nbDisques -1, intermediaire , depart , arrivee )
Corrigé Exercice 24
Python 
def maximum (L,d,f):
    if d == f:
        return L[d]
    m = (d+f) // 2
    x = maximum (L,d,m)
    y = maximum (L,m+1,f)
    return x if x > y else y