La récursivité

Avatar de Monsieur X
Description du chapitre et des ses objectifs :

Jusque là nous avons toujours travaillé avec de simples boucles, ce que l'on appelle l'itérativit. Une nouvelle notion va apparaître dans ce chapître, la récursivit qui consiste à ce qu'une fonction s'apelle elle-même pour résoudre des problèmes. Petit chapitre mais gros casse tête!

Image de Partie

Accéder directement à une des parties du cours :

Recursivité, kesako?

Les boucles sont à l'origine de toute automatisation du code en C et permet toute sorte de programmation modulaire afin de faciliter votre travail et éviter des milliers de copier/coller. Cependant, vous n'avez vu que une forme très évidente de boucle, celles dites itératives. Celles-ci s'opposent au boucles récursives qui s'opposent sur la forme avant tout. Le principe de la boucle récursive est de résoudre un problème dans une fonction en l'appellant elle-même!

Question : C'est possible ça?

Bien sûr! (En même temps je ne vous en parlerais pas sinon ) Du moment qu'une fonction a été déclarée, elle peut être utilisée n'importe où. Pour comprendre cela, rien ne vaut un bon viel exemple sur la somme des n premiers entiers:
Code c - Numéro de ligne
  1. int somme_entiers(int n)
  2. {
  3.     if(n == 0)
  4.        return 0;
  5.     return n+somme_entier(n-1);
  6. }


Méchant vous ne trouvez pas? Voyons en détail comment cela fonctionne:
Citation Moi-même :
J'appelle la fonction somme_entiers avec le nombre 4:
--- 4 est différent de 0, je continue;
--- Je retourne 4 plus ce que retourne somme_entier(4-1) (soit somme_entier(3) évidemment)
------- J'appelle la fonction somme_entiers avec le nombre 3
------------ 3 est différent de 0, je continue;
------------ Je retourne 3 plus ce que retourne somme_entier(3-1) (soit somme_entier(2) évidemment)
---------------- J'appelle la fonction somme_entiers avec le nombre 2
--------------------- 2 est différent de 0, je continue;
--------------------- Je retourne 2 plus ce que retourne somme_entier(2-1) (soit somme_entier(1) évidemment)
------------------------- J'appelle la fonction somme_entiers avec le nombre 2
----------------------------- 1 est différent de 0, je continue;
----------------------------- Je retourne 1 plus ce que retourne somme_entier(1-1) (soit somme_entier(0) évidemment)
--------------------------------- J'appelle la fonction somme_entiers avec le nombre 0
------------------------------------- 0 est égal à 0, je retourne 0;
--------------------------------- Fin de la fonction
------------------------------ Je retourne donc 1 + (0) soit 1
-------------------------- Fin de la fonction
--------------------- Je retourne donc 2 + ( 1 + (0) ) soit 3
----------------- Fin de la fonction
------------ Je retourne donc 3 + ( 2 + ( 1 + (0) ) ) soit 6
------- Fin de la fonction
--- Je retourne donc 4 + ( 3 + ( 2 + ( 1 + (0) ) ) ) ) soit 10
Fin de la fonction


Assez long non? Il est important de noter cela: une fonction récursive doit avoir un point de sortie comme la condition d'un while. Ici mon point de sortie est l'évaluation de if(n == 0) qui sort par une valeur fixe: return 0;.
Par contre en comparaison à :
Code c - Numéro de ligne
  1. int somme_entiers(int n)
  2. {
  3.     int resultat=0, i;
  4.     for(i = 0; i < n ; i++)
  5.     {
  6.         resultat += i;
  7.     }
  8.     return resultat;
  9. }
cela semble inutile.

Pourquoi la récursivitée?

Question : Alors pourquoi faire ça? Et quelle est la différence?

Et bien, 2 choses:
- Déjà la taille utilisée ici en terme de variable est énorme dans le cas de la fonction récursive! Imaginez-vous la taille nécessaire pour tenir toutes ces variables en même temps? De plus, les fonctions en elles même prennent elles aussi de la place pour être maintenues en cours de fonctionnement.
- A ceci viens s'ajouter un problème de complexitée, combien faudra-t'il faire d'opérations pour finir notre algorithme. Moins il y en a, mieux c'est. C'est une règle d'or. Dans ce cas, la complexitée est identique. Pour plus d'information sur la complexitée, je vous conseille de vous rapporter au cours de mon collègue sur la programmation en général.

Question : Ca n'explique pas en quoi la récursivitée est utile!

La récursivité est un outil très difficile d'appréciation en règle générale, maisvous verrez des cas où la récursivité vous semblera évidente, au contraire de l'itérativitée. De plus, selon certains cas précis, la récursivité peut faire baisser la complexité d'une fonction (le nombre d'instructions à faire), c'est le cas de certains algorithmes de tri de tableau. Les méthodes utilisées consistent à diviser les choses à effectuer le plus possible. (je sais c'est vague, on dit aussi qu'il faut diviser pour régner, c'est uen façon de voir les choses)

Information : Une règle importante existe, tout problème récursif possède une solution itérative. Mais ce n'est pas forcément pour cela que la complexitée sera moindre de façon itérative. Les fonctions récursives sont d'ailleurs plus efficaces par moment spécifiques

Le point à été fait sur la récursivité, un outil très délicat dans le cas d'une utilisation optimisée. Gardez à l'esprit que tout problème récursif possède une solution itérative, mais que la complexité peut varier du tout au tout. Le prochain chapitre vous attend avec impatience.

Chapitre précédent - Sommaire - Chapitre suivant

Nos rédacteurs et membres sont pour la plupart ouverts à des remarques constructives et servir à alerter le rédacteur du cours, des fautes éventuelles ou de propositions et nouvelles perspectives de cours etc ...
Pour ce faire cliquez ici

Postez vous aussi un commentaire à cette partie via le lien que voici