NSIChapitre 4

Langages et programmation

L'essentiel en 30 secondes

La récursivité est une fonction qui s'appelle elle-même avec un cas de base (arrêt) et un cas récursif. Chaque appel utilise la pile d'appels ($O(n)$ en mémoire). La POO structure le code en classes (attributs + méthodes, constructeur __init__, self obligatoire) et objets (instances). La modularité découpe le programme en modules/fonctions testables. Pour prouver un algorithme : invariant (correction) + variant (terminaison). Toujours documenter (docstring) et tester (assert, cas limites).

Les notions à connaître

Récursivité: Fonction qui s'appelle elle-même. Nécessite un cas de base (arrêt) et un cas récursif qui se rapproche du cas de base à chaque appel. Chaque appel crée un nouveau contexte sur la pile d'appels.
Pile d'appels (call stack): Chaque appel récursif empile un contexte (variables locales, adresse de retour). Quand le cas de base est atteint, les contextes se dépilent. Si trop d'appels : RecursionError (limite Python ~1000).
Classe: Modèle (plan) qui définit des attributs (données) et des méthodes (comportements). Se déclare avec class NomClasse:. Le constructeur est $__init__(self$ , ...).
Objet (instance): Variable créée à partir d'une classe via le constructeur. Ex $: ma_v$ oiture = Voiture('rouge', 2024). Chaque objet a ses propres valeurs d'attributs.
Encapsulation: Principe de regrouper données et traitements dans un objet, en contrôlant l'accès. Convention Python : $_attribut$ (protégé), $__attribut$ (privé, name mangling).
Modularité: Découpage du code en fonctions et modules (fichiers .py) indépendants. Chaque module a une responsabilité claire. On importe avec import module ou from module import fonction.
Méthodes spéciales (dunder): $__init__$ (constructeur), $__str__$ (affichage print), $__repr__$ (représentation), $__eq__$ (égalité $==), __lt__$ (comparaison $<), __len__$ (len()). Permettent de personnaliser le comportement des objets.
Assertion (assert): Instruction de vérification : assert condition, 'message'. Si la condition est False, lève AssertionError. Utilisé pour les préconditions et les tests.

Les erreurs à éviter en nsi

Oublier le return dans la récursion
Écrire return n * factorielle(n-1) et pas juste factorielle(n-1). Sans return, la fonction renvoie None.
Oublier self dans la définition d'une méthode
Toute méthode d'instance prend self en premier paramètre : def $ma_m$ ethode(self, ...):
Modifier un attribut de classe au lieu d'un attribut d'instance
Définis les attributs dans $__init__$ avec self.attribut $=$ ..., pas directement dans le corps de la classe.
Pas de cas de base dans la récursion
Toujours commencer par le(s) cas de base. Vérifie que le cas récursif se rapproche du cas de base à chaque appel.
Utiliser Fibonacci récursif naïf pour de grandes valeurs
fib(40) prend des secondes car la complexité est $O(2^n)$ . Utilise la mémoïsation ou la version itérative.

Sais-tu répondre à ces questions ?

Les corrigés détaillés sont dans le quiz du chapitre.

Qu'est-ce qu'un cas de base dans une fonction récursive ?
En programmation orientée objet en Python, quel mot-clé permet de créer une classe ?
Que renvoie l'appel factorielle(5) avec la fonction suivante ? def factorielle(n): if n == 0: return 1 return n * factorielle(n - 1)
On considère la classe suivante : class Compteur: def $__init__(self)$ : self.valeur $= 0$ def $incrementer(self)$ : self.valeur $+= 1$ def $__str__(self)$ : return f"Compteur: {self.valeur}" $c =$ Compteur() c.incrementer() c.incrementer() c.incrementer() $print(c)$ Qu'affiche ce programme ?
Que renvoie l'appel mystere(4) ? def mystere(n): if n <= 1: return n return mystere(n - 1) + mystere(n - 2)

Accède à la fiche complète

Crée ton compte gratuit pour lire la fiche en entier et accéder à 7 000+ contenus de révision.

Créer un compte gratuit Se connecter