Toutes les listes multiplicatives avec terminaison n
Recherche dichotomique
recherche d'un parcours de l'échiquier par un cavalier
Eviter les effets de bord (mais aussi les copies coûteuses)!
STRUCTURES RECURSIVES
Définition de structures qui contiennent des pointeurs vers
d'autres structures du même type
listes
arbres
avec sous-arbres en commun
et boucles
souvent traitées par des fonctions/procédures récursives
STRUCTURES RECURSIVES en Exalgo
Nouveaux types introduits par définitions type id : ^ type_id;
pour un pointeur ou type id : enreg id,id,id:type;... finenreg;
pour enregistrements
Pour le type d'un enregistrement qui contient un pointeur au même type
il faut avoir deux définitions mutuellement récursives (le pointeur et
l´enregistrement)
Recommandé de définir d'abord le type pointeur et (immédiatement) ensuite
l'enregistrement
exemple d'une liste:
type p:^S;
type S: enreg
valeur:entier;
reste: p
finenreg;
Les listes
longueur
somme
concaténer
fusionner deux listes triées
insérer: choisir le bon mode de passage de paramètres
pour pouvoir insérer au début
listes.exo
Les arbres (binaires)
Les trois ordres de parcours
préfixe, symétrique, postfixe
tous programmés de façon très simple est claire par récursion
arb-bin-rec.exo
Parcours en largeur d'un arbre
Pas de solution simple récursive ou autre
liste (FIFO) de noeuds en attente d'être traité
Extraire un noeud, traiter le, ajouter ses successeurs
terminer quand la liste est vide
largeur.exo
Parcours en largeur de structures plus complexes
Eviter les boucles
Prévoir un champs qui pourra être utilisé comme marqueur des noeuds
déjà visités
ne rien faire si un noeud est déjà marqué
marquer un noeud AVANT de visiter ses successeurs
(evite aussi de parcourir plusieurs fois la même sous-structure)
remettre les marqueurs à 0 (faux) à la fin??
FONCTIONS PURES
Théorie selon laquelle les fonctions écrites sans affectations et effets de bord
sont plus claires et plus facilement écrites sans bugs
plus proche de l'idée mathématique d'une fonction; et les définitions ressemblent
à des équations
Une question de goût
mais récursion nécessaire pour ce style de programmation
QUAND DOIT ON UTILISER LA RÉCURSION?
Quels sont les fonctions pour lesquelles récursion est essentielle?
Aucunes: ce qu'on peut faire avec récursion, on peut toujours faire
avec une pile explicite!
Jeux de parcourir un arbre sans récursion et sans pile!!
QUAND DEVRAIT ON L'UTILISER?
Quand le code est plus simple à écrire et comprendre avec récursion
Dont presque tous les cas où l'alternative serait une pile explicite
Mais si je veux parcourir deux arbres en même temps (par exemple
je veux les fusionner), je ne peux pas forcément le faire récursivement
(mais ``coroutines'' récursives existent en certains langages)
LE COUT
Espace: negligeable:
nécessité de stocker les paramètres et variables locales de chaque appel
(activation); utilisation invisible d'une pile; sauf très gros tableaux,
cet espace n'est pas important
Temps: negligeable:
les instructions supplémentaires exécutées à chaque appel d'une fonction
prennent un temps petit par rapport aux calculs de la fonction sauf si ces
calculs sont simples
La qualité du programme est plus importante
et un bon compilateur peut quelquefois générer le même code pour les deux
versions (cas de récursion à la fin)
File translated from
TEX
by
TTH,
version 3.05. On 18 Oct 2006, 09:16.