Chapitre 4 - Révision : Récursivité

---

1. Récursivité

• Fonction récursive : s'appelle elle-même
• Cas de base : condition d'arrêt (résultat direct)
• Cas récursif : appel avec paramètres plus proches du cas de base
• Pile d'appels : chaque appel est empilé, dépilé au retour
• Limite Python : 1 000 appels par défaut (RecursionError)

def factorielle(n):
    if n == 0:       # cas de base
        return 1
    return n * factorielle(n - 1)   # cas récursif

Terminaison : identifier un variant (entier positif qui décroît strictement).

---

2. Calculabilité et décidabilité

Concept	Définition
Programme = donnée	Un programme est un fichier manipulable par d'autres programmes
Calculabilité	Ce qui peut être calculé par un algorithme
Décidabilité	Problème admettant un algorithme qui répond oui/non dans tous les cas
Problème de l'arrêt	Indécidable : aucun programme ne peut dire si tout programme termine
Thèse de Church-Turing	Tous les langages complets sont équivalents en puissance de calcul