Récursivité

Définition

Jusqu'à présent, on donnait des ordres à une machine, et elle les exécutait : c'est de la programmation impérative et du code itératif. Mais pourrait-on donner des ordres récursifs, avec une seule formule ? C'est la magie de la programmation fonctionnelle !

Idée

On va essayer de changer de sens ! Au lieu de résoudre une labyrinthe en partant du départ, on part de l'arrivée.

Voici deux exemples de fonctions, récursives et itératives

Itératif

def somme_it(nb : int) -> int:
    result = 0
    for i in range(nb + 1):
        result += i
    return result

Récursif

def somme_rec(nb : int) -> int:
    if nb == 0:
      return 0
    return nb + somme_rec(nb - 1)

Définition

On appelle fonction récursive toute fonction qui s'appelle elle-même.

Une fonction récursive est constituée d'un ou de plusieurs cas d'arrêt (ici, nb == 0) et d'un ou de plusieurs cas récursifs (ici, nb + somme_rec(nb - 1)). Il est toujours possible de faire des boucles dans des fonctions récursives, mais il faut impérativement que la fonction renvoie toujours le même type (auquel cas les opérations vont échouer, car on ne peut pas additionner ou multiplier des types différents entre eux).

En Pratique

On ne réalise plus les traces des fonctions mais les appels récursifs (aussi appelés arbres, c.f. cours des L2). Les appels se stockent dans une pile (idem, on voit ça plus tard) qui a une certaine limite (1000 en python).

Récursif/Itératif

Théorème

Toute fonction peut s'écrire de manière récursive et itérative.

Pour passer de l'un à l'autre, on fait un accumulateur initialisé sur le cas de base.

Pour certaines fonctions, l'écriture récursive (ou itérative) est plus simple.

Preuves

Les preuves des fonctions récursives sont légèrement différentes : on l'utilise pas des variant de boucle mais des variants (tout court). Ils correspondent au paramètres de la fonction. Il faut prouver que chaque variant (donc paramètres) atteint un cas de base.

Le variant n'a pas forcément à être croissant/décroissant.

Corrections et clarifications

• Remplacer "labyrinthe" par un exemple plus concret si nécessaire.
• En Python, la profondeur maximale d'appel récursif par défaut est souvent ~1000 ; on peut la modifier avec sys.setrecursionlimit() si besoin.

Remarques sur les preuves

Pour prouver la terminaison d'une fonction récursive, on utilise un variant (un paramètre) qui évolue systématiquement vers un cas de base ; il n'a pas besoin d'être strictement monotone (croissant/décroissant) mais doit atteindre le cas d'arrêt en un nombre fini d'étapes.