import sys

# Anatomie d'une fonction récursive : cas de base + cas récursif
def factorielle(n: int) -> int:
    if n <= 1:            # cas de base : arrête la récursion
        return 1
    return n * factorielle(n - 1)   # cas récursif : réduit le problème

# Récursivité sur une structure de données (liste chaînée, arbre) plutôt qu'un compteur
def somme_liste(liste: list) -> int:
    if not liste:
        return 0
    return liste[0] + somme_liste(liste[1:])   # attention : liste[1:] copie -> O(n) par appel, O(n^2) total

def somme_liste_efficace(liste: list, index: int = 0) -> int:
    if index == len(liste):
        return 0
    return liste[index] + somme_liste_efficace(liste, index + 1)   # O(n) total, pas de copie

# Récursion multiple : Fibonacci naïf (arbre d'appels exponentiel)
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)   # deux appels récursifs par niveau -> O(2^n)

# Récursion terminale (tail recursion) : Python ne l'optimise PAS, mais le pattern reste utile
def factorielle_terminale(n: int, accumulateur: int = 1) -> int:
    if n <= 1:
        return accumulateur
    return factorielle_terminale(n - 1, n * accumulateur)   # l'appel récursif est la DERNIÈRE opération

# Limite de récursion en Python (pas de tail-call optimization -> pile d'appels réelle)
print(sys.getrecursionlimit())   # 1000 par défaut
# sys.setrecursionlimit(5000)   # à utiliser avec prudence : risque de crash (stack overflow) natif

# Conversion récursif -> itératif avec une pile explicite (évite la limite de récursion)
def factorielle_iterative(n: int) -> int:
    resultat = 1
    for i in range(2, n + 1):
        resultat *= i
    return resultat

# Récursion mutuelle : deux fonctions qui s'appellent l'une l'autre
def est_pair(n: int) -> bool:
    if n == 0:
        return True
    return est_impair(n - 1)

def est_impair(n: int) -> bool:
    if n == 0:
        return False
    return est_pair(n - 1)

# Diviser pour régner : la tour de Hanoï, illustration classique de récursivité
def hanoi(n: int, source: str, auxiliaire: str, destination: str, mouvements: list | None = None) -> list[str]:
    if mouvements is None:
        mouvements = []
    if n == 1:
        mouvements.append(f"Déplacer disque 1 de {source} vers {destination}")
        return mouvements
    hanoi(n - 1, source, destination, auxiliaire, mouvements)   # déplace n-1 disques hors du chemin
    mouvements.append(f"Déplacer disque {n} de {source} vers {destination}")
    hanoi(n - 1, auxiliaire, source, destination, mouvements)   # replace les n-1 disques sur la destination
    return mouvements

assert len(hanoi(3, "A", "B", "C")) == 2**3 - 1   # 2^n - 1 mouvements nécessaires

# Backtracking simple par récursion : générer tous les sous-ensembles d'un tableau
def sous_ensembles(tableau: list, index: int = 0, courant: list | None = None) -> list[list]:
    if courant is None:
        courant = []
    if index == len(tableau):
        return [courant[:]]   # copie car "courant" sera modifié par les appels suivants
    sans_element = sous_ensembles(tableau, index + 1, courant)
    courant.append(tableau[index])
    avec_element = sous_ensembles(tableau, index + 1, courant)
    courant.pop()   # backtrack : retire l'élément avant de remonter
    return sans_element + avec_element