Récursivité et pile d’appels
Toute fonction récursive exige un cas de base et une progression vers lui.
Qu’est-ce que Récursivité et pile d’appels ?
Toute fonction récursive exige un cas de base et une progression vers lui.
Résolvez un problème par une instance plus petite.
Points importants
- Testez les entrées vides, uniques, dupliquées et déjà triées.
- Séparez correction et optimisation.
- Préférez la bibliothèque standard en production.
Exemples de code C et C++
main.c
#include <stdio.h>
unsigned long long factorial(unsigned number) {
return number < 2 ? 1 : number * factorial(number - 1);
}
int main(void) {
printf("%llu\n", factorial(6));
}
720C++
main.cpp
#include <iostream>
constexpr unsigned long long factorial(unsigned number) {
return number < 2 ? 1 : number * factorial(number - 1);
}
int main() {
constexpr auto value = factorial(6);
std::cout << value << '\n';
}
720Comparaison entre C et C++
La factorielle utilise O(n) temps et O(n) pile. Les grandes entrées exigent validation et souvent une version itérative.
C
Boucles, pointeurs, tailles et buffers sont explicites.
C++
Itérateurs et algorithmes séparent opération et stockage.
Exercices pratiques
Exécutez les deux versions puis modifiez-les pour observer leurs garanties.
- Tracez chaque comparaison.
- Testez doublons et valeurs extrêmes.
- Comparez aux algorithmes standards.