La récursivité

La récursivité est le fait de permettre à une fonction de faire appel à elle-même. Un exemple classique d'une fonction récursive est la fonction factorielle $n! = n * (n-1)!$ pour tout entier naturel $n$.

Il est parfaitement possible de la définir en Python.

def fact(x: int) -> int:
    if x < 0:
        raise InvalidArgument
    elif x <= 1:
        return 1
    else:
        return x * fact(x-1)

Un autre cas classique est celui de la suite de Fibonacci qui a des propriétés étonnantes, ou encore la fonction d'Ackerman-Péter définie comme suit (même si ces fonctions sont calculables, elles demandent très vite un temps considérable à calculer dès lors que l'on fournit des arguments non triviaux) :

def A(m:int, n:int) -> int:
    if m == 0:
        return n+1
    elif n == 0 and m > 0:
        return A(m-1,1)
    elif m > 0 and n > 0:
        return A(m-1, A(m, n-1))

Lorsque vous utilisez des fonctions récursives il est nécessaire de respecter les règles suivantes :

1. La fonction doit commencer par tester les cas terminaux qui servent à arrêter la récursion. Ces cas terminaux doivent systématiquement être présents dans le code, faute de quoi on crée des fonctions qui ne termineront jamais et épuiseront rapidement les ressources de la machine jusqu'à provoquer l'arrêt brutal du programme avec une erreur.

2. Les appels récursifs doivent systématiquement faire intervenir des arguments "plus petits" que les arguments initiaux de sorte à garantir que la succession des appels récursifs atteigne un cas terminal. Dans les exemples fournis, n décroît systématiquement dans le cas de la factorielle jusqu'à atteindre 0 ou 1; dans le cas de la fonction d'Ackerman, l'argument m est soit décroissant, soit c'est n qui est décroissant qui amène ensuite à faire décroître m lorsque n vaut 0.

Ci-dessous un tri fusion écrit de façon récursive :

def merge_sort(l):

    s = len(l)
    # Gestion du cas d'arrêt : la liste vide ou la liste composée d'un seul élément
    # Ces deux listes sont déjà triées donc on peut les retourner telles quelles
    if s <= 1:
        return l
    else:
        # Si la liste est plus grande, on la sépare en deux sous-listes, et on trie
        # chacune d'entre elles par un appel récursif.
        l1 = iter(merge_sort(l[:s // 2]))
        l2 = iter(merge_sort(l[s // 2:]))

        # Ensuite il suffit d'interclasser les deux sous-listes triées
        # Pour ce faire on a défini l1 et l2 _itérateurs_ sur les sous-listes triées

        # Phase 1 : on vérifie qu'aucune des deux sous-listes n'est vide
        # (si c'est le cas, on retourne l'autre sous-liste comme résultat)
        try:
            i1 = next(l1)
        except StopIteration:
            return [_ for _ in l2]

        try:
            i2 = next(l2)
        except StopIteration:
            return [i1] + [_ for _ in l1]

        result = []

        # Phase 2 : on ajoute le plus petit de (i1, i2) à la liste finale
        # et on passe à l'élément suivant dans la sous-liste correspondante 
        # jusqu'à épuisement de l'une des sous-listes (occurrence de StopIteration)
        try:
            while True:
                if i1 > i2:
                    result.append(i2)
                    i2 = next(l2)
                else:
                    result.append(i1)
                    i1 = next(l1)
        except StopIteration:
            # Ajout de la sous-liste restante au résultat
            if i1 > i2:
                result.append(i1)
                result.extend([_ for _ in l1])
            else:
                result.append(i2)
                result.extend([_ for _ in l2])

        return result


print(merge_sort([1, 5, 7, 2, -8]))