Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chapitre 6 pdf CHAPITRE LA RECURSIVITE CPlan I Rappels II Une fonction récursive III Concevoir une fonction récursive IV Type de récursivité V Récursivité terminale et non terminale VI Terminaison et correction d ? une fonction récursive VII Complexité d

CHAPITRE LA RECURSIVITE CPlan I Rappels II Une fonction récursive III Concevoir une fonction récursive IV Type de récursivité V Récursivité terminale et non terminale VI Terminaison et correction d ? une fonction récursive VII Complexité d ? une fonction récursive VIII Comparaison entre récursivité et itération IX Conclusion CRappels L'approche e ?cace pour résoudre un problème complexe consiste souvent à le décomposer en plusieurs sous-problèmes plus simples qui seront étudiés séparément D'autre part il arrive souvent qu'une même séquence d'instructions sera utilisée à plusieurs reprises dans un programme et on souhaite évidemment ne pas avoir à la reproduire systématiquement Le concept de la programmation modulaire permet de résoudre les di ?cultés évoquées ci-dessus en utilisant la notion de fonction sous programme Toutes les fonctions qu'on a dé ?nit jusqu ? à maintenant représentent des algorithmes itératifs Une fonction peut appeler une autre fonction Un cas particulier elle peut appeler elle même c'est l'objectif de ce cours CRappels Récurrence en mathématique CFonction récursive La dé ?nition d ? une fonction récursive est plutôt simple c ? est une fonction qui s ? appelle elle-même Exemple le calcul de la factorielle Informatiquement on peut donc dé ?nir la factorielle comme def fact n assert n n doit être positif f for i in range n f f i return f CFonction récursive Une autre dé ?nition mathématique classique de la factorielle se fait par récurrence En reprenant quasiment mot pour mot cette dernière dé ?nition on obtient la fonction Python suivante def factrec n assert n n doit être positif if n return else return n factrec n- CPile d ? exécution Lorsqu ? on fait des appels de fonctions la pile d ? appels de fonctions permet de mémoriser l ? endroit du programme o? la fonction a été appelée avec les paramètres et la valeur de retour Lorsqu ? une fonction a terminé son exécution elle est dépilée Lors de l ? exécution d ? une fonction récursive on appelle la même fonction plusieurs fois ce qui produit plusieurs empilages CTrace d ? exécution de Phase empiler les appels CTrace d ? exécution de Phase empiler les appels CTrace d ? exécution de Phase dépiler les appels CTrace d ? exécution de Phase dépiler les appels CTrace d ? exécution de Phase dépiler les appels CTrace d ? exécution de Phase dépiler les appels CPile d ? exécution On voit que le nombre d ? appels imbriqués réalisés par une fonction récursive est important il faut stocker ces appels ce qui coûte de la mémoire Conclusion L ? exécution d ? un appel récursif passe par deux phases la phase de descente et la phase de remontée Dans la phase de descente chaque appel récursif fait à son tour un appel récursif En arrivant à la condition terminale on commence la phase de remontée qui se poursuit jusqu ? à ce que l ? appel initial soit terminé ce qui termine le processus récursif CPile d ? exécution CConcevoir