DEV 1.1

Récursivité

La définition d'une fonction est autorisée à contenir des appels à elle-même. On dit alors qu'elle est récursive. Cette technique est utile pour mettre en œuvre des concepts mathématiques définis par récurrence, ou pour manipuler des structures récursives (telles que les listes chaînées).

unsigned long factorielle(unsigned char n) {
  return (n < 2) ? 1UL : ((unsigned long) n)*factorielle(n - 1);
}

Dans le cas général, appeler une telle fonction aura pour conséquence d'appeler encore une fois cette fonction. Ceci risque de créer un cercle vicieux qui va accumuler les appels jusqu'à saturer la mémoire. C'est pourquoi une fonction récursive doit toujours comporter un cas de base et un cas récursif.

Le cas de base est une situation si simple que l'exécution de la fonction ne nécessite pas d'appel récursif. Le cas récursif emploie (au moins) un appel récursif pour faire son travail, mais cet appel se fait avec des arguments qui décrivent une situation strictement plus simple à traiter, de sorte que l'enchaînement des appels finisse toujours par retomber sur le cas de base.

Phases. Testez la fonction suivante dans gdb :
```
void exemple(unsigned n) {
  if (n != 0) {
    putchar('>');
    exemple(n-1);
    putchar('<');
  } else
    putchar('O');
}
```
Placez un point d'arrêt sur les trois lignes qui contiennent putchar, lancez le programme, et à chaque fois qu'il atteint un point d'arrêt utlisez la commande bt pour voir la pile des appels. Pouvez-vous identifier les phases ascendantes et descendantes ?
Fibonacci. Écrivez une fonction qui calcule le n-ième terme de la suite de Fibonacci. Vous retrouverez sa définition dans l'énoncé du quatrième exercice du deuxième sujet sur les boucles.

Écrivez ensuite une fonction qui affiche les m premiers termes de la suite, et un programme qui exécute cette fonction avec m valant 15.

Remarque Dans tout cet exercice, aucune forme de boucle n'est permise.
Tableau. Écrivez une fonction qui prend en argument un tableau de réels et affiche ses éléments séparés par une virgule. Employez la récursivité plutôt qu'une boucle.
```
1.25, 47.80, 77.01, 54.23, 895.14
```
Hanoï. Les tours de Hanoï sont un jeu de réflexion où n plateaux de tailles croissantes sont empilés les uns sur les autres pour former une tour. On souhaite déplacer la tour vers un nouveau site mais les plateaux sont trop lourds pour pouvoir en soulever plus d'un à la fois.

On part du principe qu'il y a trois sites possibles pour poser les plateaux : le site de départ, le site d'arrivée, et un site intermédiaire. À chaque tour, on peut déplacer un unique plateau mais il faut obligatoirement prendre un plateau au somment d'une pile, on ne peut le poser qu'au sommet d'une autre pile, et on ne peut pas le poser par dessus un plateau plus petit.

Imaginez comment représenter en mémoire le contenu d'un site. Partant de là, écrivez et testez les fonctions suivantes :
- initialisation des trois sites en configuration de départ,
- affichage en mode graphique des trois sites,
- déplacement (légal) d'un plateau,
- détection de la configuration d'arrivée.
Écrivez maintenant un programme qui permet de jouer aux tours de Hanoï. Le nombre de plateaux sera choisi sur la ligne de commande (entre 1 et 15).
Solution. En vous basant sur les fonctions de l'exercice précédent, écrivez un programme qui prend en argument le nombre de plateaux (compris entre 1 et 15) et qui montre la solution pas à pas (1 déplacement par seconde).

Remarque La solution est bien sûr une fonction récursive.

Développement 1.1 (suite)

Récursivité