Récursivité en programmation : définition, exemples Python et cas d'usage

La récursivité est un concept fondamental en programmation, à la fois élégant et puissant, bien qu'il puisse sembler complexe au premier abord. Elle désigne une fonction qui s'appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes similaires. Pour un exemple ludique, tapez récursivité sur Google : les suggestions de recherche forment un œuf de Pâques récursif ! Si vous souhaitez maîtriser la programmation récursive, suivez ce guide détaillé.

Qu'est-ce qu'une fonction récursive ?

Une fonction récursive est une fonction qui s'invoque elle-même, créant ainsi une boucle logique. Contrairement à une boucle infinie, elle est contrôlée par une condition d'arrêt (ou cas de base), qui met fin à la récursion une fois atteinte.

Comme une boucle for ou while, elle évite l'exécution infinie. Cependant, l'ordinateur traite la récursion différemment : chaque appel s'empile en mémoire (pile d'exécution). Certains algorithmes sont plus efficaces en récursion (ex. : arbres), d'autres en itération (ex. : boucles simples).

Comment écrire une fonction récursive

Toute fonction récursive suit cette structure en pseudo-code :

def nom_fonction(parametre):
    if condition_arret:
        return resultat
    else:
        return nom_fonction(nouveau_parametre)

Nous utilisons Python pour les exemples. La clé : définir d'abord le cas de base (condition d'arrêt), puis l'appel récursif avec des paramètres modifiés pour progresser vers ce cas.

Exemple : calcul de factorielle en Python

La factorielle de n (notée n!) est le produit de tous les entiers de 1 à n (ex. : 5! = 120).

def factorielle(n):
    if n == 1:
        return 1
    else:
        return n * factorielle(n - 1)

resultat = factorielle(3)
print(resultat)  # Affiche : 6

Traçons l'exécution pour factorielle(3) :

1. n = 3 → Pas de base → 3 * factorielle(2) (mise en pause).
2. n = 2 → Pas de base → 2 * factorielle(1) (pause).
3. n = 1 → Base → Retourne 1.
4. Étape 2 reprend : 2 * 1 = 2.
5. Étape 1 reprend : 3 * 2 = 6.

Visualisez la récursion comme une pile : chaque appel s'empile jusqu'au cas de base, puis les résultats "défilent" vers le haut. Attention : une récursion profonde consomme beaucoup de mémoire (risque de débordement de pile).

Préférez les boucles pour les tâches simples, mais la récursion excelle pour les structures hiérarchiques.

Convertir une boucle en récursion

Exemple : boucle demandant un nombre pair.

# Version itérative
i = int(input("Entrez un nombre pair : "))
while i % 2 != 0:
    print("Ce nombre n'est pas pair. Veuillez entrer un nouveau nombre :")
    i = int(input())

Version récursive (inefficiente, à titre éducatif) :

def demander_nombre_pair(nombre):
    if nombre % 2 == 0:
        return nombre
    else:
        print("Ce nombre n'est pas pair. Veuillez entrer un nouveau nombre :")
        return demander_nombre_pair(int(input()))

i = demander_nombre_pair(int(input("Entrez un nombre pair : ")))

Cette version illustre le principe, mais gaspille de la mémoire. Utilisez-la pour l'entraînement !

Exemple concret : recherche en arbre binaire

La récursion brille pour les arbres binaires, où chaque nœud a deux enfants.

Pour chercher 6 (parcours préordre gauche-droite) :

def search_tree(noeud, cible):
    if noeud is None or noeud.valeur == cible:
        return noeud.valeur == cible
    # Parcours gauche
    if search_tree(noeud.gauche, cible):
        return True
    # Parcours droit
    return search_tree(noeud.droite, cible)

Ordre de visite : 2, 7, 2, 6 (trouvé), etc. La pile suit naturellement les branches.

Résumé et conseils

La récursion demande pratique : tracez les appels étape par étape (utilisez des post-it pour simuler la pile !). Commencez toujours par le cas de base, puis l'appel récursif.

Exercez-vous en réécrivant des boucles en récursion. Avec l'expérience, vous l'appliquerez à des algorithmes avancés comme les fractales ou les graphes.