Sous-programmes récursifs

Un sous-programme récursif est un sous-programme qui s'appelle lui-même. Par exemple :

Ce sous-programme affiche $n$ si celui-ci est positif ou nul, puis se rappelle en passant $n-1$ en paramètre. Il va se rappeler jusqu'à ce que le paramètre prenne la valeur $-1$, affichant ainsi un compte à rebours dont la dernière valeur affichée sera $0$. Lorsque qu'un sous-programme se rappelle, on dit qu'il effectue un appel récursif. Pour observer ce que cela fait, considérez le programme suivant :

#include<stdio.h>

void countDown(int n)
{
  if (n >= 0)
    {
      printf("%d\n", n);
      countDown(n-1);
    }
}

int main()
{
  countDown(10);
  return 0;
}

Il affiche

10
9
8
7
6
5
4
3
2
1
0

Observons bien la procédure $countdown$ :

• La première chose faite est le test $n \geq 0$, il faut toujours tester la condition d'arrêt avant de faire quoi que ce soit. Si cela n'est pas fait correctement, le sous-programme peut boucler indéfiniment.
• Dans l'appel récursif, la valeur $n-1$, et non pas $n$, est passée en paramètre. Si vous ne faites pas décroître la valeur de $n$, le sous-programme se comportera de façon identique à chaque appel récursif, donc bouclera.
• L'appel récursif est fait après l'affichage de $n$, si vous permutez l'affichage et l'appel récursif, les nombres seront affichés dans l'ordre croissant. un sous-programme est récursif terminal si la dernière instruction exécutée est un appel récursif, ce qui est le cas ici.

Beaucoup de sous-programmes sont beaucoup plus faciles à implémenter de façon récursive. Un sous-programme utilisant des boucles mais pas la récursivité est dit itératif. Comme la récursivité permet d'éviter de faire des boucles, on oppose souvent la mode récursif au mode itératif. On exposera divers algorithmes s'implémentant naturellement de façon récursive, notamment le tri fusion, et les algorithmes dans les listes et les arbres. Pour le moment nous nous limiterons au calcul de valeurs définies par récurrence.