Récursivité

Lorsque nous écrivons des programmes, nous faisons généralement appel à différentes fonctions pour effectuer une tâche très précise. Nous appelons par exemple sqrt pour calculer la racine carrée d’un nombre, ou une fonction max ou min pour trouver le maximum ou le minimum de plusieurs valeurs. La récursivité est le fait qu’une fonction s’appelle elle-même. Ainsi, si nous avons implémenté une fonction nommée f, et que dans le corps de cette fonction f nous appelons à nouveau f, on a alors un appel récursif :

def f(n):                                   # Définit une fonction nommée f
    print(f'f() called with argument {n}')  # Affiche un message lors de chaque appel (pour démonstration)
    if n <= 0:                              # Arrête la fonction si n est négatif
        print('Let\'s stop here...')
    else:                                   # Sinon, appelle f avec un nombre plus petit
        f(n - 1)

f(10)

This is what the program would print

f() called with argument 10
f() called with argument 9
f() called with argument 8
f() called with argument 7
f() called with argument 6
f() called with argument 5
f() called with argument 4
f() called with argument 3
f() called with argument 2
f() called with argument 1
f() called with argument 0
Let's stop here...

Ceci est un exemple très simple montrant comment mettre en place une fonction récursive basique. Dans un contexte plus réel, on réalise généralement des calculs dans la fonction et on renvoie le résultat plutôt que d’afficher un message.

Dans les problèmes d’algorithmique, la récursivité peut s’avérer très utile, notamment pour les graphes, certains algorithmes de tri avancés ou encore le backtracking, thèmes que nous aborderons plus tard dans le cours. Les problèmes récursifs sont très communs et il est parfois plus facile de programmer une solution récursive qu’une solution itérative basée sur des boucles.

Video preview — Une vidéo de Reducible – 5 étapes simples pour résoudre n’importe quel problème récursif

Le principe qui consiste à résoudre un problème complexe en le décomposant récursivement jusqu’à atteindre la plus petite partie du problème s’explique souvent grâce à ce qu’on appelle le « saut de foi récursif ».

Le saut de foi récursif

Pour implémenter une solution récursive, on crée d’ordinaire une fonction qui fait appel à elle-même. On parle alors d’appel récursif.

Le grand avantage des solutions récursives est de pouvoir supposer que la fonction marche correctement pour certains cas simples, et de s’appuyer sur ce fonctionnement pour construire la solution de cas plus complexes. Tout comme lorsque l’on appelle d’autres fonctions telles que sqrt, max ou abs, on peut considérer que la fonction sait déjà faire son travail pour des cas plus petits et utiliser ces résultats pour traiter le cas en cours.

💡

La seule exigence est de veiller à ce que la fonction aboutisse à un cas de base (le cas le plus simple). Dans le cas contraire, on risque de tomber dans une fonction récursive infinie, ce qui provoquerait un StackOverflow !

Pour illustrer comment insérer un vrai calcul dans une fonction récursive, prenons l’exemple de la somme de tous les nombres de 0, 1, 2, …, n à partir d’un entier n.

Commençons par implémenter pas à pas la fonction sum. Nous voulons d’abord nous assurer que la fonction gère correctement le cas le plus simple (calculer la somme lorsque n vaut 0 ou 1) :

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:         # Si n est 0 => la somme est 0
        return 0       # Fin de l'exécution
    if n == 1:         # Si n est 1 => la somme est 1
        return 1       # Fin de l'exécution

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> None (car nous n’avons pas encore implémenté cette partie)

Grâce à cette première phase, on sait déjà que sum(0) renvoie 0 et sum(1) renvoie 1. Même si la fonction sum s’appelle elle-même avec ces valeurs, ces cas sont gérés correctement.

On peut alors aller plus loin et implémenter la fonction pour n = 2 et n = 3, en profitant du fait que l’on connaît déjà les résultats de sum(1) et sum(0) :

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:             # Si n est 2, on ajoute 2 au résultat de sum(1)
        return n + sum(1)  # ou n + sum(n - 1)
    if n == 3:             # Si n est 3, on ajoute 3 au résultat de sum(2)
        return n + sum(2)  # ou n + sum(n - 1)

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> None (car nous n’avons pas encore implémenté cette partie)

On voit clairement à présent que sum marche pour n = 0, 1, 2 et 3.

À ce stade, pour traiter des valeurs supérieures à 3, il suffit de faire en sorte que la fonction finisse par appeler les cas plus simples (0, 1, 2 ou 3). Pour n = 4, on calcule sum(4) en ajoutant 4 à sum(3) ; pour n = 5, on ajoute 5 à sum(4), etc. :

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return n + sum(1)
    if n == 3:
        return n + sum(2)
    # Pour tous les autres cas (4, 5, 6, ...)
    return n + sum(n - 1)

print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...

Les points clés d’une fonction récursive sont :

Cas de base : Une condition qui met fin à la récursivité. Sans cela, la fonction continuerait à s’appeler sans cesse, provoquant une boucle infinie. Ici, ce sont n == 0 et n == 1.

Étape récursive : La partie où la fonction s’appelle, souvent avec un argument différent. Ici, on retrouve sum(n - 1).

Comme les appels pour n == 1, n == 2 et n == 3 sont en fait identiques à ceux pour n == 4, n == 5, etc., nous pouvons simplifier davantage en ne gardant qu’un seul cas de base (n == 0) :

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    return n + sum(n - 1)

print(sum(2))          # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...

En adoptant ce « saut de foi récursif », on part du principe que la fonction donne le bon résultat pour des cas plus simples ou plus petits, et on crée ainsi la solution pour les cas restants. C’est ainsi que fonctionnent et s’implémentent la plupart des fonctions récursives.

💡

Faire un appel récursif revient à appeler une autre fonction dont vous savez déjà qu’elle marche pour les nouveaux arguments.

Challenge

Implémentez une fonction récursive qui calcule n! modulo .

Entrée

L’entrée contient un seul entier n (1 ≤ n ≤ 1000).

Sortie

Le programme doit afficher le résultat de n! modulo .

Exemples

Entrée	Sortie
5	120
10	3628800

Le saut de foi récursif

Challenge

Entrée

Sortie

Exemples

Constraints

To check your solution you need to sign in

Sign in to continue