Page 68 - Activités algorithmiques avec Python en spécialité Mathématiques

Thème : combinatoire & probabilités
TI-83 Premium CE Edition Python TI-82 Advanced Edition Python
Niveau : spécialité maths Terminale
La combinatoire des parties
L. DIDIER & R. CABANE
Défi : peut-on modérer un peu la récursivité ?
La récursivité présente l’avantage de la simplicité mais l’inconvénient d’amener parfois une « explosion » de la consommation de mémoire, très inefficace. C’est le cas dans la fonction combin ci- dessus : lors de l’appel combin(2,"abcd"), se déclenchent les appels combin(1,"bcd") et combin(2,"bcd") ; le premier va appeler combin(1,"cd") et le second de même : il y a un « doublon ». Dans l'appel combin(2,"abcde") les doublons sont bien plus fréquents...
Une fonction « simplement récursive » (qui s’appelle elle-même une seule fois) serait bien préférable. Nous en présentons un exemple ci-dessous.
Les lecteurs sont invités à en analyser le comportement en décrivant pas à pas (sur papier !) les actions qui se suivent lors de l’appel combin(2,"abcd").
Indication : nous avons ici une « définition de fonction à
l’intérieur d’une fonction ». Cette manière de procéder est tout à fait légitime en Python ; la fonction interne co (qui est récursive) va pouvoir traiter la variable L comme « externe » mais modifiable.
66
Ce document est mis à disposition sous licence Creative Commons
© Texas Instruments 2021 / Photocopie autorisée