Exercices corrigés — Récursivité (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Descente et remontée
- Un variant qui ne décroît pas assez
- Terminal ou non
- Le let qui change la complexité
- Combien d'appels coûte le chevauchement
- Recherche dichotomique récursive, prouvée
- Renverser une liste : deux décompositions, deux complexités
- L'algorithme d'Euclide et son pire cas
- Diviser par deux ne rend pas logarithmique
- Un appel qui semble terminal et ne l'est pas
- Probleme – Le tri par partition-fusion, et la troisième récurrence
- Probleme – Les tours de Hanoï : le compte, la borne, la pile
- Probleme – Engendrer toutes les parties d'un ensemble
- Probleme – : trois régimes, résolus à la main
- Probleme – Le débordement de pile, mesuré en OCaml et en C