Pensez en Python

L'appel d'une fonction génère une valeur de retour. Habituellement, nous attribuons cette valeur à une variable, ou l'utilisons comme partie d'une expression.

e = math.exp(1.0)
hauteur = rayon * math.sin(radians)

Les fonctions que nous avons écrites jusqu'à présent sont vides, c'est-à-dire qu'elles ne renvoient aucune valeur ; plus précisément, leur valeur de retour est None.

Dans ce chapitre, nous allons (enfin) écrire des fonctions productives. Le premier exemple est aire, qui retourne la surface d'un cercle dont le rayon est donné :

def aire(rayon):
    a = math.pi * rayon**2
    return a

Nous avons rencontré l'instruction return précédemment, mais, dans une fonction productive, l'instruction return inclut une expression. Cette instruction signifie : « sortir immédiatement de cette fonction et utiliser l'expression qui suit le return comme valeur de retour ». L'expression peut être arbitrairement compliquée, donc nous aurions pu écrire cette fonction de façon plus concise :

def aire(rayon):
    return math.pi * rayon**2

D'un autre côté, les variables temporaires comme a peuvent rendre le débogage plus facile.

Parfois, il est utile d'avoir plusieurs instructions de retour, une dans chaque branche d'une instruction conditionnelle :

def valeur_absolue(x):
    if x < 0:
        return -x
    else:
        return x

Puisque ces instructions de retour sont dans une alternative, une seule d'entre elles est atteinte et exécutée.

Dès qu'une instruction de retour est exécutée, la fonction se termine sans exécuter aucune des lignes de code qui suivent. Le code qui apparaît après une instruction de retour ou tout autre endroit que le flux d'exécution ne peut jamais atteindre s'appelle du code mort.

Dans une fonction productive, il est souhaitable de faire en sorte que tous les chemins d'exécution possibles à travers le programme atteignent une instruction de retour. Par exemple :

def valeur_absolue(x):
    if x < 0:
        return -x
    if x > 0:
        return x

Cette fonction est incorrecte parce que s'il arrive que x soit égal à 0, aucune des deux conditions n'est vraie, et la fonction se termine sans atteindre d'instruction de retour. Si le flux d'exécution arrive à la fin d'une fonction, la valeur de retour par défaut est None, ce qui n'est pas la valeur absolue de 0.

>>> valeur_absolue(0)
None

Au fait, Python fournit une fonction interne appelée abs qui calcule des valeurs absolues.

À titre d'exercice, écrivez une fonction comparer qui prend deux valeurs, x et y, et retourne 1 si x> y, 0 si x == y, et -1 si x < y.

Si vous écrivez des fonctions plus volumineuses, il se peut que vous dépensiez plus de temps à déboguer.

Pour gérer le développement de programmes de plus en plus complexes, vous pourriez vouloir essayer un processus appelé développement incrémental. L'objectif de celui-ci est d'éviter de longues sessions de débogage et de test en ajoutant seulement une petite quantité de code à la fois.

À titre d'exemple, supposons que vous vouliez trouver la distance entre deux points spécifiés par leurs coordonnées (x1, y1) et (x2, y2). Le théorème de Pythagore nous dit que la distance est :

La première étape est de considérer à quoi devrait ressembler une fonction distance en Python. Autrement dit, quelles sont les données en entrée (paramètres) et quelle en la donnée en sortie (la valeur de retour) ?

Dans ce cas, les entrées sont les deux points, que vous pouvez représenter en utilisant quatre nombres. La valeur de retour est la distance représentée par une valeur en virgule flottante.

Immédiatement, vous pouvez écrire un début de fonction :

def distance(x1, y1, x2, y2):
    return 0.0

Évidemment, cette version ne calcule pas des distances, elle renvoie toujours zéro. Mais elle est syntaxiquement correcte et elle s'exécute sans erreur, ce qui signifie que vous pouvez la tester avant de la rendre plus complexe.

Pour tester la nouvelle fonction, appelez-la avec des exemples d'arguments :

>>> distance(1, 2, 4, 6)
0.0

J'ai choisi ces valeurs de sorte que la distance horizontale soit égale à 3 et la distance verticale soit 4 ; de cette façon, le résultat est , l'hypoténuse d'un triangle 3-4-5. Lorsque l'on teste une fonction, il est utile de connaître la bonne réponse attendue.

À ce stade, nous avons confirmé que la fonction est syntaxiquement correcte et nous pouvons commencer à ajouter du code au corps. Une prochaine étape raisonnable est de trouver les différences x₂ - x₁ et y₂ - y₁. La version suivante stocke ces valeurs dans des variables temporaires et les affiche :

def distance(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    print('dx est', dx)
    print('dy est', dy)
    return 0.0

Si la fonction est correcte, elle devrait afficher dx est 3 et dy est 4. Dans l'affirmative, nous savons que la fonction reçoit les bons arguments et effectue correctement le premier calcul. Sinon, il y a seulement quelques lignes à vérifier.

Ensuite, nous calculons la somme des carrés de dx et dy :

def distance(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    somme_carres = dx**2 + dy**2
    print('somme_carres est : ', somme_carres)
    return 0.0

Encore une fois, vous devez exécuter le programme à ce stade et vérifier la sortie (qui devrait être 25). Enfin, vous pouvez utiliser math.sqrt pour calculer et renvoyer le résultat :

Si cela fonctionne correctement, vous avez terminé. Sinon, vous voudrez peut-être afficher la valeur de resultat avant l'instruction de retour.

def distance(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    somme_carres = dx**2 + dy**2
    resultat = math.sqrt(somme_carres)
    return resultat

La version définitive de la fonction n'affiche rien quand elle est exécutée ; elle ne fait que renvoyer une valeur. Les instructions print que nous avons écrites sont utiles pour le débogage, mais une fois que votre fonction marche, vous devez les supprimer. Ce genre de code s'appelle parfois un échafaudage, car il est utile pour la construction du programme, mais ne fait pas partie du produit final.

Lorsque vous débutez, vous devriez ajouter seulement une ou deux lignes de code à la fois. Au fur et à mesure que vous accumulez de l'expérience, vous en arriverez sans doute à écrire et déboguer des fragments de code de plus en plus longs. En tout cas, le développement incrémental peut vous faire économiser beaucoup de temps de débogage.

Les aspects clés du processus sont :

1. Commencez avec un programme qui fonctionne et faites de petits changements progressifs. À tout moment, s'il y a une erreur, vous devriez deviner à peu près l'endroit où elle se trouve ;
2. Utilisez des variables pour stocker les valeurs intermédiaires, afin de pouvoir les afficher et vérifier leur contenu ;
3. Une fois que le programme fonctionne, vous voudrez peut-être supprimer certains éléments de l'échafaudage ou consolider plusieurs instructions dans des expressions composées, mais seulement si cela ne rend pas le programme difficile à lire.

À titre d'exercice, utilisez le développement incrémental pour écrire une fonction appelée hypotenuse qui retourne la longueur de l'hypoténuse d'un triangle rectangle à partir de la longueur des deux autres côtés passés en arguments. Enregistrez chaque étape du processus de développement au fur et à mesure.

Comme vous devriez vous en douter depuis un moment, vous pouvez appeler une fonction au sein d'une autre. À titre d'exemple, nous allons écrire une fonction qui prend en entrée deux points, le centre du cercle et un point sur le périmètre, et calcule l'aire du cercle.

Supposons que le point central est stocké dans les variables xc et yc, et les coordonnées du point sur le périmètre sont xp et yp. La première étape consiste à trouver le rayon du cercle, qui est la distance entre les deux points. Nous venons d'écrire une fonction, distance, qui fait exactement cela :

rayon = distance(xc, yc, xp, yp)

La prochaine étape est de trouver l'aire d'un cercle avec ce rayon ; nous pouvons écrire aussi :

resultat = aire(rayon)

En encapsulant ces étapes dans une fonction, nous obtenons :

def surface_cercle(xc, yc, xp, yp):
    rayon = distance(xc, yc, xp, yp)
    resultat = aire(rayon)
    return resultat

Les variables temporaires rayon et resultat sont utiles pour le développement et le débogage, mais une fois que le programme fonctionne, nous pouvons rendre la fonction plus concise en composant les appels de fonction :

def surface_cercle(xc, yc, xp, yp):
    return aire(distance(xc, yc, xp, yp))

Les fonctions peuvent retourner des valeurs booléennes, ce qui est souvent pratique pour cacher des tests compliqués dans des fonctions. Par exemple :

def divisible(x, y):
    if x % y == 0:
        return True
    else:
        return False

Il est courant de donner aux fonctions booléennes des noms qui ressemblent à des questions oui/non ; is_divisible retourne soit True, soit False pour indiquer si x est divisible par y.

Voici un exemple :

>>> is_divisible(6, 4)
False
>>> is_divisible(6, 3)
True

Le résultat de l'opérateur == est lui-même un booléen, donc nous pouvons écrire la fonction de manière plus concise en renvoyant ce booléen directement :

def divisible(x, y):
    return x % y == 0

Les fonctions booléennes sont souvent utilisées dans des instructions conditionnelles :

if divisible(x, y):
    print('x est divisible par y')

Il pourrait être tentant d'écrire quelque chose comme :

if divisible(x, y) == True:
    print('x est divisible par y')

Cela fonctionne, mais la comparaison supplémentaire est inutile : on a déjà un booléen, on peut l'utiliser directement dans la condition.

À titre d'exercice, écrivez une fonction compris_entre(x, y, z) qui retourne True si x ≤ y ≤ z et False sinon.

Nous avons couvert seulement un petit sous-ensemble de Python, mais vous pourriez être intéressés de savoir que ce sous-ensemble est un langage de programmation complet, ce qui signifie que tout ce qui peut être calculé peut être exprimé dans ce langage. Tout programme jamais écrit pourrait être réécrit en utilisant uniquement les fonctionnalités du langage que vous avez apprises jusqu'ici (en fait, vous auriez besoin de quelques commandes pour contrôler des périphériques comme la souris, les disques, etc., mais c'est tout).

Prouver cette affirmation est un exercice non trivial, accompli pour la première fois par Alan Turing, l'un des premiers chercheurs en informatique (certains diront qu'il était un mathématicien, mais beaucoup des premiers informaticiens ont fait leurs débuts comme mathématiciens). Par conséquent, cela est connu comme la thèse de Turing. Pour une discussion plus complète (et précise) sur la thèse de Turing, je recommande le livre de Michael Sipser, Introduction to the Theory of Calculation. (Le lecteur francophone pourra se faire une idée de la problématique sur la page de Wikipédia consacrée à ce sujet. NdT).

Pour vous donner une idée de ce que vous pouvez faire avec les outils que vous avez étudiés jusqu'ici, nous allons évaluer quelques fonctions mathématiques définies de manière récursive. Une définition récursive est semblable à une définition circulaire, en ce sens que la définition contient une référence à la chose en train d'être définie. Une définition véritablement circulaire n'est pas très utile :

Si vous lisiez cette définition dans le dictionnaire, vous seriez sans doute bien ennuyé. D'un autre côté, si vous regardiez la définition de la fonction factorielle, notée par le symbole « ! », vous obtiendriez sans doute quelque chose comme ceci :

Cette définition indique que la factorielle de 0 est 1, et la factorielle de toute autre valeur n est n multiplié par la factorielle de n - 1.

Donc 3! est 3 fois 2!, qui est 2 fois 1!, qui est 1 fois 0!. En mettant le tout ensemble, 3! est égal à 3 fois 2 fois 1 fois 1, ce qui donne 6.

Si vous pouvez écrire une définition récursive de quelque chose, vous pouvez écrire un programme Python pour l'évaluer. La première étape consiste à décider ce que les paramètres devraient être. Dans ce cas, il devrait être clair que factorielle prend un entier naturel :

def factorielle(n):

S'il se trouve que l'argument est 0, tout ce que nous avons à faire est de renvoyer 1 :

def factorielle(n):
    if n == 0:
        return 1

Sinon, et là, cela devient intéressant, nous devons faire un appel récursif pour trouver la factorielle de n - 1 et la multiplier par n :

def factorielle(n):
    if n == 0:
        return 1
    else:
        recurse = factorielle(n - 1)
        resultat = n * recurse
        return result

Le flux d'exécution de ce programme est similaire à celui de compte_a_rebours dans la section 5.8Récursion. Si nous appelons factorielle avec la valeur 3 :

Puisque 3 est différent de 0, nous prenons la deuxième branche et calculons la factorielle de n - 1...

• Puisque 2 est différent de 0, nous prenons la deuxième branche et calculons la factorielle de n - 1...

  • Puisque 1 est différent de 0, nous prenons la deuxième branche et calculons la factorielle de n - 1...

    • Puisque 0 est égal à 0, nous prenons la première branche et retournons 1, sans faire d'appel récursif supplémentaire.
  • La valeur de retour, 1, est multipliée par n, qui vaut 1, et le résultat est retourné.
• La valeur de retour, 1, est multipliée par n, qui vaut 2, et le résultat est retourné.

La valeur de retour (2) est multipliée par n, qui est 3, et le résultat, 6, devient la valeur de retour de l'appel de fonction qui a démarré l'ensemble du processus.

La figure 6.1 montre à quoi ressemble le diagramme de pile pour cette séquence d'appels de fonction.

Dans la dernière structure de pile, les variables locales recurse et resultat n'existent pas, parce que la branche qui les crée n'est pas exécutée.

Suivre le flux d'exécution est une façon de lire les programmes, mais on peut rapidement se trouver dépassé. Une autre possibilité est ce que j'appelle « l'acte de foi ». Quand vous arrivez à un appel de fonction, au lieu de suivre le flux d'exécution, vous supposez que la fonction s'exécute correctement et renvoie le bon résultat.

En fait, vous pratiquez déjà cet acte de foi lorsque vous utilisez les fonctions internes. Quand vous appelez math.cos ou math.exp, vous n'examinez pas le corps de ces fonctions. Vous ne faites que supposer qu'elles fonctionnent parce que les gens qui ont écrit les fonctions internes étaient de bons programmeurs.

Il en va de même lorsque vous appelez une de vos propres fonctions. Par exemple, dans la section 6.4Fonctions booléennes, nous avons écrit une fonction appelée divisible qui détermine si un nombre est divisible par un autre. Une fois que nous nous sommes convaincus que cette fonction est correcte - en examinant son code et en la testant - , nous pouvons utiliser la fonction sans regarder à nouveau le corps.

Même chose en ce qui concerne les programmes récursifs. Lorsque vous arrivez à l'appel récursif, au lieu de suivre le flux d'exécution, vous devez supposer que les appels récursifs fonctionnent (renvoient le résultat correct), puis vous poser la question, « En supposant que je puisse trouver la factorielle de n - 1, puis-je calculer la factorielle de n ? » Il est clair que vous pouvez, en multipliant la factorielle de n - 1 par n.

Bien sûr, il est un peu étrange de penser que la fonction s'exécute correctement alors que vous ne l'avez pas fini de l'écrire, mais c'est pourquoi on appelle cela un acte de foi !

Après factorielle, l'exemple le plus courant d'une fonction mathématique définie de manière récursive est fibonacci, qui a la définition suivante (voir https://fr.wikipedia.org/wiki/Suite_de_Fibonacci et http://en.wikipedia.org/wiki/Fibonacci_number) :

Adapté en Python, cela ressemblerait à ceci :

def fibonacci (n):
    if n == 0:
        return 0
    elif  n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Si vous essayez de suivre le flux d'exécution dans ce cas-ci, même pour des valeurs assez petites de n, votre tête risque d'exploser. Mais, conformément à l'acte de foi, si vous supposez que les deux appels récursifs fonctionnent correctement, alors il est clair que vous obtenez le bon résultat en les ajoutant.

Que se passe-t-il si nous appelons factorielle en lui donnant 1,5 comme argument ?

>>> factorielle(1.5)
RuntimeError: Maximum recursion depth exceeded

Cela ressemble à une récursion infinie. Comment est-ce possible ? La fonction a un cas de base, pour le cas où n == 0. Mais si n n'est pas un nombre entier, nous risquons de ne pas atteindre le cas de base et d'effectuer des récursions à jamais.

Dans le premier appel récursif, la valeur de n est de 0.5. Dans l'appel suivant, elle est de - 0.5. À partir de là, elle devient de plus en plus petite (plus négative), mais elle ne sera jamais 0.

Nous avons deux choix. Nous pouvons essayer de généraliser la fonction factorielle pour travailler avec des nombres à virgule flottante, ou nous pouvons modifier factorielle pour faire en sorte qu'elle vérifie le type de son argument. La première option est appelée la fonction gamma et elle est un peu au-delà du périmètre de ce livre. Nous allons donc choisir la seconde.

Nous pouvons utiliser la fonction interne isinstance pour vérifier le type de l'argument. Tant que nous y sommes, nous pouvons également nous assurer que l'argument est positif :

def factorielle (n):
    if not isinstance(n, int):
        print('Factorielle est définie uniquement pour des entiers.')
        return None
    elif n < 0:
        print("Factorielle n'est pas définie pour des entiers négatifs.")
        return None
    elif n == 0:
        return 1
    else:
        return n * factorielle(n-1)

Le premier cas de base gère les valeurs qui ne sont pas des entiers ; le deuxième gère les entiers négatifs. Dans les deux cas, le programme affiche un message d'erreur et retourne None pour indiquer que quelque chose s'est mal passé :

>>> factorielle('fred')
Factorielle est définie uniquement pour des entiers.
None
>>> factorielle(-2)
Factorielle n'est pas définie pour des entiers négatifs.
None

Si nous passons les deux contrôles, nous savons que n est entier et qu'il est positif ou nul, donc nous pouvons prouver que la récursion ne sera pas infinie.

Ce programme illustre un mécanisme que l'on appelle parfois une garde. Les deux premières conditionnelles agissent comme des gardes, en protégeant le code qui suit des valeurs qui pourraient causer une erreur. Les gardes permettent de prouver l'exactitude du code.

Dans la section 11.4Recherche inversée, nous verrons une autre option, plus souple que l'impression d'un message d'erreur : signaler une exception.

Découper un vaste programme en fonctions plus petites crée des points de contrôle naturels pour le débogage. Si une fonction ne fonctionne pas, il y a trois possibilités à envisager :

• il y a un problème avec les arguments que la fonction reçoit ; une condition préalable est enfreinte ;
• il y a un problème avec la fonction ; une postcondition est enfreinte ;
• il y a un problème avec la valeur de retour ou la façon dont elle est utilisée.

Pour exclure la première possibilité, vous pouvez ajouter une instruction d'impression au début de la fonction et afficher la valeur des paramètres (et peut-être leur type). Ou vous pouvez écrire du code qui vérifie explicitement les conditions préalables.

Si les paramètres semblent bons, ajoutez une instruction d'impression avant chaque déclaration de retour et affichez la valeur de retour. Si possible, vérifiez le résultat à la main. Envisagez d'appeler la fonction avec des valeurs qui donnent un résultat facile à vérifier (comme dans la section 6.2Développement incrémental).

Si la fonction semble marcher, regardez l'appel de fonction pour vous assurer que la valeur de retour est utilisée correctement (ou qu'elle est utilisée tout court !).

L'ajout d'instructions d'impression au début et à la fin d'une fonction peut aider à rendre le flux d'exécution plus visible. Par exemple, voici une version de factorielle avec des instructions d'impression :

def factorielle(n):
    espace = ' ' * (4 * n)
    print(espace, 'factorielle', n)
    if n == 0:
        print(espace, 'retourner 1')
        return 1
    else:
        recurse = factorielle(n - 1)
        resultat = n * recurse
        print(espace, 'retourner', resultat)
        return resultat

espace est une chaîne de caractères espace qui contrôle l'indentation de la sortie. Voici le résultat de factorielle(4) :

                 factorielle 4
             factorielle 3
         factorielle 2
     factorielle 1
 factorielle 0
 retourner 1
     retourner 1
         retourner 2
             retourner 6
                 retourner 24

Si le déroulement de l'exécution n'est pas clair pour vous, ce genre de sortie peut être utile. Il faut un certain temps pour développer un échafaudage efficace, mais un peu d'échafaudage peut économiser beaucoup de débogage.

• variable temporaire : une variable utilisée pour stocker une valeur intermédiaire dans un calcul complexe.
• code mort : partie d'un programme qui ne peut jamais être exécutée, souvent parce qu'elle apparaît après une instruction return.
• développement incrémental : un système de développement d'un programme, qui vise à éviter du débogage en ajoutant et testant seulement une petite quantité de code à la fois.
• échafaudage : code qui est utilisé pendant le développement du programme, mais ne fait pas partie de la version finale.
• garde : un mécanisme de programmation qui utilise une instruction conditionnelle pour vérifier et gérer les circonstances qui pourraient causer une erreur.

Exercice 1

Dessinez un schéma de pile pour le programme suivant. Qu'affiche le programme ?

def b(z):
    prod = a(z, z)
    print(z, prod)
    return prod

def a(x, y):
    x = x + 1
    return x * y

def c(x, y, z):
    total = x + y + z
    square = b(total)**2
    return square

x = 1
y = x + 1
print(c(x, y+3, x+y))

Exercice 2

La fonction d'Ackermann, A(m, n), est définie comme suit :

Voir https://fr.wikipedia.org/wiki/Fonction_d%27Ackermann . Écrivez une fonction nommée ack qui calcule la fonction d'Ackermann. Utilisez votre fonction pour évaluer ack(3, 4) , qui devrait être 125. Que se passe-t-il dans le cas des valeurs plus grandes de m et n  ?

Solution : ackermann.py.

Exercice 3

Un palindrome est un mot que l'on peut lire indifféremment de gauche à droite ou de droite à gauche, comme « kayak » et « ressasser ». De façon récursive, un mot est un palindrome si sa première et sa dernière lettre sont identiques et le reste des lettres au milieu du mot est un palindrome.

Les fonctions suivantes prennent comme argument une chaîne de caractères et retournent respectivement la première lettre, la dernière et le milieu du mot (word, en anglais) :

def first(word):
    return word[0]

def last(word):
    return word[-1]

def middle(word):
    return word[1:-1]

Nous verrons leur fonctionnement dans le chapitre 8Chaînes de caractères .

1. Tapez ces fonctions dans un fichier nommé palindrome.py et testez-les. Qu'advient-il si vous appelez middle avec une chaîne ayant deux lettres ? Mais dans le cas d'une chaîne d'une lettre ? Qu'en est-il de la chaîne vide, qui s'écrit ' ' et ne contient aucune lettre ?
2. Écrivez une fonction appelée is_palindrome qui prend un argument chaîne de caractères et retourne True si celle-ci est un palindrome et False sinon. Rappelez-vous que vous pouvez utiliser la fonction interne len pour déterminer la longueur d'une chaîne.

Solution :palindrome_soln.py.

Exercice 4

Un nombre quelconque, a, est une puissance de b s'il est divisible par b et a / b est une puissance de b. Écrivez une fonction appelée is_power qui prend les paramètres a et b et retourne True si a est une puissance de b. Remarque : vous devrez penser au cas de base.

Exercice 5

Le plus grand diviseur commun (PGDC) de a et b est le plus grand nombre qui divise les deux sans aucun reste.

Une manière de trouver le PGDC de deux nombres est basée sur l'observation que si r est le reste de la division de a par b, alors pgdc(a, b) = pgdc(b, r). Comme cas de base, nous pouvons utiliser pgdc(a, 0) = a.

Écrivez une fonction appelée pgdc qui prend les paramètres a et b et retourne leur plus grand diviseur commun.

Référence : cet exercice est basé sur un exemple du livre « Structure et interprétation des programmes informatiques » (InterÉd. 1989) de Abelson et Sussman.