Cours algorithmes et structures de données génériques, tutoriel & résumé algorithme en pdf.

RÉCURSIVITÉ DES PROCÉDURES : DÉFINITION

La récursivité est une méthode de description d’algorithmes qui permet à une procédure de s’appeler elle-même (directement ou indirectement). Une notion est récursive si elle se contient elle-même en partie, ou si elle est partiellement définie à partir d’elle-même. L’expression d’algorithmes sous forme récursive permet des descriptions concises et naturelles. Le principe est d’utiliser, pour décrire l’algorithme sur une donnée jusqu’à ce que le traitement puisse s’effectuer sans nouvelle décomposition. Dans une procédure récursive, il y a deux notions à retenir : • la procédure s’appelle elle-même : on recommence avec de nouvelles données. • il y a un test de fin : dans ce cas, il n’y a pas d’appel récursif. Il est souvent préférable d’indiquer le test de fin des appels récursifs en début de procédure.Ainsi, si on dispose des fonctions void avancer (int lg) ;qui trace un segment de longueur lg sur l’écran dans la direction de départ, et de la fonction void tourner (int d) ;qui change la direction de départ d’un angle de d degrés.

Exemple  :

Tours de Hanoi Les « Tours de Hanoi » est un jeu où il s’agit de déplacer un par un des disques superposés de diamètre décroissant d’un socle de départ D sur un socle de but B, en utilisant éventuellement un socle intermédiaire I. Un disque ne peut se trouver au dessus d’un disque plus petit que lui. Le schéma de la Figure 6 montre le raisonnement mettant en évidence le caractère récursif de l’algorithme à suivre. Pour déplacer un disque de D vers B, le socle I (intermédiaire) est inutile. Pour déplacer 2 disques, il faut transférer celui qui est au sommet sur le socle I, déplacer le disque reposant sur le socle D vers B, et ramener le disque du socle I au sommet de B. Pour déplacer 3 disques, il faut déplacer les 2 disques en sommet de D vers I (en utilisant B comme intermédiaire), ensuite déplacer le disque reposant sur le socle de D vers B, et ramener les 2 disques mis de côté sur I, en sommet de B. Pour déplacer 3 disques, on utilise 2 fois la méthode permettant de déplacer 2 disques sans entrer dans le détail de ces mouvements, ce qui met en évidence la récursivité.

………