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: LA RECURSIVITE Plan I. Rappels II. Une fonction récursive III. Conc

CHAPITRE 6: LA RECURSIVITE Plan 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 Rappels L'approche efficace 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 difficultés évoquées ci-dessus en utilisant la notion de fonction (sous programme). Toutes les fonctions qu'on a définit 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. Rappels Récurrence en mathématique: Fonction récursive La définition d’une fonction récursive est plutôt simple : c’est une fonction qui s’appelle elle-même. Exemple 1 : le calcul de la factorielle. Informatiquement, on peut donc définir la factorielle comme : def fact(n): assert n>=0, "n doit être positif" f=1 for i in range(1,n+1): f=f*i return(f) Fonction récursive Une autre définition mathématique classique de la factorielle se fait par récurrence : En reprenant quasiment mot pour mot cette dernière définition, on obtient la fonction Python suivante : def fact_rec(n): assert n>=0, "n doit être positif" if n==0: return(1) else: return(n*fact_rec(n-1)) Pile 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 : Trace d’exécution de 3! Phase 1: empiler les appels Trace d’exécution de 3! Phase 1: empiler les appels Trace d’exécution de 3! Phase 2: dépiler les appels Trace d’exécution de 3! Phase 2: dépiler les appels Trace d’exécution de 3! Phase 2: dépiler les appels Trace d’exécution de 3! Phase 2: dépiler les appels Pile 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. Pile d’exécution Concevoir une fonction récursive La conception d’une fonction récursive n’est pas éloignée du principe de démonstration par récurrence. On peut définir une fonction f prenant en argument un entier naturel n en se ramenant au calcul de f(0) d’une part et de f(n) en fonction de f(n-1) d’autre part. La fonction f prend alors la forme suivante : def f(n): if n == 0: return ... else: return ... f(n-1) ... Note : il est impératif de prévoir une condition d’arrêt à la récursion. Concevoir une fonction récursive Exemple: Type de récursivité Récursivité simple Type de récursivité Récursivité multiple Type de récursivité Récursivité croisée Type de récursivité Récursivité imbriquée Récursivité terminale et non terminale Une fonction récursive est dite terminale si aucun traitement n'est effectué à la remontée d'un appel récursif (sauf le retour d'une valeur). Une fonction récursive est dite non terminale si le résultat de l'appel récursif est utilisé pour réaliser un traitement (en plus du retour d'une valeur). Exemple : def fact_rec(n): assert n>=0, "n doit être positif" if n==0: return(1) else: return(n*fact(n-1))  la valeur renvoyée est le résultat d’une multiplication par n de l’appel récursif, ce n’est pas une récursivité terminale : l’entier n va être stocké dans la pile dans l’attente du calcul de (n-1) !, … et le résultat final sera obtenu en effectuant les différents produits lors du dépilement de la pile d’exécution. Récursivité terminale et non terminale On propose un code récursif terminal du calcul de n ! qui repose sur la remarque suivante : si f(m,n)=m*n! alors f(m,n)=f(nm,n-1) alors on obtiendra le résultat attendu en calculant f(1,n): def fact_rec_term(m,n) : if n==0: return m else: return fact_rec_term(n*m,n-1) def fact(n): return fact_rec_term(1,n) dans ce genre d’algorithme, aucun calcul n’est fait à la remontée, ce qui entraîne un gain de temps. N.B :En général, la transformation d’un algorithme récursif non terminal en un algorithme récursif terminal se fait par l’utilisation d’une fonction auxiliaire qui comporte au moins un paramètre de plus. Terminaison et correction d’une fonction récursive Terminaison Pour montrer la terminaison d’une fonction récursive, il suffit d’exhiber une fonction des paramètres à valeurs entières, telle que les valeurs prises par la fonction décroissent strictement au cours des appels récursifs successifs. Correction Pour prouver la correction d’une fonction récursive, on procède en général par récurrence : on prouve d’abord que la sortie de la fonction est correcte pour les cas terminaux, ce qui correspond à l’initialisation de la récurrence, et on montre ensuite que les appels récursifs se ramènent à des instances plus petites (dans le même sens que la terminaison), ce qui constitue l’hérédité. La plupart du temps, la correction est facile à prouver. Terminaison et correction d’une fonction récursive Exemple: soit la fonction factorielle définie plus haut. On montre par récurrence sur n ≥ 0 la propriété suivante : Hn : factorielle(n) termine et renvoie la valeur n! La propriété est vérifiée car factorielle(0) se réduit à return 1. Pour n > 0, on suppose Hn-1et on cherche à montrer Hn. Le calcul de factorielle(n) commence par un appel récursif à factorielle(n-1). Par hypothèse de récurrence, cet appel termine et renvoie la valeur (n−1)!. Puis l’appel à factorielle(n) multiplie ce résultat par n et renvoie le produit. Donc, cet appel termine et renvoie bien n × (n − 1)! = n!, ce qui démontre Hn. Il est important de noter que nous n’avons rien démontré quant aux appels à la fonction factorielle sur des arguments négatifs dans ce cas la fonction va échouer ( assert n >= 0). Complexité d’une fonction récursive On explique ici comment calculer le coût d’une fonction récursive, à savoir le nombre d’opérations élémentaires qu’elle effectue ou son occupation mémoire totale. Complexité d’une fonction récursive Complexité d’une fonction récursive Complexité d’une fonction récursive Complexité d’une fonction récursive Complexité en espace d’une fonction récursive Chaque appel récursif alloue de la mémoire pour les paramètres effectifs et les variables locales de cet appel. L’occupation mémoire d’un calcul récursif admet donc pour majorant le produit du nombre d’appels récursifs par la quantité de mémoire allouée par chaque appel. Dans les deux exemples précédents, on a calculé explicitement le nombre d’appels A(n). L’occupation mémoire est donc 2n dans le premier cas (il y a deux cases mémoire, une pour n et une autre pour r) et 2(2n − 1) dans le second cas (il y a une case mémoire, pour n). Cependant, dans le second cas, les 2(2n−1) cases mémoire ne seront pas utilisées simultanément. En effet, celles allouées pour le premier appel à u(n-1) peuvent être réutilisées pour le second (et en pratique elles le sont). Pour une analyse plus fine de l’occupation mémoire, il convient donc de calculer le nombre d’appels imbriqués. Comparaison entre récursivité et itération La comparaison entre un algorithme récursif et un algorithme itératif repose sur deux aspects de l’évaluation : 1 Complexité spatiale : on mesure l'espace mémoire occupée par les variables. 2 Complexité temporelle : on mesure le nombre d'opérations. Pour une analyse plus fine de l’occupation mémoire, il convient donc de calculer le nombre d’appels imbriqués. Comparaison entre récursivité et itération Itératif Récursif def u(n): r = 2. for i in range(n): r = 0.5 * (r + 3. / r) return r Complexité en temps est en O(n). Complexité en espace : on mesure l’espace mémoire occupée par les variables, ici l’occupation mémoire est donc 2 (il y a deux cases mémoire, une pour n et une autre pour r) donc la complexité est en O(1). def u(n): if n == 0: return 2. else: x = u(n-1) return 0.5 * (x + 3. / x) Complexité en temps est en O(n). Complexité en espace est en O(n). Comparaison entre récursivité et itération 0,00E+00 5,00E-04 1,00E-03 1,50E-03 2,00E-03 2,50E-03 3,00E-03 300 320 340 360 380 400 420 440 460 480 500 temps d'exécution (s) valeurs temps REC TEMPS POUR TEMPS TANT QUE Comparaison expérimentale du calcul de la factorielle en itératif et en récursif. Limitation de la récursivité en python Conclusion Les avantages de la récursivité : il est plus facile de prouver un algorithme récursif que son équivalent itératif. L’écriture d’un programme récursif est souvent plus claire (plus mathématique) que son équivalent itératif. Parfois il n’est pas aisé de transformer un algorithme récursif en un uploads/Ingenierie_Lourd/ chapitre-6-pdf.pdf