Fonctions récursives

Qu'est-ce que la récursivité ? Principe et définition

La récursivité est une technique de programmation dans laquelle une fonction s'appelle elle-même, directement ou indirectement. Une fonction qui s'appelle elle-même est appelée une fonction récursive.

La récursivité est un concept puissant qui permet de résoudre certains problèmes de manière élégante et concise. Elle est souvent utilisée pour traiter des structures de données récursives (comme les arbres ou les graphes) ou pour implémenter des algorithmes qui se décomposent en sous-problèmes similaires.

Pour qu'une fonction récursive fonctionne correctement, elle doit avoir :

• Un ou plusieurs cas de base : Des cas où la fonction ne s'appelle pas elle-même, mais retourne directement un résultat.
• Un ou plusieurs cas récursifs : Des cas où la fonction s'appelle elle-même, mais avec des arguments qui se rapprochent des cas de base.

L'idée est de décomposer un problème en sous-problèmes plus petits, jusqu'à atteindre un cas de base que l'on sait résoudre directement.

Exemple classique : la fonction factorielle

Un exemple classique de fonction récursive est la fonction factorielle. La factorielle d'un nombre entier positif `n` (notée `n!`) est le produit de tous les entiers de 1 à `n`. Par convention, la factorielle de 0 est 1 (0! = 1).

Définition mathématique récursive de la factorielle :

• 0! = 1 (cas de base)
• n! = n * (n-1)! pour n > 0 (cas récursif)

Implémentation récursive en Python :

def factorielle(n):
    """Calcule la factorielle d'un nombre entier positif.

    Args:
        n (int): Le nombre entier.

    Returns:
        int: La factorielle de n.

    Raises:
        TypeError: Si n n'est pas un entier.
        ValueError: Si n est négatif.
    """
    if not isinstance(n, int):
        raise TypeError("n doit être un entier.")
    if n < 0:
        raise ValueError("n doit être positif ou nul.")
    if n == 0:
        return 1  # Cas de base
    else:
        return n * factorielle(n - 1)  # Cas récursif

print(factorielle(5))  # Affiche 120 (5! = 5 * 4 * 3 * 2 * 1 = 120)

Dans cet exemple :

• Le cas de base est `n == 0`, où la fonction retourne 1.
• Le cas récursif est `n > 0`, où la fonction s'appelle elle-même avec `n - 1`, et multiplie le résultat par `n`.

A chaque appel récursif, la valeur de `n` diminue, se rapprochant du cas de base (`n == 0`). Lorsque le cas de base est atteint, la chaîne d'appels récursifs se "déroule", et les résultats intermédiaires sont multipliés pour obtenir le résultat final.

Avantages et inconvénients de la récursivité

La récursivité présente des avantages et des inconvénients :

• Elégance et concision : La récursivité permet souvent d'exprimer des algorithmes de manière plus concise et plus élégante qu'avec des boucles.
• Adaptée à certains problèmes : Certains problèmes se prêtent naturellement à une solution récursive (par exemple, le traitement d'arbres ou de graphes).
• Lisibilité (parfois) : Pour certains problèmes, une solution récursive peut être plus facile à comprendre qu'une solution itérative (avec des boucles).

• Performance : Les appels de fonction récursifs peuvent être coûteux en termes de temps et de mémoire (empilement des appels sur la pile d'exécution).
• Risque de dépassement de pile : Si la fonction s'appelle elle-même trop de fois sans atteindre un cas de base, cela peut entraîner un dépassement de la pile d'exécution (erreur "RecursionError" en Python).
• Lisibilité (parfois) : Dans certains cas, une solution récursive peut être plus difficile à comprendre qu'une solution itérative.

Il est important de peser le pour et le contre avant d'utiliser la récursivité. Dans de nombreux cas, une solution itérative (avec des boucles) sera plus efficace et plus facile à comprendre.

Eviter les erreurs courantes : cas de base et profondeur de récursion

Voici quelques erreurs courantes à éviter lors de l'utilisation de la récursivité :

• Oublier le cas de base : Si vous oubliez le cas de base, la fonction s'appellera elle-même indéfiniment, entraînant un dépassement de pile.
• Cas de base incorrect : Si le cas de base n'est pas correctement défini, la fonction peut ne pas s'arrêter ou retourner un résultat incorrect.
• Ne pas se rapprocher du cas de base : Dans le cas récursif, assurez-vous que les arguments de l'appel récursif se rapprochent du cas de base. Sinon, la fonction risque de ne jamais s'arrêter.
• Dépasser la limite de récursion : Python a une limite sur la profondeur de récursion (le nombre maximum d'appels récursifs imbriqués). Cette limite peut être obtenue avec `sys.getrecursionlimit()` et modifiée avec `sys.setrecursionlimit()`, mais il est généralement préférable de ne pas dépasser la limite par défaut.

Exemple d'erreur : oubli du cas de base

def fonction_infinie(n):
    return n * fonction_infinie(n - 1)  # Oubli du cas de base : boucle infinie

# fonction_infinie(5)  # Provoquerait une RecursionError

Pour éviter les erreurs, assurez-vous toujours que votre fonction récursive a un cas de base correctement défini, et que les appels récursifs se rapprochent du cas de base.

Autres exemples de fonctions récursives

Voici quelques autres exemples classiques de fonctions récursives :

Calcul de la somme des n premiers entiers :

def somme(n):
 if n == 0:
  return 0
 else:
  return n + somme(n-1)

print(somme(5)) # 15

Recherche d'un élément dans une liste (dichotomie) :

def recherche_dichotomique(liste, element, debut=0, fin=None):
    if fin is None:
        fin = len(liste) - 1
    if debut > fin:
        return False  # Cas de base : l'élément n'est pas trouvé

    milieu = (debut + fin) // 2

    if liste[milieu] == element:
        return True  # Cas de base : l'élément est trouvé
    elif liste[milieu] < element:
        return recherche_dichotomique(liste, element, milieu + 1, fin)  # Cas récursif
    else:
        return recherche_dichotomique(liste, element, debut, milieu - 1)  # Cas récursif

Calcul de la suite de Fibonacci :

def fibonacci(n):
  if n <= 1:
   return n
  else:
   return fibonacci(n-1) + fibonacci(n-2)

Il existe de nombreux autres exemples, notamment dans le traitement d'arbres, de graphes, et dans certains algorithmes de tri.