Exercices - série 1

I. Exercice 1 : La punition⚓︎

Exercice 1

On veut créer une fonction punition qui écrit n fois un certain texte.

n est un entier positif
texte est une chaine de caractères

Python Console Session

>>> punition(5, "Je dois suivre en classe.")
Je dois suivre en classe.
Je dois suivre en classe.
Je dois suivre en classe.
Je dois suivre en classe.
Je dois suivre en classe.

Voici plusieurs versions

itérativerécursive 1récursive 2récursive 3

Python

def punition(n, texte):
    for i in range(n):
        print(texte)

Cette méthode est ici simple, avec une boucle qui répète n fois une instruction.

Python

def punition(n, texte):
    print(texte)
    punition(n - 1, texte)

Version fausse

L'appel à punition(3, texte) donne ensuite les appels :

punition(2, texte)
punition(1, texte)
punition(0, texte)
punition(-1, texte)
punition(-2, texte)
punition(-3, texte)
... sans limite, ou presque.

Python donnerait alors un message d'erreur que nous verrons plus tard.

Python

def punition(n, texte):
    if n > 0:
        print(texte)
        punition(n - 1, texte)

Le principe de cette version récursive correcte est :

si n est strictement positif,
- on écrit le texte,
- puis il reste à faire la punition n - 1 fois.
sinon, il n'y a rien à faire.

Python

def punition(n, texte):
    if n > 0:
        punition(n - 1, texte)
        print(texte)

Le principe de cette autre version récursive correcte est :

si n est strictement positif,
- on fait la punition n - 1 fois,
- il reste alors une fois le texte à écrire.
sinon, il n'y a rien à faire.

Est-ce plus complexe ?

parfois la récursivité est inutile ;
parfois la récursivité est nettement plus simple ;
parfois la récursivité est presque indispensable, avec des structures de données... récursives. Un chapitre dédié abordera ces structures, on y retrouvera naturellement la récursivité.

Il faudra faire attention à ce que la fonction récursive s'arrête !

II. Exercice 2 : le mot de passe⚓︎

Exercice 2

On veut une fonction verifie_mdp pour vérifier le mot de passe d'un identifiant.

On suppose qu'on dispose déjà de fonctions demande_mdp et message_erreur.

Les deux versions suivantes sont-elles équivalentes ou non ?

Bonne pratique

Une méthode avec plus de sécurité consiste à comparer les signatures (des hash) du mot de passe entré et du mot de passe correct. Une base de données ne devrait pas contenir de mot de passe en clair.

Python

def verifie_mdp():
    # Version itérative
    mdp = demande_mdp()
    while mdp != "secret_1234":
        message_erreur()
        mdp = demande_mdp()

Python

def verifie_mdp():
    # Version récursive
    mdp = demande_mdp()
    if mdp != "secret_1234":
        message_erreur()
        verifie_mdp()

Réponse

Oui, presque équivalentes.

La différence principale étant qu'au bout de 1000 erreurs, Python arrêtera la fonction récursive, alors que l'itérative peut continuer à l'infini.

Exercice 3 : somme des premiers entiers⚓︎

Exercice 3

On veut créer une fonction somme qui renvoie la somme des entiers de 1 à n inclus.

n est un entier
Exemples :
- \(1+2+3+4 = 10\), donc somme(4) renvoie 10.
- \(1+2+3+4+5 = 15\), donc somme(5) renvoie 15.

On pourra constater que

somme(5) est égal à 5 + somme(4).
De manière générale, pour n > 0, somme(n) est égal à n + somme(n - 1).
Pour n = 0, la somme est vide, donc vaut 0. Comme pour tout n < 0.

Python Console Session

>>> somme(0)
0
>>> somme(1)
1
>>> somme(2)
3
>>> somme(3)
6
>>> somme(4)
10

Voici plusieurs versions, à vous de dire, pour chacune, si elle est itérative ou récursive, correcte ou fausse.

version 1version 2version 3

Python

def somme(n):
    for i in range(n):
        total += i
    return total

Réponse

Il y a deux erreurs dans cette version itérative :

il faut initialiser total à 0 avant la boucle ;
l'entier n n'est pas ajouté, pour corriger :
- soit on fait un tour de boucle en plus,
- soit on ajoute i + 1 à chaque tour au lieu de i,
- soit, mieux, on fait une boucle de 1 inclus à n + 1 exclu.

Python

def somme(n):
    print(n + somme(n - 1))

Réponse

Il y a deux erreurs dans cette version récursive :

il faut une structure conditionnelle pour renvoyer 0 si n est négatif ;
il faut renvoyer le résultat et non l'afficher.

Python

def somme(n):
    return n * (n + 1) / 2

Réponse

Il y a deux erreurs dans cette version avec une formule :

il faut une structure conditionnelle pour renvoyer 0 si n est négatif ;
le résultat sera ici un flottant, si n est gigantesque le résultat sera arrondi ; il faut utiliser une division entière avec // 2

Remarque : cette formule est au programme de la spécialité mathématiques, en première.

A vous

À vous de compléter la fonction ci-dessous pour qu'elle réussisse les tests.

Solution itérative

Python

def somme(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

Solution récursive

Python

def somme(n):
    if n <= 0:
        return 0
    else:
        return somme(n - 1) + n

Exercice 4 : Retournement d'une chaine⚓︎

Exercice 4

Écrire une fonction récursive qui renvoie le retournement d'une chaine de caractères.

Indices

Si une chaine texte est non vide :

texte[0] correspond au premier caractère,
texte[1:] est une copie de la suite.

A vous

À vous de compléter la fonction ci-dessous pour qu'elle réussisse les tests.

Réponse

Python

def retourne(texte):
    """Renvoie une copie en miroir de texte"""
    if len(texte) == 0:
        return texte
    else:
        return retourne(texte[1:]) + texte[0]

Les tranches ; mauvaises méthodes

Une copie de tranche avec texte[i:j] est couteux ; il faut recopier chaque caractère.

Nous reprendrons ces exercices avec des fonctions récursives qui prendront deux paramètres i et j comme indices de travail.

Crédits⚓︎

Franck Chambon