Name: Du C au C++ De la programmation procédurale à l'objet (2ième édition)
Rating: 5 (2 reviews)

Fonctions récursives

1. Qu’est-ce que la récursivité ?

Une notion est dite récursive lorsqu’elle se contient elle-même en partie ou si elle est partiellement définie à partir d’elle-même. La récursivité est appuyée sur le raisonnement par récurrence. Typiquement il s’agit d’une suite dont le terme général s’exprime à partir de termes qui le précèdent. Par exemple, la factorielle d’un nombre N donné est le produit des nombres entiers inférieurs ou égaux à ce nombre N. Ceci est noté N! avec par définition la factorielle de 0 à 1, ce qui donne :

0! = 1

1! = 1

2! = 1*2

3! =1*2*3

(...)

N! = 1*2*3 ....*(N-1)*N

La notation générale est :

N! = 1 si N = 0

N! = N*(N-1)! si N > 0

et l’on voit que la factorielle de N est définie en fonction d’elle-même (N-1)!, c’est un processus récursif.

2. Une fonction récursive basique

Une fonction récursive est en programmation une fonction qui s’appelle elle-même. De ce fait un algorithme récursif va jouer sur les paramètres en entrée de la fonction qui seront modifiés à chaque nouvel appel de la fonction dans son propre corps. Par exemple, dans un tri au départ nous avons un ensemble D et la récursion s’exerce sur des sous-ensembles de D jusqu’à ce qu’il n’y ait plus de sous-ensemble possible.

L’appel de la fonction par elle-même peut être direct, par exemple une fonction f() qui appelle f(), ou indirecte si f() appelle g() qui appelle f(). Nous nous en tiendrons à la récursion directe dans la suite de ce module.

Pour une fonction récursive il y a trois aspects fondamentaux :

Le test d’arrêt : comment s’arrête la succession des appels ?
La décomposition des ou de la donnée(s) : sur quelle base sont faits les appels successifs ?
L’empilement puis le dépilement en mémoire des appels successifs. Chaque appel possède en effet ses propres variables locales en mémoire (comme s’il s’agissait d’appels de fonctions différentes).

Voici un exemple de fonction récursive :


#include <stdio.h> 
#include <stdlib.h> ...

Exemples classiques de fonctions récursives

Voici un ensemble d’exemples souvent cités et bien intéressants pour s’approprier la récursivité et l’écriture de fonctions récursives.

1. Calculs

a. Afficher les chiffres d’un entier

Soit un entier de valeur 45671, il s’agit d’afficher successivement les caractères 4, 5, 6, 7, 1 et non plus la valeur de l’entier. Pour ce faire, tant que le résultat est supérieur à 0 on prend le modulo 10 qui donne le dernier chiffre, on divise par 10 et on recommence. En itératif cela donne :


void chiffreIter (int val) 
{ 
   while (val>0){ 
       printf("%d_", val%10); 
       val/=10; 
   } 
}

La version récursive est très simple, il suffit de remplacer la boucle par un appel récursif :


void chiffre(int val) 
{ 
   if (val>0){ 
      printf("%d_", val%10); 
      chiffre(val/10); 
   } 
}

b. Produit factoriel

Un produit factoriel c’est : n! = 1*2*3*...*n. La définition est :

n! = 1 si n=0

n! = n(n-1)! si n>0

Il s’agit d’une fonction de récurrence et on boucle sur n tant que n>0, voici une version de fonction itérative :


int factIter (int n) 
{ 
int res=1; 
   while (n>1) 
      res*=n--;  // attention décrémentation après multiplication 
   return res; 
}

D’une certaine façon, la version récursive peut sembler plus facile, plus proche de la définition du calcul. Si n est égal à 0, la fonction retourne 1, sinon la fonction retourne n*(n-1), ce qui donne :


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

Éventuellement l’écriture peut être rendue plus concise avec l’opérateur conditionnel :


int fact(int n) 
{ 
    return n>1 ? n*fact(n-1) : 1; 
}

c. Suite de Fibonacci

Il s’agit d’une suite établie comme suit :

Pour n >= 0

fib(n) = n

fib(n) = fib(n-2) + fib(n-1)

si n = 0 ou n = 1

si n > 1

Par exemple pour les valeurs de 0 à 8 nous avons :

n	0	1	2	3	4	5	6	7	8
fib(n)	0	1	1	2	3	5	8	13	21

Voici une version itérative de la fonction :


int fibIter(int n) 
{ 
int i,res,f1,f2; 
 ...

Mise en pratique : récursivité

Exercice 1

Afficher avec une fonction récursive tous les nombres entre n et n’ entrés par l’utilisateur.

Exercice 2

Qu’impriment les programmes suivants ?


// programme 1 
void f(int n) 
{ 
    if (n>0){ 
        f (n-3); 
        printf("%3d\n",n); 
        f (n-2); 
    } 
} 
 
int main() 
{ 
    f(6); 
    return 0; 
} 
 
// programme 2 
void f(int n) 
{ 
    if (n>0){ 
        f (n/10-100); 
        printf("%3d\n",n); 
        f (n/5-200); 
    } 
} 
int main() 
{ 
    f (10000); 
    return 0; 
}

Exercice 3

Remplacer les fonctions f(), g(), h() ci-après par des variantes itératives équivalentes (plus ou moins). Comparer dans chaque cas la quantité de mémoire utilisée et le temps de calcul nécessaire pour l’une et l’autre des variantes.


void f(void) 
{ 
    if (getchar() == ' ') 
        f (); 
} 
 
void g(int n) 
{ 
    int i; 
    if (n>0){ 
        scanf("%d",&i); 
        g(n-1); 
        printf("%d\n",i); 
    } 
} 
 
int h(int n) 
{ 
    return n<0 ? 0 : (n==0 ? 1 : h(n-1) + h(n-2)); 
}

Exercice 4

Écrire une fonction prenant un argument entier et renvoyant la somme des chiffres décimaux constituant l’argument. Comparer deux variantes de la solution à ce problème, l’une récursive et l’autre itérative.

Exercice 5

Écrire un programme destiné à lire une succession de nombres réels en virgule flottante et afficher la somme des 1^er, 3^e, 6^e, 10^e, 15^e (etc.) éléments de cette suite. Tout caractère non numérique sera interprété comme le signal d’arrêt de cette suite de nombres.

Exercice 6

Écrire un programme destiné à lire un chiffre décimal d. Afficher systématiquement chacun des entiers positifs x inférieurs...

Récursivité