Récursivité (MPSI)

Écrire et analyser des fonctions récursives, comprendre la pile d'appels et la démarche « diviser pour régner ».

MPSI · Séquence 3 sur 10 · Thèmes : Programmation Python, Algorithmique et preuve de programmes

Notions abordées

• Concept de récursion
• Types de récursivité
• Pile d'appels
• Limites de la récursivité
• Diviser pour régner
• Structures récursives

Ressources de la séquence

Ces ressources sont réservées aux élèves et professeurs inscrits :

• Un cours rédigéSe connecter pour ouvrir
• Une présentationSe connecter pour ouvrir
• Une série d'exercicesSe connecter pour ouvrir
• Un notebook Python à compléter, exécutable dans le navigateurSe connecter pour ouvrir

Dans le programme MPSI

• Séquence précédente : Introduction à Python
• Séquence suivante : Correction et terminaison des programmes
• Toutes les séquences de MPSI

Thèmes liés dans l'autre année

• MP · Séquence 1

  Complexité algorithmique

  Mesurer l'efficacité d'un algorithme : compter les opérations, utiliser la notation asymptotique et calculer la complexité de programmes itératifs et récursifs.

• MP · Séquence 2

  Algorithmes de tri

  Comprendre, programmer et comparer les principaux algorithmes de tri, des tris simples au tri rapide et au tri fusion.

• MP · Séquence 3

  Arbres binaires

  Représenter, parcourir et exploiter les arbres binaires, les arbres binaires de recherche et les tas.