date: 2023-10-16
Type: Cours
Projet: Blindcode
Cours: Algorithmie

Principe de la Récursivité

Header :

La récursivité est un concept fondamental en programmation où une fonction s'appelle elle-même pour résoudre un problème. Cela permet de résoudre des problèmes complexes en les décomposant en des sous-problèmes plus simples. Dans ce chapitre, nous explorerons les principes de la récursivité en pseudo-code.

Body

1. Fonction Récursive de Base

Une fonction récursive commence par définir un cas de base où la fonction s'arrête. Ensuite, elle s'appelle elle-même avec un problème plus simple à résoudre. Le cas de base est essentiel pour éviter une récursion infinie.

Exemple de fonction récursive de base pour le calcul d'un factoriel :

FONCTION factoriel(n : ENTIER) : ENTIER
    SI n = 0 ALORS
        RETOURNER 1  // Cas de base : 0! = 1
    SINON
        RETOURNER n * factoriel(n - 1)  // Appel récursif
    FIN SI
FIN FONCTION

Dans cet exemple, le cas de base est défini lorsque n est égal à zéro, et la fonction retourne 1. Sinon, la fonction s'appelle elle-même avec n - 1 pour résoudre un problème plus simple.

A toi de jouer

Que fait la fonction si je l'appelle avec 0 ?
Que fait la fonction si je l'appelle avec 4 ?
Que fait la fonction si je l'appelle avec 10 ?
Que fait la fonction si je l'appelle avec -5 ?
Que fait la fonction si je l'appelle avec 3.5 ?

2. Récursivité sur des Structures de Données

La récursivité peut également être utilisée pour traiter des structures de données récursives, telles que les listes chaînées ou les arbres. Dans ce cas, la fonction récursive parcourt la structure de données en appelant récursivement la fonction sur les sous-structures.

Exemple de récursivité sur une liste chaînée :

FONCTION sommeListe(liste : LISTE) : ENTIER
    SI LISTE_EST_VIDE(liste) ALORS
        RETOURNER 0  // Cas de base : liste vide
    SINON
        RETOURNER PREMIER_ELEMENT(liste) + sommeListe(SUPPRIMER_PREMIER_ELEMENT(liste))  // Appel récursif
    FIN SI
FIN FONCTION

Dans cet exemple, la fonction sommeListe calcule la somme des valeurs dans une liste chaînée en utilisant la récursivité. Le cas de base est défini lorsque la liste est vide, et la fonction retourne 0. Sinon, elle additionne la valeur du nœud actuel avec la somme des valeurs dans le reste de la liste.

3. Optimisation de la Récursivité

La récursivité peut être coûteuse en termes de ressources, car chaque appel récursif ajoute une nouvelle pile d'appels. Pour éviter les problèmes de débordement de pile, il est parfois nécessaire d'optimiser les fonctions récursives. Une technique courante est la "récursion de queue," où l'appel récursif est la dernière instruction de la fonction, ce qui permet à certains compilateurs d'optimiser le code.

La récursivité est un concept puissant qui permet de résoudre des problèmes complexes en les décomposant en des sous-problèmes plus simples. Elle est particulièrement utile pour traiter des structures de données récursives. Cependant, il est important de définir un cas de base pour éviter une récursion infinie et d'optimiser les fonctions récursives si nécessaire pour éviter les débordements de pile.