Recursion

Présentation & objectifs

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 techniques

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.

Pendant le cours

Acquisition des connaissances

Pour pouvoir commencer l’activité pratique efficacement, nous introduirons quelques concepts nécessaires au début du cours. Pour vous faire gagner du temps, nous vous présenterons quelques diapositives, que vous pouvez trouver ci-après :

• Diapositives de la séance.

Ces diapositives couvrent uniquement les éléments principaux du cours, et beaucoup plus de détails sont donnés dans les articles associés, que vous devriez étudier en détail :

• Recursive algorithms.

Vous pouvez vérifier votre compréhension de ces articles ici :

• Self-assessment quiz.

Activité pratique

Le reste du cours est dédié à une activité pratique. Lorsque vous êtes prêt, cliquez sur le lien ci-dessous pour commencer :

• Practical activity.

Après le cours

Compléter la séance en cours

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.