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 Plan ◦Récursivité et récur

Algorithme et programmation structure La recursivite Plan ◦Récursivité et récurrence ◦Définitions / 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 ? Récursivité et récurrence Deux notions tres proche : o Mathematiques : recurrence o Informatique : recursivite De nombreuses définitions mathématiques sont récursives : Definition (Peano) 0 est un entire naturel. Si n est un entier, alors n+1 est un entier Definition et principes Definition On appellee recursivite toute function ou procedure qui s’appelle elle meme. Principes Tout objet est dit recursif s’il se definit 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 Un 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 ◦De recursivite non terminale dans l’autre cas ◦De recursivite directe lorsque la fonction s’appelle elle-meme ◦De recursivite indirecte lorsque f appelle g qui appelle f. Recursivite non terminale void f(int n) { if(n > 0) f(n-1); Console.WriteLine(“Hello World”); Recursivite terminale void f(int n) { if (n == 0) Console.WriteLine(“Hello”); else f(n-1); Exemple 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 = 0 retourner 1 sinon retourner N × Fact(N-1) public static unsigned int fact(unsigned int N) { if ( N == 0) return 1; else return N * fact(N-1); } C# Comment ca marche ? Notion de pile d’execution Définition (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 fixee, une mauvaise utilization de la recursivite peut entrainer un debordement de pile. Recursivite 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 == 0 retourner a sinon retournerAlgo(n-1, n*a) devient Tantque n <> 0 a <- n *a; n <- n-1; Retourner a; Les pièges a éviter Pour programmer une fonction recursive, il suffit de la faire s’appeler elle-meme int f(int n) { return f(n-1); } ◦La fonction f est-elle recursive ? ◦La fonction f est-elle correcte ? ◦1. la condition terminale ◦2. la terminaison de la fonction ◦une solution Theoreme de Godel Il n’existe pas de moyen automatique pour savoir si un programme termine ou pas. uploads/Ingenierie_Lourd/ algorithme-et-programmation-structure-la-recursivite.pdf