01 · Naturels : zéro, successeur et récursion
Naturels : zéro, successeur et récursion¶
Représentez tout naturel par zéro ou un successeur, puis lisez l’égalité et l’addition dans ces deux cas.
Vous savez que les opérateurs appellent des méthodes spéciales et que le décorateur journalise au retour.
- expliquer avec vos mots la définition mathématique de « Naturels : zéro, successeur et récursion »
- indiquer comment elle est représentée dans les données Python
- prédire une petite exécution à partir du code réel
Zéro et successeur appartiennent au point de départ de Peano. `n + 0 = n` et `n + S(m) = S(n + m)` définissent récursivement l’addition.
`pre=None` représente zéro et `pre=n` représente `S(n)`. Le 2 est la chaîne `S(S(0))`, pas un champ contenant l’int 2.
`0` / `S(n)` → `NaturalNumber.pre`; recursive addition → `__add__`
Définition mathématique
Définition mathématique¶
Zéro et successeur appartiennent au point de départ de Peano. n + 0 = n et n + S(m) = S(n + m) définissent récursivement l’addition.
Représentation des données
Représentation des données¶
pre=None représente zéro et pre=n représente S(n). Le 2 est la chaîne S(S(0)), pas un champ contenant l’int 2.
Implémentation Python
Implémentation Python¶
__eq__ distingue zéro et successeur puis compare les prédécesseurs ; les branches de __add__ reprennent exactement les deux équations.
La correspondance exacte utilisée dans ce cours:
Trace d’exécution
Trace d’exécution¶
Pour 2 + 2, l’opérande droit descend à zéro. Au retour, le cas de base précède les deux appels externes.
Notez la ligne de base, la dernière ligne récursive et la valeur finale.
Écrivez d’abord votre prédiction, puis exécutez.
Vérification par les tests
Vérification par les tests¶
Les tests nomment la séparation de zéro, l’injectivité du successeur et les équations d’addition ; ils ne remplacent pas l’induction.
Portée et limites
Portée et limites¶
La chaîne unaire montre la structure mais son coût croît avec la valeur ; gardez de petites entrées.