Structure de données – Récursivité, pointeurs, modules

Récursivité Pointeurs Modules

Structure de données – Récursivité, pointeurs, modules

Table des matières :
1 La récursivité …………………………………………………………………………………………. 3 1.1 Définition………………………………………………………………………………………… 3 1.2 Exemples de fonctions récursives ………………………………………………………. 4 1.2.1 Exemple : factorielle…………………………………………………………………… 4 1.2.2 Exercice 1 : Boucles récursives …………………………………………………… 6 1.2.3 Exercice 2 : Numération……………………………………………………………… 6 1.2.4 Exercice 3 : Tours de Hanoi ………………………………………………………… 6 2 La récursivité des objets………………………………………………………………………….. 9 2.1 Rappel sur les structures…………………………………………………………………… 9 2.2 Exemple de déclaration incorrecte……………………………………………………… 9 2.3 Structures et pointeurs ……………………………………………………………………. 10 2.4 Opérations sur les pointeurs ……………………………………………………………. 13 2.4.1 Création dynamique d’un objet…………………………………………………… 13 2.4.2Affectation de pointeurs ……………………………………………………………. 13 2.4.3 Affectation de zones pointées ……………………………………………………. 13 2.4.4 Comparaison de pointeurs (== et !=)…………………………………………… 13 2.4.5 Accès à l’élément pointé …………………………………………………………… 14 2.4.6Suppression de la zone allouée dynamiquement………………………….. 14 2.4.7 Addition, soustraction de pointeurs …………………………………………….. 14 3 Les Modules ………………………………………………………………………………………… 15 3.1 Pourquoi des modules ?…………………………………………………………………..15 3.2 Exemple : module de simulation d’écran graphique …………………………….. 16 3.2.1 Le fichier d’en-tête de l’écran graphique ……………………………………… 16 3.2.2 Le module écran graphique……………………………………………………….. 17 3.2.3 Programme d’application de l’écran graphique …………………………….. 19 3.2.4 Le résultatde l’exécution du test du module écran ……………………….. 20 3.2.5 Exercice 4 – Spirale rectangulaire (récursive)……………………………….. 21 3.2.6 Exercice 5 – Module de gestion de piles d’entiers (allocation contiguë) 22 4 Conclusion…………………………………………………………………………………………… 24

Techniciens 2eme année

Page2 sur 24

Structure de données – Récursivité, pointeurs, modules

1 La récursivité
1.1 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). Cette notion très utilisée en programmation car elle permet l’expression d’algorithmes concis, faciles à écrire et à comprendre. Dans une procédureré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.

void p (…) { if (fin) { … } else { … p (…); … } }

pas d’appel récursif (partie « alors »)

la…