Récursivité pratique
Plus qu'un simple casse-tête, les fonctions récursives sont un outil qui peut devenir indispensable dans la résolution de certains problèmes de développement. Notamment, elles permettent de grandement simplifier et accélérer un développement qui aurait demandé beaucoup plus de travail s'il avait adopté l'approche itérative. Par exemple, notre routine de factorielle ci-dessous donnerait en itératif:

function fact(x)
  {
  result = 1;
  while( x > 1)
    {
    result = result * x;
    x--;
    }
  return result;
  }

Ce n'est certes guère plus long que la manière récursive, mais c'est surtout considéré comme moins "élégant" dans le cas présent. D'autres cas existent où l'élégance n'est plus de mise, mais l'efficacité. Nombre de problèmes sont résolus en appliquant directement la récursivité, et seraient insolvables (ou difficilement solvable) sans.

Par exemple, la méthode de tri récursif QuickSort est proportionnellement efficace au désordre du tableau à trier. Cela implique, paradoxalement, que cette méthode mettra plus de temps à trier un tableau qui est déjà en parti "rangé" (ou, pire, déjà trié) qu'un tableau rangé au hasard... Mais en cas de désordre intégral, c'est certainement la plus rapide.
Pour simplifier, QuickSort fonctionne en choisissant (au hasard ou non) un point central, ou "pivot", qui est sensé être correctement placé par rapport au tri final. Puis QuickSort est réappliqué aux deux "portions" du tableau séparées par le pivot: on place dans chacun un pivot, et ainsi de suite... A chaque fois, un "tri" est fait: on place d'un coté les éléments inférieurs au pivot, et de l'autre les éléments supérieurs. Au final, on obtient un tableau parfaitement trié.

Autre exemple: le plan du métro. Pour trouver le parcours le plus efficace entre deux stations de métro, c'est la récursivité qui est utilisée: elle permet de parcourir tous les chemins possibles partant d'une station donnée, et de trouver le plus court pour une autre station, en éliminant les chemins qui n'y mènent pas, ceux qui présentent trop de changements et ceux prennent trop de stations pour arriver à destination.

La récursivité permet aussi d'étudier les théories du Chaos... auquel cas on retombe dans le casse-tête.

Les applications sont quasi illimitées: la récursivité est un outil essentiel pour le développeur.

Guide pratique
Lors de la construction de votre fonction récursive, vous devez vous assurez que ces points sont observés:
- la fonction doit être définie de manière conditionnelle: quand elle est appelée, il doit y avoir une vérification de la/des condition(s) d'arrêt. Si elle(s) est/sont satisfaite(s), la récursivité doit s'arrêter.
- au moins l'un des cas de l'expression conditionnelle doit mener à une expression évaluable sans appel récursif.
- chaque fois qu'elle est appelée de manière récursive (par elle-même, donc), un ou plusieurs des arguments qui lui sont transmis doivent se rapprocher de la condition d'arrêt.
- le nombre d'appel récursif pour parvenir à un résultat doit être fini (s'il était infini, on aurait alors une boucle sans fin).
- enfin, et c'est probablement le point le plus important: dans une fonction récursive, la complexité du problème doit être réduite à chaque nouvel appel récursif.

Nous aurons l'occasion prochainement de voir de manière plus complète des applications de la récursivité...

Page 1 | 2