Algorithmique Complexe Récursivité Définition:
La récursivité consiste à écrire les instructions nécessaires à la résolution d'un problème en utilisant l'algorithme du même problème sur des valeurs plus
petites.
Une procédure récursive est une procédure qui s'auto-appelle!!
Principe:
Une procédure récursive comporte un bloc terminal ou bloc d’arrêt.
Utilisation de la pile :
Une "pile" est une zone mémoire réservée à chaque programme. Son rôle est de stocker les variables locales et les paramètres d'une procédure.
Exemple: Calcul du factoriel de a.
Exercices:
Suite de Fibonacci:
La suite de Fibonacci est définit par :
Ecrire une procédure
récursive qui permet de faire le calcul.
Le but du jeu est de déplacer n disques, initialement empilés sur une tour, vers une autre tour.
Condition : un disque n’est déposé que si la tour est vide ou si il est plus petit que le disque précédemment déposé.
Un arbre binaire localement complet de taille n aura n+1 feuille.
Cet arbre est donc tout simplement une liste chaînée.
Dans ce cas :
n=2^(h+1)-1
n : nombre de noeud.
h : hauteur.
Tour de HANOÏ:
Condition : un disque n’est déposé que si la tour est vide ou si il est plus petit que le disque précédemment déposé.
Analyse du problème:
Méthode : déplacer les n-1 disques vers la tour 2, déplacer le disque n vers la tour 3 et puis déplacer les n-1 vers la tour 3.
Si on peut faire cette tâche pour n-1 on le peut pour n.
Arbres:
Un arbre est une structure de données qui peut se définir de façon récursive.
Un arbre possède des pointeurs vers d’autres arbres.
Arbres enracinées :
On distingue généralement entre deux type d’arbres :
◦Arbres enracinés : un arbre hiérarchique dans lequel on peut établir des niveaux.
◦Arbres non enracinés : pas de relation d’ordre ou de hiérarchie.
Terminologie :
◦Chaque élément d'un arbre se nomme un noeud.
◦Les noeuds sont reliés les uns aux autres par des relations d'ordre ou de hiérarchie.
◦Un noeud possède un père.
◦Il possède éventuellement un ou plusieurs fils.
Arité d’un arbre :
L’arité qualifie le nombre de fils maximum que peut avoir un noeud, si arité=n;on parle dans ce cas d’un arbre n-aire.
Cas particulier : l’arbre binaire.
Taille d’un arbre :
La taille d'un arbre est le nombre de noeud interne qui le compose, c.-à-d. tous les noeuds sauf les feuilles.
Profondeur d’un arbre :
C’est la distance en terme de noeud par rapport à l'origine, la racine est de profondeur 0.
Exemple :
La hauteur d’un arbre ?
Profondeur max d’un arbre!!
Arbre localement complet :
Un arbre binaire localement complet est un arbre binaire dont chacun des noeuds possèdent soit 0 soit 2 fils.Un arbre binaire localement complet de taille n aura n+1 feuille.
Arbre dégénéré :
Appelé aussi filiforme est un arbre dont les noeuds ne possède qu'un et un seul fils.
Arbre binaire complet :
C’est un arbre qui est localement complet et dont toutes les feuilles ont la même profondeur.Dans ce cas :
n=2^(h+1)-1
n : nombre de noeud.
h : hauteur.
A suivre...!!!
