FriconiX
Des milliers de pictogrammes gratuits dessinés avec amour!

Cours 13.1. Fonctions récursives en C

Introduction

La récursivité est une méthode de description d'algorithmes qui permet à une procédure (ou une fonction) de s'appeler elle-même. La fonction fct() ci-dessous s'appelle elle-même :

void fct() {
  ...
  fct();
}

La forme récursive permet généralement l'écriture des fonctions sous une forme concise et plus simple à comprendre. Toutefois, elle peut être moins naturelle à concevoir. Lorsque le problème traité peut se décomposer en une succession de sous-problèmes identiques, la récursivité est généralement bien indiquée.

Exemple

Prenons l'exemple de la fonction factorielle() qui calcule la factorielle d'un entier. On rappelle ici le calcul de la factorielle de \(n\) :

$$ !n = 1 \times 2 \times 3 \times ... \times (n-1) \times n $$

Forme itérative

La forme itérative est l'implémentation classique (sans récursivité). Voici le code de la fonction factorielle() sans récursivité :

int factorielle (int N) {

  int i,fact=1;
  for (i=2;i<=N;i++) fact*=i;  // Parcourt tous les termes et multiplie fact par i
  return fact;
}

Forme récursive

Pour la forme récursive, nous allons nous appuyer sur une autre écriture de la factorielle :

$$ !n = n \times !(n-1) $$

Cette ériture permet l'introduction de la récursivité car elle fait intervenir la factorielle (d'où la récursivité). Voic l'implémentation de la fonction récursive en C :

int factorielle (int N) {

  if (N<=1) return 1;         // Si N <= 1, retourne 1 car !0=1 et !1=1
  return N*Factorielle(N-1);  // Retourne N*!(N-1)
}

La forme récursive est généralement plus simple à comprendre et plus élégante, elle peut être séduisante dans sa conception intellectuelle. Mais les appels récursifs occasionnent la sauvegarde du contexte (les valeurs des variables) avant chaque appel et sa restitution au retour de l'appel, ce qui peut légérement diminuer l'efficacité du programme.

Exercices

Exercice 1

Ecrire une fonction récursive power() qui calcule la puissance de deux nombres: \(a^n\). Le prototype de la fonction est fourni ci-dessous:

double power (double a, unsigned int n);

Le calcul de la puissance peut s'écrire de deux façons :

$$ a^n = a \times a \times a ... a \times a $$

$$ a^n = a \times a^{n-1} $$

La seconde équation permet d'introduire la récursivité. Voici un exemple d'exécution du programme final :

2^8 = 256.00
3^4 = 81.00
1.5^2 = 2.25

Exercice 2

Ecrire une fonction récursive palindrome() qui

int palindrome (const char *phrase, int NbCaract)
Entrez un mot : radar
radar est un palindrome.
Entrez un mot : abracadabrantesque
abracadabrantesque n'est pas un palindrome.

Quiz

Qu'est-ce qu'une fonction récursive ?

Vérifier Bravo ! Essaie encore ...

De manière générale, une fonction récursive est-elle plus rapide que sa version itérative ?

Vérifier Bravo ! Essaie encore ...

À chaque nouvel appel de la fonction récursive, que deviennent les variables locales ?

Vérifier Bravo ! Essaie encore ...

Voir aussi


Dernière mise à jour : 07/11/2020