Aller au contenu

Écrire une punition

Le tableau à craie de Bart Simpson

Au début de presque chaque épisode des Simpsons, Bart écrit une punition au tableau à craie.

I will not waste chalk. (S1E2)

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
🐍 Console Python
>>> 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

🐍 Script 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.

🐍 Script 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 donne alors un message d'erreur que nous verrons plus tard.

🐍 Script 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.
🐍 Script 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.

La récursivité est-elle 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.

Des chapitres dédiés aborderont ces structures, on y retrouvera naturellement la récursivité.

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

La récursivité est-elle plus efficace ?

  • souvent une version récursive est plus simple à écrire, il y a un gain d'efficacité à l'écriture du code, son maintien...
  • souvent une version récursive est plus gourmande en mémoire qu'une version itérative équivalente, et donc plus lente. Mais seulement avec un facteur multiplicatif près proche de 1.

⚠ Avec d'autres langages, il existe une possibilité : écrire une fonction récursive et laisser le compilateur la transformer en itérative ; le meilleur des deux mondes ! Ceci est impossible avec Python, par choix. Vous étudierez donc les fonctions récursives terminales en post-BAC, pas avant.