Factorielle et somme des n premiers entiers

Factorielle et somme des n premiers entiers

Tu as déjà vu la factorielle ; voici un second exemple classique de récursivité : la somme des n premiers entiers, c'est-à-dire 1 + 2 + 3 + ... + n.

Cette somme se définit récursivement ainsi : la somme jusqu'à n est égale à n plus la somme jusqu'à n moins 1. Le cas de base est n égal 0 : la somme jusqu'à 0 vaut 0.

def somme(n):
    if n <= 0:
        return 0                # (cas de base)
    else:
        return n + somme(n - 1) # (cas recursif)

print(somme(5))   # (affiche 15, car 1+2+3+4+5 = 15)

Compare cette version récursive à une version classique avec une boucle :

def somme_iterative(n):
    total = 0
    for i in range(1, n + 1):
        total = total + i
    return total

Les deux fonctions renvoient exactement le même résultat. La récursivité n'est donc pas la seule solution : c'est souvent une question de clarté. Pour un problème qui se définit naturellement en fonction d'une version plus petite de lui-même, la version récursive est parfois plus lisible et plus proche de la définition mathématique du problème.

Reprenons la factorielle avec un autre exemple de déroulement, factorielle(4) :

# factorielle(4) = 4 * factorielle(3)
# factorielle(3) = 3 * factorielle(2)
# factorielle(2) = 2 * factorielle(1)
# factorielle(1) = 1   (cas de base atteint)
# donc factorielle(4) = 4 * 3 * 2 * 1 = 24

Retiens la méthode générale pour construire une fonction récursive : identifie d'abord le cas de base le plus simple, puis exprime le cas général en fonction d'un problème plus petit qui se rapproche de ce cas de base.