Le cas de base : la clé d'une récursivité correcte

Le cas de base : la clé d'une récursivité correcte

Toute fonction récursive correcte a besoin d'un cas de base : une condition simple, sans appel récursif, qui arrête la chaîne d'appels et renvoie directement un résultat.

Pour la factorielle, le cas de base naturel est 0! égal 1 (par convention mathématique), ou 1! égal 1. Voici la version complète et correcte :

def factorielle(n):
    if n <= 1:
        return 1                      # (cas de base : arrete la recursivite)
    else:
        return n * factorielle(n - 1) # (cas recursif)

Déroulons factorielle(3) :

• factorielle(3) appelle 3 * factorielle(2)
• factorielle(2) appelle 2 * factorielle(1)
• factorielle(1) atteint le cas de base : renvoie 1, sans nouvel appel
• factorielle(2) peut alors calculer 2 * 1 = 2
• factorielle(3) peut alors calculer 3 * 2 = 6

Le résultat final est bien 6, ce qui correspond à 3 multiplié par 2 multiplié par 1.

Règle à retenir : chaque fonction récursive doit contenir au moins deux éléments :

1. un cas de base (ou plusieurs), qui renvoie une valeur directement, sans appel récursif,
2. un cas récursif, qui appelle la fonction sur un problème strictement plus petit, en se rapprochant du cas de base.

Si tu oublies le cas de base, ou si le cas récursif ne se rapproche jamais du cas de base (par exemple en appelant factorielle(n + 1) par erreur), la fonction s'appelle indéfiniment : c'est une récursion infinie, qui finit par provoquer une erreur (RecursionError en Python).