Remerciez-le!

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

Algorithme et programmation structure la recursivite

Algorithme et programmation structure La recursivite CPlan Récursivité et récurrence Dé ?nitions principe Un peu de vocabulaire Exemple Comment ca marche Notion de pile d ? exécution La récursivité terminale Les pièges a éviter Pourquoi ca marche CRécursivité et récurrence Deux notions tres proche o Mathematiques recurrence o Informatique recursivite De nombreuses dé ?nitions mathématiques sont récursives De ?nition Peano ? est un entire naturel ? Si n est un entier alors n est un entier CDe ?nition et principes De ?nition On appellee recursivite toute function ou procedure qui s ? appelle elle meme Principes Tout objet est dit recursif s ? il se de ?nit a partir de lui meme Une function est dite recursive si elle comporte dans son corps au moins un appel a elle-meme Un structure est recursive si un de ses attributs en est une autre instance CUn peu de vocabulaire Pour une fonction recursive on parlera De recursivite terminale si aucune instruction n ? est executee apres l ? appel de la fonction a elle-meme Recursivite terminale void f int n if n Console WriteLine ??Hello ? else f n- De recursivite non terminale dans l ? autre cas Recursivite non terminale void f int n if n f n- Console WriteLine ??Hello World ? De recursivite directe lorsque la fonction s ? appelle elle-meme De recursivite indirecte lorsque f appelle g qui appelle f CExemple Le calcul de la factorielle peut se faire de façon récursive Algorithme Fact Entree un entier positif N Sortie factorielle de N si N retourner sinon retourner N ? Fact N- public static unsigned int fact unsigned int N if N return else return N fact N- C CComment ca marche CNotion de pile d ? execution Dé ?nition Pile d ? exécution La Pile d ? exécution du programme en cours est un emplacement mémoire destiner à mémoriser les paramètres les variables locales ainsi que les adresses de retour des fonctions en cours d ? exécution Elle fonctionne selon le principe LIFO Last- In-First-Out dernier entre premier sorti Attention La pile a une taille ?xee une mauvaise utilization de la recursivite peut entrainer un debordement de pile CRecursivite terminale Rappel une récursivité est dite terminale s ? il y ? a plus d ? instructions après l ? appel a la fonction Autrement dit la valeur retournee est directement la valeur obtenue par un appel recursif sans qu ? il n ? y ait aucune operation sur cette valeur Retenir Quand une function est recursive terminale on peut transformer l ? appellee recursif en une boucle sans utilization de memoire supplementaire si n retourner a sinon retourner Algo n- n a devient Tantque n a - n a n - n- Retourner a CLes pièges a éviter Pour programmer une fonction recursive il su ?t de la faire s ? appeler elle-meme int f int n return f n- La fonction f est-elle recursive La fonction f est-elle correcte la condition terminale la terminaison de la