Récursivité en

À propos de Récursivité

La récursion est une façon d'exécuter du code de manière répétée à l'intérieur d'une fonction, en faisant en sorte que la fonction s'appelle elle-même. Les fonctions qui s'appellent elles-mêmes sont appelées fonctions récursives. On peut voir la récursion comme une autre façon de faire une boucle ou d'itérer. Et comme pour les boucles, on utilise une expression booléenne ou un test True/False pour déterminer quand arrêter l'exécution récursive.

Contrairement aux boucles, une récursion sans terminaison en Python ne peut pas tourner indéfiniment. Les valeurs utilisées à chaque appel de fonction sont placées dans leur propre cadre sur la pile de l'interprète Python. Si le nombre total d'appels de fonction occupe plus d'espace que la pile n'en propose, cela provoquera une erreur.

Implémentation par boucle ou par récursion

Une boucle et la récursion peuvent sembler similaires, dans la mesure où toutes deux sont itératives. Cependant, elles ont l'air différentes, aussi bien au niveau du code qu'au niveau de l'implémentation. Une boucle peut se dérouler dans le même cadre sur la pile d'appels. En général, on gère cela en mettant à jour une ou plusieurs variables afin de maintenir progressivement l'état à chaque itération. C'est une implémentation efficace, mais elle peut sembler un peu encombrée à la lecture du code.

La récursion, plutôt que de mettre à jour l'état des variables, peut passer directement des valeurs mises à jour comme arguments au prochain appel (à l'itération suivante) de la même fonction. Cela allège le corps de la fonction et peut clarifier la façon dont chaque mise à jour se produit. Cependant, c'est aussi une implémentation moins efficace, car chaque appel à la même fonction ajoute un cadre supplémentaire à la pile.

La récursion : pourquoi et pourquoi pas ?

S'il y a un risque de provoquer une erreur ou un débordement de pile, pourquoi donc utiliser une stratégie récursive pour résoudre un problème ? Lisibilité, traçabilité et intention. Il existe des situations où une solution est plus lisible ou plus facile à appréhender lorsqu'elle est exprimée par la récursion que par une boucle. Il peut aussi y avoir des contraintes du programme liées à l'utilisation ou à la modification des données, à la gestion de la complexité, à la délégation des responsabilités ou à l'organisation du travail.

Les problèmes qui se prêtent bien à la récursion incluent des problèmes complexes mais répétitifs qui deviennent de plus en plus petits au fil du temps, en particulier les algorithmes de diviser pour régner et les algorithmes cumulatifs. Cependant, en raison de la limite du nombre de cadres autorisés sur la pile en Python, tous les problèmes ne tirent pas profit d'une stratégie entièrement récursive. Les problèmes moins naturellement adaptés à la récursion incluent ceux qui ont un état stable mais qui doivent se répéter pendant un certain nombre de cycles, ceux qui doivent s'exécuter de manière asynchrone, et les situations qui demandent un grand nombre d'itérations.

Stratégie par boucle ou par récursion : l'insécurité d'Indira

Indira fait virer automatiquement sa prestation mensuelle de sécurité sociale sur son compte bancaire le deuxième mercredi de chaque mois. Indira s'inquiète de l'équilibre de son compte bancaire. Elle craint d'émettre des chèques avant que son argent ne soit déposé. Elle demande à sa petite-fille Adya de lui donner la liste des dates auxquelles son argent apparaîtra sur son compte.

Adya, qui apprend tout juste à programmer en Python, écrit un programme basé sur ses premières idées. Elle veut renvoyer une list des dates de dépôt afin qu'elles puissent être imprimées. Elle veut écrire une fonction qui fonctionnera pour n'importe quelle année. Au cas où le calendrier changerait (ou au cas où d'autres proches voudraient qu'Adya calcule leurs propres dates de dépôt), elle décide que la fonction doit prendre un paramètre supplémentaire pour le jour de la semaine. Enfin, Adya décide que la fonction doit prendre un paramètre pour indiquer quel jour de la semaine du mois il s'agit : le premier, le deuxième, etc. Pour toutes ces exigences, elle décide d'utiliser la classe date importée depuis datetime. En rassemblant tout cela, Adya aboutit à :

from datetime import date


def paydates_for_year(year, weekday, ordinal):
    """Returns a list of the matching weekday dates.
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    output = []

    for month in range(1, 13):
        for day_num in range(1, 8):
            if date(year, month, day_num).isoweekday() == weekday:
                output.append(date(year, month, day_num + (ordinal - 1) * 7))
                break
    return output

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))

Cette première itération fonctionne, mais Adya se demande si elle peut réécrire le code pour utiliser moins de lignes et moins de boucles imbriquées. Elle a aussi lu qu'il est bon de minimiser la modification d'état, alors elle aimerait voir si elle peut éviter de modifier certaines de ses variables comme output, month et day_num .

Elle connaît aussi la récursion et réfléchit à la façon dont elle pourrait modifier son programme pour utiliser une approche récursive. Les variables créées et modifiées dans sa fonction à boucle pourraient plutôt être passées en arguments. Plutôt que de modifier les variables à l'intérieur de sa fonction, elle pourrait passer des valeurs mises à jour comme arguments au prochain appel de fonction. Avec ces intentions, elle arrive à cette approche récursive :

from datetime import date


def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
    """Returns a list of the matching weekday dates
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
        month (int): The month number currently being processed.
        day_num (int): The day number of the month currently being processed.
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    if month == 13:
        return output
        
    if date(year, month, day_num).isoweekday() == weekday:
        return paydates_for_year_rec(
                 year, weekday, ordinal, month + 1, 1, output
                 + [date(year, month, day_num + (ordinal - 1) * 7)]
                 )
    
    return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))

Adya est contente qu'il n'y ait plus de boucles imbriquées, plus d'état modifié, et 2 lignes de code en moins !

Elle s'inquiète un peu du fait que l'approche récursive utilise plus d'étapes que l'approche par boucle, et qu'elle est donc moins « performante ». Mais réécrire le problème à l'aide de la récursion l'a vraiment aidée à gérer de vilaines boucles imbriquées (un risque pour les performances), une modification d'état excessive et la confusion autour d'une logique conditionnelle complexe. Elle la trouve aussi plus « lisible » : elle est sûre que, lorsqu'elle reviendra sur ce code après une pause, elle pourra le relire et se rappeler plus facilement ce qu'il fait.

À l'avenir, Adya essaiera peut-être de résoudre les problèmes d'abord de manière récursive. Elle trouvera peut-être plus facile de parcourir d'abord le problème en étapes claires lorsque l'imbrication, la modification et la complexité sont réduites au minimum. Après avoir établi la logique de base, elle pourra alors se concentrer sur l'optimisation de ses premières étapes récursives en une approche par boucle plus performante.

Plus tard encore, lorsqu'elle découvrira tuples, Adya pourra envisager d'autres approches « optimisées », comme utiliser une list comprehension avec Calendar.itermonthdates, ou de mémoïser certaines valeurs.

Variante récursive : l'appel terminal

Un appel terminal se produit lorsque la dernière instruction d'une fonction se contente de s'appeler elle-même, rien de plus. Cet exemple n'est pas un appel terminal, car la fonction ajoute 1 au résultat de son propre appel :

def print_increment(step, max_value):
    if step > max_value:
        return 1
    print(f'The step is {step}')
    return 1 + print_increment(step + 1, max_value)


def main():
    retval = print_increment(1, 2)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

Cela affiche :

The step is 1
The step is 2
retval is 3 after recursion

Pour la réécrire en appel terminal, fais de retval un paramètre de print_increment.

def print_increment(step, max_value, retval):
    if step > max_value:
        return retval
    print(f'The step is {step}')
    return print_increment(step + 1, max_value, retval + 1)


def main():
    retval = print_increment(1, 2, 1)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

Tu trouveras peut-être un appel terminal encore plus facile à appréhender qu'un appel récursif qui n'est pas un appel terminal. Cependant, lorsqu'on utilise la récursion, il est toujours important de savoir qu'il n'y aura pas tellement d'itérations que la pile débordera.

Les limites de la récursion en Python

Certains langages savent optimiser les appels terminaux, de sorte que chaque appel récursif réutilise le cadre de pile du premier appel à la fonction (un peu comme une boucle réutilise un cadre), au lieu d'ajouter un cadre supplémentaire à la pile. Python n'est pas l'un de ces langages. Pour se prémunir contre un débordement de pile, Python impose une limite de récursion qui vaut par défaut mille cadres. Une exception RecursionError est levée lorsque l'interprète détecte que la limite de récursion a été dépassée. Il est possible d'utiliser la méthode sys.setrecursionlimit pour augmenter la limite de récursion, mais cela risque de provoquer une erreur de segmentation à l'exécution qui fera planter le programme, et peut-être même le système d'exploitation.

Ressources

Pour en apprendre plus sur l'utilisation de la récursion en Python, tu peux commencer par

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively