Retour sur les fonctions

Nous savons déclarer une fonction avec des paramètres simples, et leur associer des arguments lors de l’appel, qu’ils soient positionnels ou nommés.

>>> def log(message, component, level):
...     print(f'[{level}] {component}: {message}')
... 
>>> log('Une erreur est survenue', 'system', 'error')
[error] system: Une erreur est survenue
>>> log('Une erreur est survenue', 'system', level='error')
[error] system: Une erreur est survenue

Nous obtenons un message d’erreur si nous omettons un des arguments.

>>> log('Une erreur est survenue', 'system')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: log() missing 1 required positional argument: 'level'

Pourtant nous avons vu qu’il existait dans la bilbiothèque standard des fonctions avec des arguments optionnels, comment font-elles ? Cela se passe au moment de la définition des paramètres de la fonction, ou une valeur par défaut est donnée à certains paramètres. Les arguments optionnels correspondent simplement aux paramètres ayant une valeur par défaut.

Pour définir une valeur par défaut à un paramètre, il suffit d’écrire parametre=valeur plutôt que parametre dans la liste des paramètres de la fonction. Voici ainsi une version plus évoluée de notre fonction log, s’appuyant sur des valeurs par défaut.

>>> def log(message, component=None, level='info'):
...     if component is None:
...         print(f'[{level}] {message}')
...     else:
...         print(f'[{level}] {component}: {message}')
...
>>> log('Une erreur est survenue', 'system', 'error')
[error] system: Une erreur est survenue
>>> log("Message d'information")
[info] Message d'information
>>> log('Fonction dépréciée', level='warning')
[warning] Fonction dépréciée

Paramètres par défaut mutables

C’est aussi simple que cela… ou presque ! Il y a une chose à laquelle il faut faire attention, comme toujours, ce sont les types mutables.
Eh oui, les valeurs par défaut sont définies une seule fois pour toutes, quand la fonction elle-même est définie. C’est-à-dire que ces valeurs seront partagées entre tous les appels à la fonction.

Pour les valeurs immutables, pas de problème, il n’y a pas de risque d’effets de bord. Mais pour les mutables, faites bien attention à ce que vous faites, on arrive rapidement à des situations problématiques.

>>> def get_monster(name, attacks=[]):
...     return {'name': name, 'attacks': attacks}
... 
>>> pythachu = get_monster('Pythachu')
>>> pythachu['attacks'].append('tonnerre')
>>> pythachu
{'name': 'Pythachu', 'attacks': ['tonnerre']}
>>> pythard = get_monster('Pythard')
>>> pythard
{'name': 'Pythard', 'attacks': ['tonnerre']}

Et oui, la même liste d’attaque a été utilisée et donc partagée entre nos deux dictionnaires, d’où le bug. C’est pourquoi il est généralement conseillé d’éviter les mutables comme valeurs par défaut de paramètres.

Pour cela, on utilisera une valeur comme None (appellée sentinelle) qui indiquera l’absence de valeur et permettra donc d’instancier un objet (ici une liste) dans le corps de la fonction, évitant le problème de l’instance partagée.

>>> def get_monster(name, attacks=None):
...     if attacks is None:
...         attacks = []
...     return {'name': name, 'attacks': attacks}
... 
>>> pythachu = get_monster('Pythachu')
>>> pythachu['attacks'].append('tonnerre')
>>> pythachu
{'name': 'Pythachu', 'attacks': ['tonnerre']}
>>> pythard = get_monster('Pythard')
>>> pythard
{'name': 'Pythard', 'attacks': []}

Je dis « généralement » car il y a des cas où c’est le comportement voulu, cela permet de mettre en place facilement un mécanisme de cache¹ sur une fonction par exemple.

>>> def compute(x, cache={}):
...     if x in cache:
...         return cache[x]
...     print('Calcul complexe...')
...     ret = x**3 - x**2
...     cache[x] = ret
...     return ret
... 
>>> compute(2)
Calcul complexe...
4
>>> compute(3)
Calcul complexe...
18
>>> compute(2) # Réutilisation du cache
4
>>> compute(5)
Calcul complexe...
100

Ordre de placement des paramètres

Nous l’avions vu, lors d’un appel de fonction les arguments positionnels doivent toujours être placés avant les arguments nommés. C’est ce qui permet à Python de faire correctement la correspondance entre arguments et paramètres.

>>> log(level='warning', 'Avertissement')
  File "<stdin>", line 1
SyntaxError: positional argument follows keyword argument

Une règle similaire existe pour les paramètres : ceux qui prennent une valeur par défaut doivent se placer après les autres. Cela est logique puisqu’ils sont optionnels, et qu’on ne pourrait pas savoir dans le cas contraire à quel paramètre est censé correspondre un argument.

>>> def log(component=None, level='info', message):
...     pass
... 
  File "<stdin>", line 1
SyntaxError: non-default argument follows default argument

Vous pensiez avoir tout vu sur les arguments ? Que nenni ! Certaines fonctions que nous utilisons couramment exploitent encore des fonctionnalités inconnues.

Si je vous demandais par exemple de recoder la fonction print, comment procéderiez-vous ? Pour rappel, la fonction permet de recevoir un nombre variable d’arguments.

>>> print()

>>> print(1)
1
>>> print(1, 2, 3)
1 2 3

On pourrait essayer de placer plusieurs paramètres optionnels à la suite mais on ne couvrirait jamais tous les cas : si l’on créait une fonction avec 10 paramètres optionnels il ne serait pas possible de l’appeler avec 11 arguments.

Il doit donc y avoir autre chose, une manière de gérer un nombre variable d’arguments : les arguments variadiques ! L’idée derrière ce nom est simplement de récupérer les arguments positionnels sous forme d’une liste (ou plutôt d’un tuple).
Et cela se fait avec une syntaxe plutôt simple en Python, il suffit de placer *args dans la liste des paramètres de la fonction. On obtiendra ainsi un tuple args contenant ces arguments.

>>> def print_args(*args):
...     print(args)
... 
>>> print_args()
()
>>> print_args(1)
(1,)
>>> print_args(1, 2, 3)
(1, 2, 3)

args est ici un nom complètement arbitraire (mais très couramment utilisé) pour nommer cette liste, et n’importe quel autre nom fonctionnerait tout aussi bien. C’est le * placé avant qui a pour effet de récupérer les arguments et non le nom donné au paramètre.

Avec *args, tous les arguments sont ainsi optionnels. Mais il est aussi possible de préciser d’autres paramètres avant *args, qui ne récupérera alors que le reste des arguments : cela permet alors de conserver des arguments obligatoires.

>>> def my_sum(first, *args):
...     for n in args:
...         first += n
...     return first
... 
>>> my_sum(1)
1
>>> my_sum(1, 2, 3, 4, 5)
15
>>> my_sum()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: my_sum() missing 1 required positional argument: 'first'

Si vous testez un peu, vous remarquerez que cette syntaxe est valide pour les arguments positionnels mais pas les arguments nommés.

>>> print_args(foo='bar')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: print_args() got an unexpected keyword argument 'foo'

En effet, comment un tuple d’arguments pourrait représenter nos arguments nommés ?
Mais il existe une autre syntaxe pour récupérer les arguments nommés, sous forme d’un dictionnaire cette fois : **kwargs. kwargs pour keyword arguments (arguments nommés) car il ne pourra récupérer que les arguments qui sont explicitement nommés. Là encore le nom du paramètre n’est qu’une convention.

>>> def print_args(*args, **kwargs):
...     print(args, kwargs)
... 
>>> print_args()
() {}
>>> print_args(3, 5, foo='bar', toto='tata')
(3, 5) {'foo': 'bar', 'toto': 'tata'}

Le paramètre spécial **kwargs ne peut se placer que tout à la fin de la liste des paramètres puisqu’il récupère les arguments qui n’ont pas été attrapés par les paramètres précédents. *args quant à lui peut se placer à peu près où vous le souhaitez (avant **kwargs) mais souvenez-vous qu’il attrape tous les arguments positionnels, donc les paramètres situés après ne pourront récupérer que des arguments nommés.

>>> def print_args(foo, *args, bar, **kwargs):
...     print(foo, args, bar, kwargs)
...
>>> print_args(1, 2, 3, bar=4, baz=5)
1 (2, 3) 4 {'baz': 5}

Dans cet exemple, il n’est pas possible de fournir un argument positionnel au paramètre bar. bar est ce qu’on appelle un paramètre keyword-only (nommé uniquement).

Opérateur splat

L’opérateur * utilisé dans la liste des paramètres est appelé splat, et ce n’est pas sa seule utilisation.

Il permet en effet aussi de réaliser l’opération inverse, celle de transmettre à une fonction les éléments d’une liste (ou autre itérable) comme arguments positionnels différents.

>>> def addition(a, b):
...     return a + b
... 
>>> addition(*[1, 2])
3
>>> args = [1, 2]
>>> addition(*args)
3

addition(*[1, 2]) est ainsi strictement équivalent à addition(1, 2).

Et on voit que le splat du côté de l’appel n’est pas lié au splat dans la définition des paramètres puisque notre fonction n’accepte pas d’arguments variadiques ici. Mais les deux sont bien sûr compatibles.

>>> print_args(*[1, 2, 3])
(1, 2, 3) {}

Contrairement aux paramètres, rien ne nous empêche ici d’utiliser plusieurs splats pour envoyer des arguments de plusieurs listes, ni d’utiliser des arguments « normaux » en plus de nos listes.

>>> print_args(1, 2, *[3, 4, 5], 6)
(1, 2, 3, 4, 5, 6) {}
>>> print_args(*[1, 2, 3], 4, *[5, 6])
(1, 2, 3, 4, 5, 6) {}

De manière équivalente, ** est l’opérateur double-splat et peut s’utiliser lors d’un appel pour transmettre le contenu d’un dictionnaire comme arguments nommés. Il est alors nécessaire que les clés du dictionnaire soient des chaînes de caractères (un nom de paramètre ne peut pas être autre chose qu’une chaîne).

>>> print_args(**{'foo': 0, 'bar': 'baz'})
() {'foo': 0, 'bar': 'baz'}

Je vous ai présenté plus tôt la fonction help qui permet d’obtenir des informations sur un module ou une fonction. Mais pour avoir accès à ces informations il faut que celles-ci aient été renseignées, que les fonctions aient été documentées.

C’est le cas dans la bibliothèque standard et c’est pourquoi nous obtenons des pages d’aide si complètes. Mais qu’en est-il de nos propres fonctions ?

Prenons cette fonction operation capable d’appliquer différentes opérations arithmétiques à deux valeurs.

def operation(op, a, b):
    if op == '+':
        return a + b
    elif op == '-':
        return a - b
    elif op == '*':
        return a * b
    elif op == '/':
        return a / b
    print('error')
    return -1

La gestion d’erreurs est nulle mais ce n’est pas le sujet ici, nous y reviendrons plus tard.
Voyons pour le moment à quoi ressemble la page d’aide de notre fonction.

>>> help(operation)
Help on function operation in module __main__:

operation(op, a, b)

C’est… succinct. D’un côté, on n’a rien renseigné d’autre à notre fonction, et il serait difficile à Python de nous donner plus d’informations.

Docstring

Une première étape vers la documentation est de rédiger une docstring dans notre fonction. Une docstring c’est simplement une chaîne de caractères placée au début de notre fonction, sans assignation ni rien.

def operation(op, a, b):
    "Renvoie le résultat de l'opération a (op) b"
    ...

Dans le déroulement de notre fonction ça ne change rien puisqu’une telle chaîne de caractères n’a aucun effet. Mais Python la détecte et la rend accessible comme documentation de notre fonction.

>>> help(operation)
Help on function operation in module __main__:

operation(op, a, b)
    Renvoie le résultat de l'opération a (op) b

Mais la documentation ne se résume généralement pas en une ligne. Aussi, on trouvera souvent une chaîne multi-lignes délimitée par des triple-guillemets pour documenter notre fonction.

def operation(op, a, b):
    """
    Renvoie le résultat de l'opération a (op) b
    
    Avec op l'un des opérateurs suivants :
    +: addition
    -: soustraction
    *: multiplication
    /: division
    """
    ...

Ne vous inquiétez pas pour les retours à la ligne introduits au début et à la fin de la chaîne, ils disparaissent dans la documentation.

>>> help(operation)
Help on function operation in module __main__:

operation(op, a, b)
    Renvoie le résultat de l'opération a (op) b
    
    Avec op l'un des opérateurs suivants :
    +: addition
    -: soustraction
    *: multiplication
    /: division

Comment documenter ?

Dans notre documentation, on ne va pas définir en détails ce que fait notre fonction, expliquer toutes les conditions qui y sont faites, ça n’aurait pas trop d’intérêt. Non, le but d’une documentation est de décrire l’usage : comment utiliser notre fonction et à quoi s’attendre en retour.

Si notre fonction a des comportements particuliers (erreurs qu’elle gère ou pas, astuces d’optimisation, etc.), il est bon aussi de les indiquer dans la documentation.

Pour notre fonction operation, la documentation devrait indiquer que notre fonction réalise des opérations arithmétiques de 4 types (addition, soustraction, multiplication et division flottante) et renvoie le résultat de l’opération, l’opération à effectuer et les deux opérandes étant récupérés depuis les paramètres.
Il serait ajouté que la fonction affiche un message d’erreur en cas d’opération inconnue (en renvoyant -1), et qu’elle ne traite pas l’erreur de division par zéro.

Annotations de types

La docstring n’est pas l’unique manière de documenter une fonction, d’autres informations peuvent être apportées par les annotations de types. Comme leur nom l’indique, ces annotations servent à décrire les types des paramètres de la fonction.

Notre fonction peut s’annoter simplement : le premier paramètre est une chaîne de caractère, et les deux suivants sont des nombres, que l’on va pour le moment considérer comme des int. Pour annoter un paramètre, on le fait suivre d’un : et du type que l’on veut préciser.

def operation(op: str, a: int, b: int):
    ...

Ces informations sont ajoutées à la signature de la fonction dans la documentation fournie par help.

>>> help(operation)
Help on function operation in module __main__:

operation(op: str, a: int, b: int)
...

Il est aussi possible de préciser une annotation sur la fonction en elle-même pour indiquer le type de la valeur de retour. Pour cela, on utilise un -> derrière la liste des paramètres, suivi du type de retour.

def operation(op: str, a: int, b: int) -> int:
    ...

On le constate d’ailleurs si l’on appelle notre fonction avec des nombres flottants.

>>> operation('+', 1.2, 3.4)
4.6

Module typing

Cela nous pose tout de même un problème : notre fonction est documentée pour être utilisée avec des int, mais on aimerait pouvoir l’appeler avec des float. On pourrait la documenter avec des float mais se poserait alors le problème inverse.

Heureusement, il existe un module Python pour travailler et modeler ces annotations de types, le module typing. Celui-ci contient des outils qui vont nous être utiles pour préciser des cas plus complexes d’utilisation des types, comme ici avec le choix entre deux types.

Pour ce problème il existe donc typing.Union, un objet particulier qui comme son nom l’indique permet de créer des unions (au sens mathématique) de types. Il s’utilise à l’aide de crochets à l’intérieur desquels sont précisés les types autorisés.
Dans notre cas on aurait typing.Union[int, float].

Cet objet définit une forme spéciale de typage, et s’utilise donc directement en tant qu’annotation. Un paramètre annoté ainsi sera considéré comme pouvant être de n’importe lequel des types précisés.

import typing

def operation(op: str, a: typing.Union[int, float], b: typing.Union[int, float]) -> typing.Union[int, float]:
    ...

Ce type n’a pas pour but d’être instancié, et vous obtiendrez d’ailleurs une erreur si vous essayez de le faire. Il n’est utile que pour renseigner des annotations.

On notera qu’il est possible de créer un alias à notre type particulier, de façon à le renseigner plus facilement, tout simplement en l’assignant à une variable.

Number = typing.Union[int, float]

def operation(op: str, a: Number, b: Number) -> Number:
    ...

D’autres problèmes peuvent se poser lorsque l’on cherche à documenter les types d’une fonction. Par exemple prenons la fonction my_sum suivante, équivalente à la fonction sum de la bibliothèque standard, pour calculer une somme de nombres.

def my_sum(values, start=0):
    "Calcule et renvoie les somme des éléments de `values`"
    for value in values:
        start += value
    return start

Comment l’annoter de façon à préciser que l’on attend une liste de nombres comme premier argument ? On ne peut pas simplement utiliser list qui serait bien trop générique, autorisant des éléments d’autres types et mêmes des listes disparates (composées d’éléments de types différents).

typing vient à la rescousse en proposant un typing.List que l’on spécialise avec le type voulu, ici le type spécial Number défini plus haut.

def my_sum(values: typing.List[Number], start : typing.Number = 0) -> typing.Number:
    ...

On pourrait aussi utiliser typing.Iterable[Number] qui aurait l’intérêt d’autoriser tout type d’itérable (tuple, range, etc.) et non uniquement les listes.

Le module typing comprend de nombreuses choses, certaines dépassant le cadre de ce cours, et je ne vais donc pas m’appesentir sur sa présentation. Pour terminer, sachez simplement qu’il existe un type spécial typing.Any, pour préciser qu’un paramètre peut accepter une valeur de n’importe quel type.

def print(value: typing.Any):
    ...

Les décorateurs sont faits pour décorer. Enfin pas exactement, il faut comprendre le terme comme « envelopper ». Un décorateur, c’est un objet que l’on va appliquer à une fonction pour en changer le comportement.

Le décorateur est indépendant et extérieur à la fonction, il se contente de l’envelopper.
Lors des appels à notre fonction, c’est le décorateur qui prendra le pas et choisira les opérations à effectuer. Il pourra choisir d’appeler notre fonction ou non, d’exécuter des opérations avant ou après, etc.

Il s’agit de l’application directe du patron de conception décorateur.

Par exemple, plus tôt dans ce chapitre nous avons vu un mécanisme de cache (mémoïsation) appliqué à une fonction, à l’aide de la valeur par défaut d’un paramètre. Ce mécanisme aurait pu être implémenté à l’aide d’un décorateur, celui-ci décidant si l’appel à la fonction est nécessaire ou non, en fonction de ce qu’il a dans son cache, puis il se chargerait d’y enregistrer les résultats reçus.

La syntaxe pour appliquer un décorateur à une fonction est très simple, il suffit de précéder la définition de notre fonction par une ligne composée d’un @ et du nom du décorateur.

@decorator
def function(a, b):
    ...

En pratique, on notera que ce code est équivalent au suivant, l’application à l’aide de l'@ n’étant que du sucre syntaxique apporté par Python.

def function(a, b):
    ...

function = decorator(function)

Le mécanisme de cache dont je parlais est fourni par le décorateur lru_cache du module functools. Appliqué à une fonction, il permettra donc de garder en mémoire les résultats de la fonction et éviter de réexécuter des calculs coûteux.

from functools import lru_cache

@lru_cache
def addition(a, b):
    print(f'Calcul de {a} + {b}...')
    return a + b

On le voit à l’utilisation, la fonction n’est appelée que si son résultat n’est pas déjà connu.

>>> addition(3, 5)
Calcul de 3 + 5...
8
>>> addition(1, 2)
Calcul de 1 + 2...
3
>>> addition(3, 5)
8

Un tel mécanisme par décorateur a l’intérêt de ne rien changer au code de la fonction, qui reste le même que si le décorateur n’était pas là.

Décorateur paramétré

Mais que signifie ce lru dans lru_cache ? Il s’agit du sigle Least Recently Used (Utilisés le Plus Récemment en français) explicitant le comportement du cache.

En effet, votre ordinateur a une mémoire limitée et le cache cherche donc à minimiser son empreinte. Pour cela, il ne conservera pas tous les résultats en mémoire mais seulement ceux qu’il juge prioritaires. C’est là qu’intervient le mécanisme LRU qui signifie simplement que les résultats prioritaires sont ceux utilisés le plus récemment.
Cela signifie aussi que les résultats les plus anciens finiront par disparaître du cache lorsque celui-ci aura été rempli par d’autres valeurs.

La taille maximale par défaut du cache est de 128 résultats, mais il est possible d’en changer en paramétrant le décorateur.
Comme une fonction, un décorateur peut-être suivi de parenthèses contenant des arguments pour le paramétrer et donc influer sur son comportement.

@decorator('foo', 5)
def function(a, b):
    ...

Ici, la taille du cache est un paramètre du décorateur. Nous allons d’ailleurs voir le mécanisme LRU en action en réduisant la taille allouée à ce cache, disons à 3.

@lru_cache(3)
def addition(a, b):
    print(f'Calcul de {a} + {b}...')
    return a + b

Et maintenant, regardez bien ce qu’il se passe quand la taille maximale est atteinte.

>>> addition(3, 5)
Calcul de 3 + 5...
8
>>> addition(1, 2)
Calcul de 1 + 2...
3
>>> addition(4, 7)
Calcul de 4 + 7...
11
>>> addition(3, 5) # la valeur est toujours en cache
8
>>> addition(9, 6)
Calcul de 9 + 6...
15
>>> addition(1, 2) # la valeur est sortie du cache
Calcul de 1 + 2...
3

Notre cache est limité à 3 résultats, pour enregistrer 9 + 6 il doit donc faire de la place. Le résultat le plus anciennement utilisé, ici 1 + 2, est donc supprimé.

Attention, je dis bien plus anciennement utilisé et non calculé. Car le résultat le plus anciennement calculé est 3 + 5, mais on l’a redemandé par la suite à la fonction, signifiant au cache qu’il était à nouveau utilisé. Le résultat supprimé est celui auquel on a accédé le moins récemment.

Il est aussi parfaitement possible de se passer de ce mécanisme LRU et donc de conserver tous les résultats sans limite de taille (autre que celle de l’ordinateur), en spécifiant None comme taille maximale au décorateur.

@lru_cache(None)
def addition(a, b):
    print(f'Calcul de {a} + {b}...')
    return a + b

from functools import cache

@cache
def addition(a, b):
    print(f'Calcul de {a} + {b}...')
    return a + b

Les conditions peuvent être des expressions, les boucles (for) peuvent être des expressions, les définitions de fonction peuvent aussi être des expressions.

Je dis bien les définitions car les fonctions en elles-mêmes, nous l’avons vu précédemment, sont déjà des valeurs et donc des expressions à part entière.

>>> def add_one(n):
...     return n + 1
... 
>>> add_one
<function add_one at 0x7f662ecf61f0>
>>> x = add_one
>>> x(5)
6

Leur définition, c’est le bloc def qui définit leur nom, leurs paramètres et leur code ; lui ne peut pas être assigné à une variable ou passé en argument.

La solution se trouve du côté des fonctions lambdas (ou « fonctions anonymes ») introduites par le mot-clé lambda. Ce mot-clé, suivi d’un : et d’une expression permet de définir une fonction sans nom, l’expression étant le code de la fonction.
Une fonction lambda ne peut alors être composée que d’une unique expression.

>>> lambda: 42
<function <lambda> at 0x7f616ffe93a0>

Il s’agit d’une fonction à part entière, et si nous l’appelons nous obtenons bien 42 comme réponse.

>>> (lambda: 42)()
42

La lambda est une expression et peut donc être assignée à une variable.

>>> get_42 = lambda: 42
>>> get_42
<function <lambda> at 0x7f616ffe9430>
>>> get_42()
42

Tout comme les fonctions, les lambdas peuvent recevoir des paramètres en tous genres, il suffit pour cela de préciser la liste des paramètres avant le signe :.

>>> addition = lambda a, b: a + b
>>> addition(3, 5)
8

Mais l’intérêt principal des fonctions comme expressions réside dans le fait de pouvoir être passées comme arguments à d’autres fonctions. Souvenez-vous par exemple de la fonction sorted et de son paramètre key recevant une fonction.
Avec une lambda, il n’est pas nécessaire de définir une fonction au préalable : on peut directement passer l’expression de tri sous forme de lambda à la fonction.

Voici par exemple un tri de mots ne tenant pas compte de la casse (différence entre lettres minuscules et capitales), en s’appuyant sur la conversion en minuscules des chaînes.

>>> words = ['poire', 'Ananas', 'banane', 'abricot', 'FRAISE']
>>> sorted(words, key=lambda w: w.lower())
['abricot', 'Ananas', 'banane', 'FRAISE', 'poire']

Deux grands modèles s’opposent en informatique lorsqu’il est question de répéter des tâches : le modèle itératif et le modèle récursif.

Le modèle itératif, nous le connaissons, c’est celui des boucles. On place notre tâche dans une boucle et celle-ci sera donc répétée un certain nombre de fois.

Le modèle récursif est assez différent dans sa conception, il repose sur des fonctions. L’idée étant que la fonction s’appelle elle-même, provoquant ainsi une répétition, on parle alors de fonction récursive.

C’est un concept issu des mathématiques qui se définit assez bien et intuitivement, nous l’appliquons même généralement sans le savoir.
Prenons par exemple la somme d’une liste de N nombres : de quoi s’agit-il ? Simplement de l’addition entre le premier nombre de la liste et la somme des N-1 autres nombres.

Par exemple sum([1, 2, 3, 4, 5]) est égal à 1 + sum([2, 3, 4, 5]), sum([2, 3, 4, 5]) à 2 + sum([3, 4, 5]) et ainsi de suite.

Nous venons de définir la somme de manière récursive. On a réduit une opération complexe (la somme de N nombres) à une succession d’opérations plus simples (une addition entre deux nombres) et un procédé récursif (exécuter à nouveau la procédure sur un ensemble restreint).

En Python, cela donnerait le code suivant.

def my_sum(numbers):
    return numbers[0] + my_sum(numbers[1:])

Mais on remarque tout de suite un problème, on ne sait pas quand ça va s’arrêter. Cette fonction va-t-elle même s’arrêter ? En l’occurrence oui, mais en provoquant une erreur.

>>> my_sum([1, 2, 3, 4, 5])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in my_sum
  File "<stdin>", line 2, in my_sum
  File "<stdin>", line 2, in my_sum
  [Previous line repeated 3 more times]
IndexError: list index out of range

En effet, nos appels récursifs finissent par appeler my_sum([]) qui échoue car n’a pas de premier élément (numbers[0]).

Le souci est que c’est à nous de gérer explicitement la condition de fin et que nous ne l’avons pas fait. Ici la condition de fin est facilement identifiable, la somme des nombres d’une liste vide est toujours nulle. On devrait donc, dans le cas où l’on rencontre une liste vide, renvoyer directement zéro.

Nous pouvons ajouter cette condition à notre fonction récursive et constater que le comportement est alors bon.

>>> def my_sum(numbers):
...     if not numbers:
...         return 0
...     return numbers[0] + my_sum(numbers[1:])
... 
>>> my_sum([1, 2, 3, 4, 5])
15

Mais il y a des cas où la condition de fin est moins évidente à trouver, cela pouvant mener à une récursion infinie.

Récursion infinie

Notre premier cas ne possédait pas de condition de fin mais s’est arrêté en raison d’une IndexError. Que ce serat-il passé sans cette erreur ?

On peut prendre un cas assez similaire qui est de calculer la taille d’une chaîne de caractères. Récursivement, la taille d’une chaîne se conçoit comme l’addition entre deux tailles de sous-chaînes, par exemple entre la taille du premier caractère (1) et la taille du reste.
On a len('abcdef') égal à 1 + len('bcdef').

def my_len(s):
    return 1 + my_len(s[1:])

Là encore, nous avons oublié de prévoir la condition de fin (renvoyer 0 sur une chaîne vide), et patatra !

>>> my_len('abcdef')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in my_len
  File "<stdin>", line 2, in my_len
  File "<stdin>", line 2, in my_len
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Cette fois ce n’est pas une erreur dans notre code qui nous arrête, mais une erreur de Python lui-même qui nous indique que nous avons dépassé le nombre maximum de récursions. Nous sommes entrés dans une récursion infinie.

En fait, chaque appel récursif occupe un peu de mémoire dans notre programme, pour stocker le contexte de la fonction (les arguments qui lui sont passés par exemple). Quand nous empilons les appels récursifs, la mémoire utilisée croît, jusqu’à atteindre une limite. En Python c’est l’interpréteur qui fixe arbitrairement une limite de 1000 appels.

Récursions croisées

La récursivité ne se limite pas à une fonction seule, il est aussi possible de croiser des fonctions qui s’appelleraient les unes les autres.

Par exemple, comment déterminer si un nombre n est impair ? En regardant si n-1 est pair ! Et pour savoir si n-1 est pair on teste si n-2 est impair. On répète cela jusqu’à zéro que l’on sait pair (et donc non impair).

En Python, cela nous donnerait les deux fonctions suivantes.

def odd(n): # impair
    if n == 0:
        return False
    return even(n - 1)

def even(n): # pair
    if n == 0:
        return True
    return odd(n - 1)

Qui se comportent bien comme on veut pour calculer la parité des nombres.

>>> odd(5)
True
>>> even(5)
False
>>> odd(4)
False
>>> even(4)
True

Bien sûr je ne présente ces fonctions qu’à titre d’exemple. Les fonctions récursives étant déjà assez rares en Python pour les raisons expliquées plus haut, les récursions croisées le sont encore plus.
Et l’exemple présenté ci-dessus est particulièrement inefficace (on peut directement tester la parité d’un nombre avec n % 2).

Aussi, préférez dans la mesure du possible opter pour des solutions itératives.