Recursivité

Objectifs de la séance

Pour résoudre un problème de taille donnée, il peut être nécessaire de résoudre des sous-problèmes de tailles plus petites, puis d’agréger les résultats intermédiaires pour obtenir le résultat final. Les algorithmes récursifs font exactement cela, en décrivant les opérations à effectuer sur une petite partie des données, avant de passer à la partie suivante via un appel à soi-même.

Dans cette séance, vous étudierez des situations, souvent caractérisées par la nature des structures de données, où les solutions algorithmiques s’expriment naturellement de manière récursive.

Avant le cours

Pré-requis

Pour pouvoir commencer à travailler sur l’activité, vous devez remplir les conditions suivantes :

• Veuillez apporter votre propre ordinateur.
• Assurez-vous d’avoir une connexion réseau fonctionnelle.

Articles à étudier

Pour pouvoir commencer l’activité pratique efficacement, consultez les documentations sur les algorithmes et les structures de données récursifs.

• Algorithmes récursifs

  Dans cet article, nous vous présentons ce qu'est un algorithme récursif.

  5 min de lecture

• Structures de données récursives

  Dans cet article, nous vous présentons ce qu'est une structure de données récursive.

  5 min de lecture

• Quiz d’auto-évaluation

  Ces quiz sont là pour vous permettre de vérifier que vous avez compris les articles à étudier.

Pendant le cours

Quiz Wooclap

Commencez par effectuer le quiz Wooclap de la session avec votre encadrant(e) pour vérifier que vous disposez des connaissances nécessaires pour aborder sereinement les activités pratiques.

Activité pratique

• TP : Fonctions récursives

  Voici une liste d'exercices pour expérimenter la construction de fonctions récursives.

  1h15

• TP : Types de données récursives

  Dans cette activité, vous allez implémenter un arbre généalogique qui repose sur une structure de données récursive.

  1h15

Après le cours

Terminer l’activité pratique

Avant la prochaine séance, vous devez :

• Revoir le contenu des articles ci-dessus.
• Compléter les parties non optionnelles de l’activité pratique.

Préparer la prochaine séance

De plus, vous devez :

• Vérifier la section “Avant le cours” de la prochaine séance, et vous assurer de faire tout ce qui est nécessaire pour la préparer.