Chapitre 3 : La Récursivité et son Application dans des Algorithmes

 

Chapitre 3 : La Récursivité et son Application dans des Algorithmes

Introduction à la Récursivité

La récursivité est une technique de programmation où une fonction s'appelle elle-même pour résoudre un problème. Cette approche est particulièrement utile pour des problèmes qui peuvent être divisés en sous-problèmes plus petits du même type. Dans ce chapitre, nous explorerons les principes de la récursivité, ses avantages et inconvénients, et comment l'appliquer efficacement dans des algorithmes.

Définition et Principes de la Récursivité

Définition

Une fonction est dite récursive si elle fait appel à elle-même pour accomplir sa tâche. En général, une fonction récursive se compose de deux parties :

  • Le cas de base : C'est la condition qui arrête les appels récursifs. Sans ce cas, la récursion continuerait indéfiniment.
  • Le cas récursif : C'est la partie de la fonction où elle se rappelle elle-même avec des arguments modifiés pour rapprocher la solution du cas de base.

Principes de la Récursivité

  1. Décomposition du problème : Diviser le problème en sous-problèmes plus simples.
  2. Appel récursif : Résoudre les sous-problèmes en appelant la fonction récursive.
  3. Cas de base : Définir une condition d'arrêt pour éviter une récursion infinie.

Comparaison Récursivité vs Itération

  • Récursivité : Chaque appel de fonction ajoute un niveau dans la pile d'exécution, ce qui peut consommer plus de mémoire. Elle est souvent plus élégante pour des problèmes naturels comme les structures arborescentes.
  • Itération : Utilise des boucles (for, while) et est généralement plus efficace en termes de consommation de mémoire, mais peut être moins intuitive pour certains problèmes.

Récursion Simple

Cas de Base et Cas Récursif

Pour comprendre la récursion simple, examinons l'exemple classique du calcul de la factorielle d'un nombre n (noté n!). La factorielle est définie comme :

  • Cas de base : 0! = 1
  • Cas récursif : n! = n * (n - 1)!

Exemple de Code :

python

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

Exemples Classiques

  1. Calcul de la factorielle
  2. Suites Mathématiques : La suite de Fibonacci est un autre exemple de récursion simple où chaque terme est la somme des deux termes précédents.

Récursion Multiple et Récursion Terminale

Récursion Multiple

Certaines fonctions récursives nécessitent plusieurs appels récursifs pour résoudre un problème. Un exemple classique est la recherche dans un arbre binaire.

Exemple :

python

def recherche_arbre(nœud, valeur): if nœud is None: return False if nœud.valeur == valeur: return True return recherche_arbre(nœud.gauche, valeur) or recherche_arbre(nœud.droit, valeur)

Récursion Terminale

La récursion terminale (ou récursion en queue) est une forme d'appel récursif où l'appel récursif est la dernière opération effectuée avant le retour du résultat. Elle peut être optimisée par le compilateur pour éviter de consommer trop de mémoire.

Exemple de Code :

python

def factorielle_terminal(n, accum=1): if n == 0: return accum else: return factorielle_terminal(n - 1, n * accum)

Optimisation des Récursions : Récursion Terminale

L'optimisation de la récursion terminale, aussi connue sous le nom d'optimisation de la récursion en queue, consiste à transformer les appels récursifs en itérations lorsque cela est possible. Cela permet de réduire l'utilisation de la pile et d'éviter des dépassements de mémoire.

Problèmes Récursifs Complexes

Algorithmes de Division et Conquête

Les algorithmes de division et conquête utilisent la récursivité pour diviser un problème complexe en sous-problèmes plus simples. Deux exemples courants sont :

  1. Quicksort : Un algorithme de tri qui choisit un pivot et partitionne les éléments autour de ce pivot.
  2. Mergesort : Un algorithme de tri qui divise la liste en sous-listes plus petites, les trie, puis les fusionne.

Exemple de Code pour Quicksort :

python

def quicksort(liste): if len(liste) <= 1: return liste pivot = liste[len(liste) // 2] gauche = [x for x in liste if x < pivot] milieu = [x for x in liste if x == pivot] droite = [x for x in liste if x > pivot] return quicksort(gauche) + milieu + quicksort(droite)

Récursion dans les Structures de Données Complexes

La récursion est également utilisée pour parcourir des structures de données complexes telles que les arbres et les graphes.

Exemple : Parcours en profondeur d'un arbre binaire.

Gestion de la Mémoire et Limitations

Empilement des Appels Récursifs

Chaque appel récursif ajoute un cadre d'appel à la pile d'exécution. Une récursion profonde peut conduire à une consommation excessive de mémoire et à un dépassement de pile.

Dépassement de la Pile (Stack Overflow)

Un dépassement de pile se produit lorsque la pile d'exécution est trop remplie, généralement en raison de récursions trop profondes ou d'une récursion infinie. Cela peut entraîner des erreurs d'exécution et des plantages de programme.

Exemple d'Erreur :

python

def boucle_infinie(): boucle_infinie()