| Récursivité d’une fonction. Récursivité croisée. Organisation des activations sous forme d’arbre en cas d’appels multiples. |
On se limite à une présentation pratique de la récursivité comme technique de programmation. Les récurrences usuelles : 𝑇(𝑛) = 𝑇(𝑛−1) + 𝑎𝑛,𝑇(𝑛) = 𝑎𝑇(𝑛/2) + 𝑏, ou 𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑓(𝑛) sont introduites au fur et à mesure de l’étude de la complexité des différents algorithmes rencontrés. On utilise des encadrements élémentaires ad hoc afin de les justifier; on évite d’appliquer un théorème-maître général. |
| Ensemble ordonné, prédécesseur et successeur, prédécesseur et successeur immédiat. Éléments minimal. Ordre produit, ordre lexicographique. Ordre bien fondé. |
On fait le lien avec la notion d’accessibilité dans un graphe orienté acyclique. L’objectif n’est pas d’étudier la théorie abstraite des ensembles ordonnés mais de poser les définitions et la terminologie. |
| Ensemble inductif, défini comme le plus petit ensemble engendré par un système d’assertions et de règles d’inférence. Ordre induit. Preuve par induction structurelle. |
On insiste sur les aspects pratiques : construction de structure de données et filtrage par motif. On présente la preuve par induction comme une généralisation de la preuve par récurrence. |