Remerciez-le!

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

Cpge info recursivite eleve

Informatique générale La récursivité CPGE è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 Rappels suites arithmético-géométriques expl la suite récursive un un u ?? cherchons son expression explicite Recherche du point ?xe Suite auxiliaire Résolution 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 - ne permettaient pas la récursivité mais de nos jours la grande majorité des langages l ? acceptent n expl cherchons à calculer la factorielle n i i Une possibilité serait def f a c t o r i e l l e n r e s u l t 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 sinon et ainsi def f a c t o r i e l l e R n if else La fonction factorielleR va multiplier par n le résultat que renverra la même fonction mais avec le paramètre n- et ainsi de suite In ?ne on a bien calculé la factorielle de n 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 que comporte la pile Lycée du Parc des Loges CCPGE ème année La récursivité Informatique générale n return factorielleR 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 à appels 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