Chapitre 1

Rcursivit

1.1 Dnition

La rcursivit est un concept fondamental cl dans l'informatique, c'estune mthode de rsolution de problme qui consiste rduire un problmeen sous-problmes de plus en plus petits jusqu' ce qu'on arrive un petitproblme assez simple qu'il peut tre rsolu trivialement. La rcursivit per-met d'crire des solutions lgantes aux problmes qui pourraient autrementtre trs dicile rsoudre.

En d'autres terme Un algorithme est dit rcursif s'il s'appelle lui-mme,LISP et Algol 60 ont t les premiers langages de programmation qui ontintroduit la rcursivit et maintenant tous les langages de programmationmodernes proposent une implmentation de la rcursivit.

La rcursivit c'est l'application de l'adage Diviser pour rgner l'algorithmique : pour rsoudre un problme d'une taille donne, on scindece problme en plusieurs sous-problmes plus petits, on recommence avecchacun de ces sous-problmes jusqu' ce que tous les petits sous-...-sous-problmes soient facilement rsolubles.

En gnral, les programmes informatiques rcursives ncessitent plus demmoire et de calcul par rapport aux algorithmes itratifs, mais ils sont plussimples et dans de nombreux cas un moyen naturel de rchir au problme.

Exemple Calcul de la somme dans un tableau

On commence par un simple problme qu'on essai de rsoudre la m-thode classique que tous les tudiants connaissent. Supposant qu'on veutcalculer le factoriel d'un nombre. La solution itrative qui calcul le factorielutilise une variable ( fact) pour accumuler la valeur de chaque nombre moins,

1

en commenant par le premier.

Algorithm 1 Solution itrative du factoriel

function factoriel(n : integer) :integerfact : integer ;sum 1 ;for i 1 to n do

fact fact i ;end for

factoriel fact ;end function

Supposant maintenant que nous ne pouvons pas utiliser de boucle pour,tant que ou rpter la question qui se pose : Comment calculer le factoriel d'unnombre ? (exemple factoriel(6) En mathmatique, on peut commencer parrappeler que le factoriel est une fonction qui est dnie pour deux paramtres,le premier est le nombre lui mme et le deuxime le factoriel du nombremoins un. Pour rednir le problme de factoriel au produit, on peut rcrirele factoriel comme une expression entre parenthses. Une telle expressionressemble ceci :

factoriel(6) = (1 (2 (3 (4 (5 6))))

On peut rcrire cette expression d'une autre faon :

factoriel(6) = (6 (5 (4 (3 (2 1)))))

m

factoriel(6) = (6 factoriel(5))factoriel(6) = (6 5 factoriel(4))factoriel(6) = (6 5 4 factoriel(3))factoriel(6) = (6 5 4 3 factoriel(2))factoriel(6) = (6 5 4 32factoriel(1))

Donc le problme a t rduit un simple produit sachant que le factorielde 1 est gale 1. Notant que c'est un problme qu'on peut rsoudre sansboucle ou instructions spciales. En fait, on peut utiliser cette squence desimplications pour calculer le factoriel nale.

Comment peut-on prendre cette ide et la transformer en algorithmique ?Tout d'abord, on va reformuler le problme de factoriel en termes d'algo-rithme. On peut dire que le factoriel d'un nombre peut tre le produit entre

2

Algorithm 2 Solution rcursive du factoriel

1: function factoriel(n : integer): integer2: if n = 1 then3: factoriel 14: else

5: factoriel n factoriel(n 1)6: end if

7: end function

nombre mme et le factoriel du nombre moins un. Pour le dire sous une formefonctionnelle : Factoriel(n) = n factoriel(n 1) Le code de la fonctionfactoriel deviendra comme suit :

Il y a quelques ides cls dans ce code qu'on peut voir. Tout d'abord,sur la ligne 2, on vrie si le nombre est gale un. Cette vrication estcruciale et essentielle pour sortir de la fonction. Le factoriel de 1 est trivial ;la fonction retourne 1. Deuximement, sur la ligne 5 la fonction fonctionfactoriel s'appelle elle mme ! pour cette raison on appel la fonction factoriellercursive. Une fonction rcursive est une fonction qui s'appelle elle mme. Lagure 1.1 montre la srie d'appels rcursifs qui sont ncessaires pour calculerle factoriel. Cette srie d'appels est vue comme une srie de simplications.Chaque fois qu'on fait un appel rcursif on rsout un problme plus petit,jusqu' ce qu'on atteigne le point o le problme ne peut pas devenir pluspetit.

Lorsqu'on atteint le point o le problme est aussi simple que cela peutl'tre, on commence reconstituer les solutions de chacun des petits pro-blmes jusqu' ce que le problme initial est rsolu. La gure 1.1 montre lesproduits qui sont eectues que la fonction factoriel travaille son chemin versl'arrire dans la srie d'appels. Lorsque factoriel revient au plus haut, on ala solution l'ensemble du problme.

1.2 Les trois rgles de la rcursivit

Pour une meilleur utilisation de la rcursivit en algorithmique et en pro-grammation, les algorithmes rcursifs doivent obir trois lois importantes :

1. Un algorithme rcursif doit avoir un cas de base.

2. Un algorithme rcursif doit changer son tat et de progresser vers lecas de base.

3

factoriel(4) 4x

factoriel (3) 3 x

factoriel (2) 2 x

factoriel (1) 1 x

=

=

=

=

factoriel (0) 1=

Figure 1.1 Sries d'appels rcursifs factoriel(4)

3. Un algorithme rcursif doit se appeler, de manire rcursive.

Vriant chacun de ces lois plus en dtail et voir comment il a t utilisdans l'algorithme de factoriel. Tout d'abord, un cas de base est la conditionqui permet l'algorithme pour arrter rcursivit. Un scnario de base esttypiquement un problme qui est assez petit pour rsoudre directement. Dansl'algorithme du factoriel le cas de base est le factoriel de 1 qui gale 1.

Pour obir la deuxime loi, on devra prendre des dispositions pour unchangement d'tat qui se dplace vers le cas de base. Un changement d'tatsignie que certaines donnes que l'algorithme utilise est modi. Habituel-lement les donnes que reprsente notre problme devient de plus en pluspetit. Dans l'algorithme de factoriel la structure de donnes primaire est unefonction, donc on devra se concentrer sur le changement d'tat. Depuis le casde base qui est gale 1, une progression naturelle vers le scnario de baseest de raccourcir la fonction. C'est exactement ce qui se passe sur la ligne 5de 1 lorsqu'on appel factoriel avec le nombre suivant (n 1).

La troisime rgle est que l'algorithme doit s'appeler lui mme. C'estla mme dnition de la rcursivit. La rcursivit est un concept drou-tant pour de nombreux programmeurs dbutants. En tant que program-meur novice, vous avez appris que les fonctions sont bon parce que vouspouvez prendre un grand problme et le rduire en petits problmes (sous-problmes). Les sous-problmes peuvent tre rsolus en crivant une fonction

4

factoriel(4) 4x 6

factoriel (3) 3 x 2

factoriel (2) 2 x 1

factoriel (1) 1 x 1

==

=

=

24

factoriel (0) 1=

=

Figure 1.2 Sries de retours rcursifs factoriel(4) par produit

pour rsoudre chaque problme. Nous avons un problme rsoudre avecune fonction, mais cette fonction rsout le problme en se faisant appeler !Mais la logique n'est pas circulaire du tout ; la logique de la rcursivit estune expression lgante de rsoudre un problme en le dcomposant en desproblmes plus petits et plus faciles rsoudre.

1.3 Solution rcursive vs itrative

Pour mettre en uvre des algorithmes rcursifs ncessite le plus sou-vent une pile. Vue la dicult d'implanter cette pile qui a fait dire pendantlongtemps que les programmes rcursifs taient moins ecaces que les pro-grammes itratifs, mais la situation a chang. En fait, le dbat sur le choixentre la rcursivit ou l'itratif est aussi vieux que l'informatique et les pro-grs des compilateurs rduit encore la dirence d'ecacit. Voici quelquesarguments en faveur de la rcursivit :

La rcursion permet de prsenter simplement des algorithmes beau-coup plus astucieux (et donc plus ecaces) (exemple l'algorithme detri rapide).

Les compilateurs d'aujourd'hui sont tellement astucieux que plus leprogramme leur est prsent de faon abstraite et sans eets de bord,plus ils peuvent mettre en uvre leurs optimisations et aboutir descodes objets ecaces.

5

Des structures de donnes rcursives, comme par exemple les quadtrees,ont t conues pour leur ecacit. On ne voit pas comment on pourraitexcuter sur elles des algorithmes non rcursifs.

1.4 Structure de donnes rcursive

Une structure de donne rcursive S est une structure qui se compose ellemme d'une structure de donne S ou si l'un de ses composantes est unestructure de donne faisant appel S. Parmi structure de donnes rcursivesvont tre expos dans les prochains chapitres, nous verrons les listes, les piles,les le et les arbres.

Exercices

Suite de Fibonacci

La suite de Fibonacci est une suite d'entiers (un)n > 0 dnit par :u0 = 0

u1 = 1

un = un1 + un2 \ n > 2 Vrier que cette suite vrie bien les rgles de la rcursivit. crire la fonction fib qui calcul le nime terme fib(n) de faon itrative puisrcursive.

Tracer b(4), Combien d'appel rcursive gnre t'il ? Combien au maxd'appels imbriqus ?

L'algorithme est-il terminal ? Justiez la rponse.

6