Vous savez comment sont les informaticiens : on ne peut pas leur donner quoi que ce soit sans qu’ils essayent de jouer avec, et le pire, c’est qu’ils y réussissent.
La programmation des fonctions personnalisées a donné lieu à l'essor d’une logique un peu particulière, adaptée en particulier au traitement de certains problèmes mathématiques (ou de jeux) : la programmation récursive. Pour vous expliquer de quoi il retourne, nous allons reprendre un exemple cher à vos cœurs : le calcul d’une factorielle (là, je sentais que j’allais encore me faire des copains).
Rappelez-vous : la formule de calcul de la factorielle d’un nombre n s’écrit :
N ! = 1 x 2 x 3 x … x n
Nous avions programmé cela aussi sec avec une boucle Pour, et roule Raoul. Mais une autre manière de voir les choses, ni plus juste, ni moins juste, serait de dire que quel que soit le nombre n :
n ! = n x (n-1) !
En bon français : la factorielle d’un nombre, c’est ce nombre multiplié par la factorielle du nombre précédent. Encore une fois, c’est une manière ni plus juste ni moins juste de présenter les choses ; c’est simplement une manière différente.
Si l’on doit programmer cela, on peut alors imaginer une fonction Fact, chargée de calculer la factorielle. Cette fonction effectue la multiplication du nombre passé en argument par la factorielle du nombre précédent. Et cette factorielle du nombre précédent va bien entendu être elle-même calculée par la fonction Fact.
Autrement dit, on va créer une fonction qui pour fournir son résultat, va s’appeler elle-même un certain nombre de fois. C’est cela, la récursivité.
Toutefois, il nous manque une chose pour finir : quand ces auto-appels de la fonction Fact vont-ils s’arrêter ? Cela n’aura-t-il donc jamais de fin ? Si, bien sûr, rassure-toi, ô public, la récursivité, ce n’est pas Les Feux de L’Amour. On s’arrête quand on arrive au nombre 1, pour lequel la factorielle est par définition 1.
Cela produit l’écriture suivante, un peu déconcertante certes, mais parfois très pratique :
Fonction Fact (N en Numérique)
Si N = 0 alors
Renvoyer 1
Sinon
Renvoyer Fact(N-1) * N
Finsi
Fin Fonction
Vous remarquerez que le processus récursif remplace en quelque sorte la boucle, c’est-à-dire un processus itératif. Et en plus, avec tous ces nouveaux mots qui riment, vous allez pouvoir écrire de très chouettes poèmes. Vous remarquerez aussi qu’on traite le problème à l’envers : on part du nombre, et on remonte à rebours jusqu’à 1 pour pouvoir calculer la factorielle. Cet effet de rebours est caractéristique de la programmation récursive.
Pour conclure sur la récursivité, trois remarques fondamentales.
la programmation récursive, pour traiter certains problèmes, est très économique pour le programmeur ; elle permet de faire les choses correctement, en très peu d'instructions.
en revanche, elle est très dispendieuse de ressources machine. Car à l’exécution, la machine va être obligée de créer autant de variables temporaires que de « tours » de fonction en attente.
Last but not least, et c’est le gag final, tout problème formulé en termes récursifs peut également être formulé en termes itératifs ! Donc, si la programmation récursive peut faciliter la vie du programmeur, elle n’est jamais indispensable. Mais ça me faisait tant plaisir de vous en parler que je n’ai pas pu résister… Et puis, accessoirement, même si on ne s'en sert pas, en tant qu'informaticien, il faut connaître cette technique sur laquelle on peut toujours tomber un jour ou l'autre
Mer 13 Fév - 9:52