CM #5 : Récursivité

Un autre chapitre court sur une notion-clef en algorithmique: la récursivité. Une fonction ou une procédure est dite récursive si dans son code elle fait appel à elle-même. Ce type de sous-programmes permet de réaliser des algorithmes complexes sans utiliser de boucles. La difficulté principale de ce genre d’algorithme est de s’assurer de la terminaison du programme.

Définition et utilisation

Récursivité

Un algorithme (fonction ou procédure) est dit récursif si sa définition (son code) contient un appel à lui-même. Un algorithme récursif s'oppose à un algorithme itératif.

Les algorithmes itératifs sont utilisés dans différents contextes:

le calcul de suite récursive (numérique par exemple)
les stratégies basées sur le principe diviser pour régner comme pour les algorithmes de rechercher ou de tri
le calcul sur des structures de données inductives (listes, arbres…), voir le cour de Programmation Avancée (S6 IMA3).

Remarque

Même si certains contextes se prêtent plus naturellement à l'utilisation d'algorithmes récursifs, il est toujours possible d'écrire une version itérative de l'algorithme.

Exemples classiques

L’exemple le plus pertinent pour illustrer les algorithmes récursifs et le calcul de n!. En effet, on se base sur la formulation récursive de la suite où n! = n \times (n-1)! et 1! = 0! = 1. L’algorithme est le suivant:

int fact(int n)
{
    if (0 == n)     return 1;
    else            return n * fact(n-1);
}

Lorsque l’on écrit un algorithme récursif, il faut faire attention à la définition de la fonction (notamment s’assurer qu’elle s’arrête) et à son utilisation (notamment son appel et son type de retour).

Un autre exemple classique est la suite de Fibonacci définie de la manière suivante u_n = u_{(n-1)} + u_{(n-2)} et u_0 = 0$, $u_1 = 1.

int fibo(int n)
{
    if ( 0 == n )       return 0;
    else if ( 1 == n )  return 1;
    else                return fibo(n-1) + fibo(n-2);
}

Enfin un autre exemple classique:

int sum(int n, int r)
{
    if ( 1 == n )   return r+1;
    else            return (n-1, r+1);
}

Que fait cet algorithme ?

Remarque

rest appelé paramètre d'accumulation.

Récursivité terminale

Un algorithme récursif est dit récursif terminal si l'appel récursif est la dernière instruction réalisée.

De fait, un algorithme récursif terminal ne nécessite pas de stocker la valeur obtenue par récursivité. Par exemple:

fact(n) n’est pas terminal car le résultat de fact(n-1) est stocké pour être multiplié par n
somme(n,r) est récursif terminal puisqu’il n’y a pas de stockage de résultat i.e. somme(n,r) = somme(n-1, r+1) = somme(n-2, r+2) = ...

Transformation récursif vers itératif

La transformation de récursif en itératif est dépendante de l’algorithme mais implique en général une boucle. Par exemple, le calcul de factorielle, version récursive,

int fact(int n)
{
    if (0 == n)     return 1;
    else            return n * fact(n-1);
}

devient en itératif

int fact_iter(int n)
{
    int f = 1;
    for (int i = 0; i < n; i++)
    {
        f *= i;
    }
    return f;
}