Récursivité¶

Une fonction récursive est une fonction qui s’appelle elle-même. Chaque appel à la fonction est indépendant des autres, avec ses propres variables.

Une récursion a toujours la forme suivante :

if (cas simple):
    (solution immédiate)
else:
    (solution récursive,
    impliquant un cas plus simple que le problème original)

L’exemple le plus classique d’emploi de la récursivité est l’écriture de la fonction factorielle. Pour rappel, la factorielle d’un nombre n est définie comme n fois la factorielle du nombre n-1, et la factorielle de 1 est 1.

def fact(n):
    """
    :entrée n: int
    :pré-cond: n > 0
    :sortie f: int
    :post-cond: f = n! = 1×2×3×...×(n-1)×n
    """
    if n == 1:
       f = 1
    else:
       f = fact(n-1)*n
    print("--- fact({}) = {}".format(n,f))
    return f

    print(fact(6))

    --- fact(1) = 1
    --- fact(2) = 2
    --- fact(3) = 6
    --- fact(4) = 24
    --- fact(5) = 120
    --- fact(6) = 720
    720