Remerciez-le!

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

Informatique générale La récursivité CPGE 2ème année Nous verrons dans ce chapi

Informatique générale La récursivité CPGE 2ème année Nous verrons dans ce chapitre ce qu’est la récursivité, son utilité et ses limites. Dans ce chapitre, vous mettrez en application ces concepts au travers d’exemples simples, les exemples plus complexes seront traités au travers des autres TPs de l’année (tris, graphes, etc.) I Les fonctions récursives 1 Rappels : suites arithmético-géométriques expl : la suite récursive ( un+1=0,8un + 4 u0 =−2 , cherchons son expression explicite. Recherche du point ﬁxe : . . . Suite auxiliaire : . . . Résolution : . . . 2 La récursivité On dit qu’une fonction f est récursive lorsque son exécution provoque un ou plusieurs appels de f elle-même. Il y a alors un appel . . . . . . . . . . . . . et des appels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Comme nous le verrons, une récursivité mal gérée peut très vite accaparer l’ensemble des ressources de l’ordinateur et ainsi le paralyser. Ainsi pour se protéger, les langages de programmation des années 50-60 ne permettaient pas la récursivité mais de nos jours la grande majorité des langages l’acceptent. expl : cherchons à calculer la factorielle n! = n Y i=1 i Une possibilité serait : def factorielle(n) : r e s u l t=1 for i in . . . . . . . . . Néanmoins puisque la même opération est appliquée, on pourrait proposer une fonction récursive. En posant un =n!, la factorielle se déﬁnit par la récurrence un = ( . . . si n=0 . . . . . . . . . . . sinon , et ainsi : def factorielleR(n) : i f . . . . . . else : . . . La fonction factorielleR va multiplier par n le résultat que renverra la même fonction mais avec le paramètre n-1 et ainsi de suite. In ﬁne, on a bien calculé la factorielle de n. 3 Pile d’exécution d’une fonction récursive Lorsque l’ordinateur exécute un programme, il met en mémoire le code des instructions ainsi que l’état de certaines variables. Il en va de même lors d’appels de fonction, le code est chargé ainsi que les paramètres. Puis une fois la fonction évaluée, cette mémoire est libérée. On peut donc représenter les exécutions comme une pile d’instructions et de valeurs. Lorsqu’une fonction est appelée, la fonction ainsi que ses paramètres sont empilés, puis une fois exécuter, la pile est dépilée. Si on appelle factorielleR(3), que comporte la pile ? Lycée du Parc des Loges 1/ 7 CPGE 2ème année La récursivité Informatique générale n=3 ; return 3*factorielleR(2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . On peut dès lors remarquer que si la fonction s’appelle elle-même de nombreuses fois, la pile va très vite augmenter et pourra certainement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Rq : en python, la récursivité est limitée à 1 000 appels. 4 Terminaison d’une fonction récursive Comment être certain que la fonction s’arrêtera ? On utilise en général la descente de Fermat (ou descente inﬁnie) aﬁn de montrer que la fonction se termine (i.e. qu’il y aura un nombre ﬁni d’instructions exécutées). expl : considérons la fonction factorielleR déﬁnie précédemment. On considère le paramètre n qui est un entier donc . . . . . . . . . . . . . . . . . . .. Puisque factorielleR(0) se termine et renvoie 1, il suﬃt de vériﬁer que . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Ce qui est le cas, donc la fonction factorielleR n’eﬀectuera qu’un nombre ﬁni d’instructions et se terminera. expl : la terminaison de la suite de Syracuse n’a toujours pas été démontrée. On rappelle que cette suite est déﬁnie par u0 entier et un+1 = ( un 2 si un est pair 3un + 1 sinon . 5 Correction d’une fonction récursive Comment être certain que la fonction renverra le bon résultat ? On utilise en général un résonnement par récurrence pour montrer qu’elle renvoie bien le bon résultat. expl : déﬁnissons Hn l’hypothèse de récurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H0 est . . . . . . . . Supposons Hn vériﬁée, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hn est donc vraie quelque soit n entier et la fonction récursive factorielleR est . . . . . . . . . . . . 6 Complexité d’une fonction récursive La complexité a été vue en première année. Il existe principalement deux types de complexité : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dans nos approches, on considérera la complexité . . . . . . . . . . . . . . . comme la complexité arithmétique en comptant le nombre d’opérations faites. La complexité . . . . . . . . . . . . sera considérée comme la place mémoire nécessaire à l’exécution du pro- gramme. expl : factorielle nécessite . unités de mémoire (. . . . . . . . . . . . . . ) . . . opérations ( . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ) expl : factorielleR nécessite . unités de mémoire (. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . uploads/Science et Technologie/ cpge-info-recursivite-eleve.pdf