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

Cas de Base et Cas Récursifs

Header :

La récursivité est basée sur deux concepts clés : le cas de base (ou cas de terminaison) et le cas récursif. Le cas de base spécifie la condition qui arrête la récursivité, tandis que le cas récursif définit comment résoudre un problème en le décomposant en des sous-problèmes plus simples. Dans ce chapitre, nous ne verrons pas de nouvelle notions, mais nous décomposerons et insisterons sur le point de la récursivité pour bien insister sur le point qui va faire la différence entre une fonction qui plante et une fonction qui fonctionne.

Body

1. Cas de Base

Le cas de base est une condition qui indique quand la récursivité doit s'arrêter. Il est essentiel pour éviter une récursion infinie. Lorsque la condition du cas de base est remplie, la fonction récursive retourne un résultat sans effectuer d'appel récursif supplémentaire.

Exemple de cas de base dans une fonction récursive (calcul du factoriel) :

FONCTION factoriel(n : ENTIER) : ENTIER
    SI n = 0 ALORS
        RETOURNER 1  // Cas de base : 0! = 1
    SINON
        RETOURNER n * factoriel(n - 1)  // Cas 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. Cela arrête la récursivité.

2. Cas Récursif

Le cas récursif décrit comment résoudre un problème en le décomposant en des sous-problèmes plus simples. Une fonction récursive s'appelle elle-même avec des valeurs modifiées pour progresser vers le cas de base.

Exemple de cas récursif dans la même fonction (calcul du factoriel) :

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

Dans le cas récursif, la fonction factoriel s'appelle elle-même avec une valeur réduite de n (c'est-à-dire n - 1). Cette étape est répétée jusqu'à ce que n atteigne le cas de base.

3. Importance de l'équilibre entre le Cas de Base et le Cas Récursif

L'équilibre entre le cas de base et le cas récursif est essentiel. Un cas de base incorrect peut entraîner une récursion infinie, tandis qu'un cas récursif incorrect peut ne pas conduire à une solution. Il est important de s'assurer que la récursivité se termine correctement lorsque le cas de base est atteint.
Si un de ces 2 cas n'est pas bien codé, votre fonction plante.