INGIniousVous avez appris précédemment comment utiliser la récursion sur des entiers et des tableaux.
Dans cette séance-ci, nous travaillerons la récursion sur les listes. Ce type de données abstrait présente un exemple de récursion structurelle : la liste est définie soit comme la liste vide, soit comme un élément suivi d'une liste.
Une telle implémentation vous est fournie par la classe List.py.
La figure suivante représente graphiquement un objet de type List qui contient les entiers de 1 à 5.
\begin{equation*}
\boxed{1}\rightarrow\boxed{\boxed{2}\rightarrow\boxed{\boxed{3}\rightarrow\boxed{\boxed{4}\rightarrow\boxed{\boxed{5}\rightarrow\!\bullet}}}}
\end{equation*}
On vous demande d'implémenter un algorithme avec récursion. Avant d'élaborer votre algorithme, détaillez :
- le cas de base,
- comment traiter le cas de base,
- comment construire la solution actuelle (taille n) si je connais une solution pour un problème plus petit (par exemple de taille n-1).