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 écriture 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.

Tester l'exemple en ligne

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

Faire l'exercice

Solution

Exercice 2

Ecrire une fonction récursive palindrome() qui

retourne vrai si le mot passé en paramètre est un palindrome
et faux sinon. On supposera ici que la chaîne de caractères ne contient pas d'espaces. Le prototype est donné ci-dessous :

int palindrome (const char *phrase, int NbCaract)

phrase pointe vers la chaîne de caractères à tester.
NbCaract est la longueur de la chaine à tester.

Entrez un mot : radar
radar est un palindrome.

Entrez un mot : abracadabrantesque
abracadabrantesque n'est pas un palindrome.

Faire l'exercice

Solution

Quiz

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

une fonction qui contient une boucle

une fonction qui appelle une autre fonction

une fonction qui s'appelle elle-mème

une fonction qui ne se termine jamais

Vérifier

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

beaucoup plus lente

légérement plus lente

légérement plus rapide

beaucoup plus rapide

Vérifier

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

elles sont sauvegardées sur la pile

c'est ce que l'on appelle la sauvegarde du contexte

elles sont perdues (la mémoire est libérée)

elles sont conservées que si elles sont statiques

Vérifier

Cours 12.4 Sommaire Cours 13.2

Voir aussi

Dernière mise à jour : 23/11/2022