# Fichier: python_cheats/cheatsheets/recursive.txt
# Cheatsheet Fonctions Récursives Python - Guide Complet pour Débutants


[OK] QU'EST-CE QU'UNE FONCTION RÉCURSIVE ?

# Définition
# Une fonction récursive est une fonction qui s'appelle elle-même
# Elle résout un problème en le décomposant en sous-problèmes plus simples

# Anatomie d'une fonction récursive
def fonction_recursive(parametres):
    # 1. CAS DE BASE (condition d'arrêt) - OBLIGATOIRE
    if condition_arret:
        return valeur_simple
    
    # 2. CAS RÉCURSIF (appel à soi-même)
    return fonction_recursive(parametres_modifies)

# Exemple le plus simple: compte à rebours
def compte_a_rebours(n):
    # Cas de base: quand n atteint 0, on arrête
    if n <= 0:
        print("Décollage! [RAPIDE]")
        return
    
    # Cas récursif: afficher n et rappeler avec n-1
    print(n)
    compte_a_rebours(n - 1)

# Utilisation
compte_a_rebours(5)

# === SORTIE CONSOLE ===
# 5
# 4
# 3
# 2
# 1
# Décollage! [RAPIDE]
# 
# Explication du déroulement:
# compte_a_rebours(5) -> affiche 5, puis appelle compte_a_rebours(4)
#   compte_a_rebours(4) -> affiche 4, puis appelle compte_a_rebours(3)
#     compte_a_rebours(3) -> affiche 3, puis appelle compte_a_rebours(2)
#       compte_a_rebours(2) -> affiche 2, puis appelle compte_a_rebours(1)
#         compte_a_rebours(1) -> affiche 1, puis appelle compte_a_rebours(0)
#           compte_a_rebours(0) -> n=0, cas de base! Affiche "Décollage!" et return


[OK] CONCEPTS FONDAMENTAUX

# === 1. CAS DE BASE (BASE CASE) ===
# C'est la condition qui arrête la récursion
# SANS cas de base = boucle infinie = crash!

# [X] MAUVAIS - Pas de cas de base
def mauvais_exemple(n):
    print(n)
    mauvais_exemple(n - 1)  # Erreur: RecursionError

# [OK] BON - Avec cas de base
def bon_exemple(n):
    if n <= 0:  # CAS DE BASE
        return
    print(n)
    bon_exemple(n - 1)

# === 2. CAS RÉCURSIF (RECURSIVE CASE) ===
# L'appel à la fonction elle-même avec des paramètres modifiés
# Les paramètres DOIVENT se rapprocher du cas de base

def somme_recursive(n):
    # Cas de base
    if n <= 0:
        return 0
    
    # Cas récursif: n + somme de tous les nombres avant n
    return n + somme_recursive(n - 1)

print(somme_recursive(5))  # 15 (5+4+3+2+1)

# === SORTIE CONSOLE ===
# 15
#
# Visualisation étape par étape de l'exécution:
# Appels descendants (empilage):
# somme_recursive(5) -> attend le résultat de somme_recursive(4)
#   ├─ somme_recursive(4) -> attend le résultat de somme_recursive(3)
#   │   ├─ somme_recursive(3) -> attend le résultat de somme_recursive(2)
#   │   │   ├─ somme_recursive(2) -> attend le résultat de somme_recursive(1)
#   │   │   │   ├─ somme_recursive(1) -> attend le résultat de somme_recursive(0)
#   │   │   │   │   └─ somme_recursive(0) -> CAS DE BASE! retourne 0
#   │   │   │   └─ retourne 1 + 0 = 1
#   │   │   └─ retourne 2 + 1 = 3
#   │   └─ retourne 3 + 3 = 6
#   └─ retourne 4 + 6 = 10
# └─ retourne 5 + 10 = 15

# Calcul détaillé:
# somme_recursive(5)
#   = 5 + somme_recursive(4)
#   = 5 + (4 + somme_recursive(3))
#   = 5 + (4 + (3 + somme_recursive(2)))
#   = 5 + (4 + (3 + (2 + somme_recursive(1))))
#   = 5 + (4 + (3 + (2 + (1 + somme_recursive(0)))))
#   = 5 + (4 + (3 + (2 + (1 + 0))))  <- Cas de base
#   = 5 + (4 + (3 + (2 + 1)))
#   = 5 + (4 + (3 + 3))
#   = 5 + (4 + 6)
#   = 5 + 10
#   = 15

# === 3. PILE D'APPELS (CALL STACK) ===
# Python empile chaque appel récursif en mémoire
# Limite par défaut: ~1000 appels (varie selon OS)

import sys

# Voir la limite actuelle
print(sys.getrecursionlimit())  # Généralement 1000

# Modifier la limite (ATTENTION: dangereux!)
sys.setrecursionlimit(2000)  # À utiliser avec précaution

# Visualiser la pile
def demo_pile(n):
    if n <= 0:
        print("Cas de base atteint!")
        return
    print(f"Appel #{n} - Avant récursion")
    demo_pile(n - 1)
    print(f"Appel #{n} - Après récursion")

demo_pile(3)

# === SORTIE CONSOLE ===
# Appel #3 - Avant récursion
# Appel #2 - Avant récursion
# Appel #1 - Avant récursion
# Cas de base atteint!
# Appel #1 - Après récursion
# Appel #2 - Après récursion
# Appel #3 - Après récursion
#
# Explication:
# 1. demo_pile(3) s'exécute -> affiche "Appel #3 - Avant"
# 2. Appelle demo_pile(2) -> affiche "Appel #2 - Avant"
# 3. Appelle demo_pile(1) -> affiche "Appel #1 - Avant"
# 4. Appelle demo_pile(0) -> CAS DE BASE -> affiche "Cas de base atteint!"
# 5. Retour à demo_pile(1) -> affiche "Appel #1 - Après"
# 6. Retour à demo_pile(2) -> affiche "Appel #2 - Après"
# 7. Retour à demo_pile(3) -> affiche "Appel #3 - Après"
#
# Visualisation de la pile:
# ┌─────────────┐
# │ demo_pile(3)│ <- Premier appel (dernier à se terminer)
# ├─────────────┤
# │ demo_pile(2)│
# ├─────────────┤
# │ demo_pile(1)│
# ├─────────────┤
# │ demo_pile(0)│ <- Dernier appel (premier à se terminer)
# └─────────────┘


[OK] EXEMPLES CLASSIQUES POUR DÉBUTANTS

# === 1. FACTORIELLE ===
# n! = n × (n-1) × (n-2) × ... × 1
# Exemple: 5! = 5 × 4 × 3 × 2 × 1 = 120

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

print(factorielle(5))  # 120
print(factorielle(0))  # 1
print(factorielle(1))  # 1

# === SORTIE CONSOLE ===
# 120
# 1
# 1
#
# Détail factorielle(5):
# factorielle(5)
#   = 5 * factorielle(4)
#   = 5 * (4 * factorielle(3))
#   = 5 * (4 * (3 * factorielle(2)))
#   = 5 * (4 * (3 * (2 * factorielle(1))))
#   = 5 * (4 * (3 * (2 * 1)))  <- Cas de base
#   = 5 * (4 * (3 * 2))
#   = 5 * (4 * 6)
#   = 5 * 24
#   = 120
#
# Détail factorielle(0):
# factorielle(0) -> n <= 1 -> retourne 1 immédiatement
#
# Détail factorielle(1):
# factorielle(1) -> n <= 1 -> retourne 1 immédiatement

# Version avec validation
def factorielle_safe(n):
    if n < 0:
        raise ValueError("Factorielle uniquement pour nombres positifs")
    if n <= 1:
        return 1
    return n * factorielle_safe(n - 1)

# === 2. PUISSANCE ===
# x^n = x × x × x ... (n fois)

def puissance(x, n):
    # Cas de base
    if n == 0:
        return 1
    if n == 1:
        return x
    
    # Cas récursif
    return x * puissance(x, n - 1)

print(puissance(2, 5))   # 32 (2^5)
print(puissance(3, 4))   # 81 (3^4)

# Version optimisée (divide and conquer)
def puissance_rapide(x, n):
    if n == 0:
        return 1
    if n == 1:
        return x
    
    # Si n est pair: x^n = (x^(n/2))^2
    if n % 2 == 0:
        half = puissance_rapide(x, n // 2)
        return half * half
    # Si n est impair: x^n = x × x^(n-1)
    else:
        return x * puissance_rapide(x, n - 1)

print(puissance_rapide(2, 10))  # 1024

# === 3. FIBONACCI ===
# Séquence: 0, 1, 1, 2, 3, 5, 8, 13, 21...
# F(n) = F(n-1) + F(n-2)

def fibonacci(n):
    # Cas de base
    if n <= 0:
        return 0
    if n == 1:
        return 1
    
    # Cas récursif
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(7))  # 13
print([fibonacci(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

# === SORTIE CONSOLE ===
# 13
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
#
# Détail fibonacci(7):
# fibonacci(7)
#   = fibonacci(6) + fibonacci(5)
#   = (fibonacci(5) + fibonacci(4)) + (fibonacci(4) + fibonacci(3))
#   = ((fib(4) + fib(3)) + (fib(3) + fib(2))) + ((fib(3) + fib(2)) + (fib(2) + fib(1)))
#   ... continue à se développer ...
#   = 8 + 5 = 13
#
# [ATTENTION] ATTENTION: Arbre d'appels pour fibonacci(5) (TRÈS INEFFICACE):
#                    fib(5)
#                   /      \
#              fib(4)        fib(3)
#             /     \        /     \
#        fib(3)   fib(2)  fib(2)  fib(1)
#        /   \    /   \   /   \      |
#    fib(2) fib(1) 1  0  1   0      1
#    /   \    |
#   1    0    1
#
# Nombre d'appels pour fib(5) = 15 appels!
# fib(3) est calculé 3 fois! fib(2) est calculé 5 fois!
# Pour fib(40), il y aurait 331,160,281 appels! [!]
#
# Liste complète Fibonacci(0 à 9):
# fib(0) = 0
# fib(1) = 1
# fib(2) = fib(1) + fib(0) = 1 + 0 = 1
# fib(3) = fib(2) + fib(1) = 1 + 1 = 2
# fib(4) = fib(3) + fib(2) = 2 + 1 = 3
# fib(5) = fib(4) + fib(3) = 3 + 2 = 5
# fib(6) = fib(5) + fib(4) = 5 + 3 = 8
# fib(7) = fib(6) + fib(5) = 8 + 5 = 13
# fib(8) = fib(7) + fib(6) = 13 + 8 = 21
# fib(9) = fib(8) + fib(7) = 21 + 13 = 34

# Version avec mémoïsation (cache)
def fibonacci_memo(n, cache={}):
    if n in cache:
        return cache[n]
    
    if n <= 0:
        return 0
    if n == 1:
        return 1
    
    cache[n] = fibonacci_memo(n - 1, cache) + fibonacci_memo(n - 2, cache)
    return cache[n]

print(fibonacci_memo(50))  # Rapide! 12586269025

# === SORTIE CONSOLE ===
# 12586269025
#
# Différence de performance:
# Sans mémoïsation: fibonacci(50) prendrait des ANNÉES! (2^50 appels ≈ 1,125 quadrillions)
# Avec mémoïsation: fibonacci(50) prend quelques millisecondes (seulement 50 appels uniques)
#
# Comment ça marche:
# 1er appel fibonacci_memo(50):
#   - Pas dans cache -> calcule
#   - Appelle fib(49) et fib(48)
#   - Stocke résultat dans cache[50]
#
# 2ème appel fibonacci_memo(50):
#   - Déjà dans cache -> retourne immédiatement!
#
# Évolution du cache pendant fib(5):
# fib(5) -> cache = {}
#   fib(4) -> cache = {}
#     fib(3) -> cache = {}
#       fib(2) -> cache = {}
#         fib(1) -> retourne 1
#         fib(0) -> retourne 0
#       cache[2] = 1
#     fib(2) -> trouvé dans cache! retourne 1
#     cache[3] = 2
#   fib(3) -> trouvé dans cache! retourne 2
#   cache[4] = 3
# fib(3) -> trouvé dans cache! retourne 2
# cache[5] = 5
#
# Résultat: Au lieu de 15 appels, seulement 9 appels (et 6 lectures cache)

# Version avec décorateur
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_cache(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci_cache(n - 1) + fibonacci_cache(n - 2)

print(fibonacci_cache(100))  # Très rapide!

# === 4. SOMME D'UNE LISTE ===

def somme_liste(liste):
    # Cas de base: liste vide
    if not liste:
        return 0
    
    # Cas récursif: premier élément + somme du reste
    return liste[0] + somme_liste(liste[1:])

print(somme_liste([1, 2, 3, 4, 5]))  # 15
print(somme_liste([]))               # 0

# Version avec index (plus efficace)
def somme_liste_index(liste, index=0):
    # Cas de base
    if index >= len(liste):
        return 0
    
    # Cas récursif
    return liste[index] + somme_liste_index(liste, index + 1)

# === 5. INVERSER UNE CHAÎNE ===

def inverser_chaine(s):
    # Cas de base
    if len(s) <= 1:
        return s
    
    # Cas récursif: dernier caractère + reste inversé
    return s[-1] + inverser_chaine(s[:-1])

print(inverser_chaine("hello"))   # "olleh"
print(inverser_chaine("Python"))  # "nohtyP"

# === SORTIE CONSOLE ===
# olleh
# nohtyP
#
# Détail inverser_chaine("hello"):
# inverser_chaine("hello")
#   = "o" + inverser_chaine("hell")
#   = "o" + ("l" + inverser_chaine("hel"))
#   = "o" + ("l" + ("l" + inverser_chaine("he")))
#   = "o" + ("l" + ("l" + ("e" + inverser_chaine("h"))))
#   = "o" + ("l" + ("l" + ("e" + "h")))  <- len("h") <= 1, retourne "h"
#   = "o" + ("l" + ("l" + "eh"))
#   = "o" + ("l" + "leh")
#   = "o" + "lleh"
#   = "olleh"
#
# Étapes visuelles:
# "hello" -> prendre dernier 'o' -> reste "hell"
#   "hell" -> prendre dernier 'l' -> reste "hel"
#     "hel" -> prendre dernier 'l' -> reste "he"
#       "he" -> prendre dernier 'e' -> reste "h"
#         "h" -> un seul caractère -> retourne "h"
#       construire "e" + "h" = "eh"
#     construire "l" + "eh" = "leh"
#   construire "l" + "leh" = "lleh"
# construire "o" + "lleh" = "olleh"

# Alternative
def inverser_v2(s):
    if len(s) == 0:
        return ""
    return inverser_v2(s[1:]) + s[0]

# === 6. VÉRIFIER PALINDROME ===

def est_palindrome(s):
    # Nettoyer la chaîne
    s = s.lower().replace(" ", "")
    
    # Cas de base
    if len(s) <= 1:
        return True
    
    # Cas récursif: premier == dernier ET milieu est palindrome
    if s[0] != s[-1]:
        return False
    
    return est_palindrome(s[1:-1])

print(est_palindrome("radar"))        # True
print(est_palindrome("kayak"))        # True
print(est_palindrome("python"))       # False
print(est_palindrome("A man a plan a canal Panama"))  # True

# === SORTIE CONSOLE ===
# True
# True
# False
# True
#
# Détail est_palindrome("radar"):
# "radar" (après nettoyage: "radar")
#   premier='r', dernier='r' -> égaux [OK]
#   est_palindrome("ada")
#     premier='a', dernier='a' -> égaux [OK]
#     est_palindrome("d")
#       len("d") <= 1 -> retourne True (cas de base)
#     retourne True
#   retourne True
# retourne True
#
# Détail est_palindrome("python"):
# "python" (après nettoyage: "python")
#   premier='p', dernier='n' -> différents [X]
#   retourne False immédiatement
#
# Détail est_palindrome("A man a plan a canal Panama"):
# Nettoyage: "amanaplanacanalpanama"
#   'a' == 'a' [OK] -> vérifie "manaplanacanalapanam"
#     'm' == 'm' [OK] -> vérifie "anaplanacanalpana"
#       'a' == 'a' [OK] -> vérifie "naplanacanalp an"
#         ... continue ...
#           'n' == 'n' [OK] -> vérifie "a"
#             len("a") <= 1 -> True (cas de base)
#           retourne True
#         retourne True
#       retourne True
#     retourne True
#   retourne True
# retourne True


[OK] MANIPULATION DE LISTES

# === 1. TROUVER MAXIMUM ===

def maximum_liste(liste):
    # Cas de base: un seul élément
    if len(liste) == 1:
        return liste[0]
    
    # Cas récursif: max entre premier et max du reste
    max_reste = maximum_liste(liste[1:])
    return liste[0] if liste[0] > max_reste else max_reste

print(maximum_liste([3, 7, 2, 9, 1]))  # 9

# Version plus élégante
def max_recursive(liste):
    if len(liste) == 1:
        return liste[0]
    return max(liste[0], max_recursive(liste[1:]))

# === 2. COMPTER OCCURRENCES ===

def compter(liste, element):
    # Cas de base
    if not liste:
        return 0
    
    # Cas récursif
    count = 1 if liste[0] == element else 0
    return count + compter(liste[1:], element)

print(compter([1, 2, 3, 2, 4, 2], 2))  # 3
print(compter(['a', 'b', 'a', 'c'], 'a'))  # 2

# === 3. FILTRER LISTE ===

def filtrer(liste, condition):
    # Cas de base
    if not liste:
        return []
    
    # Cas récursif
    if condition(liste[0]):
        return [liste[0]] + filtrer(liste[1:], condition)
    else:
        return filtrer(liste[1:], condition)

nombres = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
pairs = filtrer(nombres, lambda x: x % 2 == 0)
print(pairs)  # [2, 4, 6, 8, 10]

# === 4. APLATIR LISTE IMBRIQUÉE ===

def aplatir(liste):
    # Cas de base: liste vide
    if not liste:
        return []
    
    # Si premier élément est une liste
    if isinstance(liste[0], list):
        return aplatir(liste[0]) + aplatir(liste[1:])
    
    # Sinon, ajouter l'élément et continuer
    return [liste[0]] + aplatir(liste[1:])

print(aplatir(nested))  # [1, 2, 3, 4, 5, 6, 7]

# === SORTIE CONSOLE ===
# [1, 2, 3, 4, 5, 6, 7]
#
# Liste imbriquée originale: [1, [2, 3], [4, [5, 6]], 7]
#
# Exécution détaillée de aplatir([1, [2, 3], [4, [5, 6]], 7]):
#
# Niveau 1: aplatir([1, [2, 3], [4, [5, 6]], 7])
#   liste[0] = 1 (pas une liste)
#   return [1] + aplatir([[2, 3], [4, [5, 6]], 7])
#
# Niveau 2: aplatir([[2, 3], [4, [5, 6]], 7])
#   liste[0] = [2, 3] (EST une liste) [OK]
#   return aplatir([2, 3]) + aplatir([[4, [5, 6]], 7])
#
#   Branche gauche: aplatir([2, 3])
#     liste[0] = 2 (pas une liste)
#     return [2] + aplatir([3])
#       liste[0] = 3 (pas une liste)
#       return [3] + aplatir([])
#         Liste vide -> return []
#       return [3]
#     return [2, 3]
#
#   Branche droite: aplatir([[4, [5, 6]], 7])
#     liste[0] = [4, [5, 6]] (EST une liste) [OK]
#     return aplatir([4, [5, 6]]) + aplatir([7])
#
#     Sous-branche: aplatir([4, [5, 6]])
#       liste[0] = 4 (pas une liste)
#       return [4] + aplatir([[5, 6]])
#         liste[0] = [5, 6] (EST une liste) [OK]
#         return aplatir([5, 6]) + aplatir([])
#
#         aplatir([5, 6])
#           liste[0] = 5 (pas une liste)
#           return [5] + aplatir([6])
#             liste[0] = 6 (pas une liste)
#             return [6] + aplatir([])
#               return []
#             return [6]
#           return [5, 6]
#         
#         return [5, 6] + [] = [5, 6]
#       return [4] + [5, 6] = [4, 5, 6]
#
#     aplatir([7])
#       liste[0] = 7 (pas une liste)
#       return [7] + aplatir([])
#         return []
#       return [7]
#
#     return [4, 5, 6] + [7] = [4, 5, 6, 7]
#
#   return [2, 3] + [4, 5, 6, 7] = [2, 3, 4, 5, 6, 7]
#
# return [1] + [2, 3, 4, 5, 6, 7] = [1, 2, 3, 4, 5, 6, 7]
#
# Visualisation de la structure imbriquée:
# [1, [2, 3], [4, [5, 6]], 7]
#  │   └─┬─┘   │   └─┬─┘   │
#  │     │     │     │      │
#  1    2,3    4    5,6     7
#
# Après aplatissement:
# [1, 2, 3, 4, 5, 6, 7]
#
# Trace avec profondeur:
# aplatir([1, [2,3], [4,[5,6]], 7])       depth=0
#   [1] +
#   aplatir([[2,3], [4,[5,6]], 7])        depth=0
#     aplatir([2,3]) +                    depth=1
#       [2] + aplatir([3])                depth=1
#         [3] + aplatir([])               depth=1
#           []
#       = [2,3]
#     aplatir([[4,[5,6]], 7])             depth=1
#       aplatir([4,[5,6]]) +              depth=2
#         [4] + aplatir([[5,6]])          depth=2
#           aplatir([5,6]) +              depth=3
#             [5] + aplatir([6])          depth=3
#               [6] + []
#             = [5,6]
#           + []
#         = [4,5,6]
#       aplatir([7])                      depth=2
#         [7] + []
#       = [4,5,6,7]
#     = [2,3,4,5,6,7]
# = [1,2,3,4,5,6,7]
#
# Autres exemples:
# aplatir([[[1]]]) -> [1]
# aplatir([1, [2, [3, [4]]]]) -> [1, 2, 3, 4]
# aplatir([[1, 2], [3, 4], [5]]) -> [1, 2, 3, 4, 5]

# === 5. PERMUTATIONS ===

def permutations(liste):
    # Cas de base
    if len(liste) <= 1:
        return [liste]
    
    # Cas récursif
    result = []
    for i in range(len(liste)):
        # Élément courant
        element = liste[i]
        # Reste de la liste
        reste = liste[:i] + liste[i+1:]
        # Permutations du reste
        for perm in permutations(reste):
            result.append([element] + perm)
    
    return result

print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

# === SORTIE CONSOLE ===
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
#
# Explication: Génère toutes les permutations possibles (n! possibilités)
#
# Exécution détaillée de permutations([1, 2, 3]):
#
# Niveau 1: permutations([1, 2, 3])
#   Itération i=0: element=1, reste=[2, 3]
#     permutations([2, 3])
#       Itération i=0: element=2, reste=[3]
#         permutations([3])
#           len([3]) <= 1 -> return [[3]]
#         Pour [3]: result = [2] + [3] = [2, 3]
#       Itération i=1: element=3, reste=[2]
#         permutations([2])
#           len([2]) <= 1 -> return [[2]]
#         Pour [2]: result = [3] + [2] = [3, 2]
#       return [[2, 3], [3, 2]]
#     
#     Pour [2, 3]: result = [1] + [2, 3] = [1, 2, 3] [OK]
#     Pour [3, 2]: result = [1] + [3, 2] = [1, 3, 2] [OK]
#
#   Itération i=1: element=2, reste=[1, 3]
#     permutations([1, 3])
#       Itération i=0: element=1, reste=[3]
#         permutations([3]) -> [[3]]
#         result = [1, 3]
#       Itération i=1: element=3, reste=[1]
#         permutations([1]) -> [[1]]
#         result = [3, 1]
#       return [[1, 3], [3, 1]]
#     
#     Pour [1, 3]: result = [2] + [1, 3] = [2, 1, 3] [OK]
#     Pour [3, 1]: result = [2] + [3, 1] = [2, 3, 1] [OK]
#
#   Itération i=2: element=3, reste=[1, 2]
#     permutations([1, 2])
#       Itération i=0: element=1, reste=[2]
#         permutations([2]) -> [[2]]
#         result = [1, 2]
#       Itération i=1: element=2, reste=[1]
#         permutations([1]) -> [[1]]
#         result = [2, 1]
#       return [[1, 2], [2, 1]]
#     
#     Pour [1, 2]: result = [3] + [1, 2] = [3, 1, 2] [OK]
#     Pour [2, 1]: result = [3] + [2, 1] = [3, 2, 1] [OK]
#
# return [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
#
# Visualisation en arbre:
#                    [1, 2, 3]
#         /              |              \
#     1:[2,3]         2:[1,3]         3:[1,2]
#      /    \          /    \          /    \
#   2:[3] 3:[2]    1:[3] 3:[1]    1:[2] 2:[1]
#     |     |        |     |        |     |
#   [123] [132]    [213] [231]    [312] [321]
#
# Logique de l'algorithme:
# Pour chaque élément à la position i:
# 1. Le fixer en première position
# 2. Générer toutes les permutations du reste
# 3. Ajouter l'élément fixé devant chaque permutation
#
# Exemple avec [A, B, C]:
# - Fixer A: permutations de [B,C] = [BC, CB] -> [ABC, ACB]
# - Fixer B: permutations de [A,C] = [AC, CA] -> [BAC, BCA]
# - Fixer C: permutations de [A,B] = [AB, BA] -> [CAB, CBA]
#
# Nombre de permutations:
# n éléments -> n! permutations
# [1] -> 1! = 1 permutation
# [1,2] -> 2! = 2 permutations
# [1,2,3] -> 3! = 6 permutations [OK]
# [1,2,3,4] -> 4! = 24 permutations
# [1,2,3,4,5] -> 5! = 120 permutations
#
# Complexité:
# - Temporelle: O(n × n!) car on génère n! permutations de taille n
# - Spatiale: O(n × n!) pour stocker toutes les permutations
#
# Application: Problème du voyageur de commerce (TSP)
# Trouver le meilleur ordre pour visiter n villes

# === 6. RECHERCHE BINAIRE ===

def recherche_binaire(liste, element, debut=0, fin=None):
    if fin is None:
        fin = len(liste) - 1
    
    # Cas de base: élément non trouvé
    if debut > fin:
        return -1
    
    # Milieu
    milieu = (debut + fin) // 2
    
    # Cas de base: élément trouvé
    if liste[milieu] == element:
        return milieu
    
    # Cas récursifs
    if element < liste[milieu]:
        return recherche_binaire(liste, element, debut, milieu - 1)
    else:
        return recherche_binaire(liste, element, milieu + 1, fin)

# Liste DOIT être triée!
nombres_tries = [1, 3, 5, 7, 9, 11, 13, 15]
print(recherche_binaire(nombres_tries, 7))   # 3
print(recherche_binaire(nombres_tries, 10))  # -1

# === SORTIE CONSOLE ===
# 3
# -1
#
# Recherche binaire: algorithme O(log n) pour trouver un élément
# CONDITION: La liste DOIT être triée!
#
# Exécution détaillée de recherche_binaire([1,3,5,7,9,11,13,15], 7):
# Liste: [1, 3, 5, 7, 9, 11, 13, 15]
# Index:  0  1  2  3  4   5   6   7
#
# Appel 1: recherche_binaire(..., 7, debut=0, fin=7)
#   milieu = (0 + 7) // 2 = 3
#   liste[3] = 7
#   7 == 7 -> TROUVÉ! return 3 [OK]
#
# Résultat: 3 (l'élément 7 est à l'index 3)
#
# Exécution détaillée de recherche_binaire([1,3,5,7,9,11,13,15], 10):
# Chercher 10 dans [1, 3, 5, 7, 9, 11, 13, 15]
#
# Appel 1: recherche_binaire(..., 10, debut=0, fin=7)
#   milieu = (0 + 7) // 2 = 3
#   liste[3] = 7
#   10 > 7 -> chercher dans la moitié droite
#   return recherche_binaire(..., 10, debut=4, fin=7)
#
# Appel 2: recherche_binaire(..., 10, debut=4, fin=7)
#   milieu = (4 + 7) // 2 = 5
#   liste[5] = 11
#   10 < 11 -> chercher dans la moitié gauche
#   return recherche_binaire(..., 10, debut=4, fin=4)
#
# Appel 3: recherche_binaire(..., 10, debut=4, fin=4)
#   milieu = (4 + 4) // 2 = 4
#   liste[4] = 9
#   10 > 9 -> chercher dans la moitié droite
#   return recherche_binaire(..., 10, debut=5, fin=4)
#
# Appel 4: recherche_binaire(..., 10, debut=5, fin=4)
#   debut > fin -> élément non trouvé
#   return -1 [OK]
#
# Résultat: -1 (10 n'est pas dans la liste)
#
# Visualisation étape par étape pour rechercher 10:
#
# Étape 1: [1, 3, 5, 7, | 9, 11, 13, 15]
#                      ^ milieu=7
#          10 > 7 -> chercher à droite ->
#
# Étape 2: [9, 11, | 13, 15]
#              ^ milieu=11
#          10 < 11 -> chercher à gauche <-
#
# Étape 3: [9]
#           ^ milieu=9
#          10 > 9 -> chercher à droite ->
#
# Étape 4: [] (zone vide)
#          Élément non trouvé -> return -1
#
# Exemple supplémentaire: rechercher 13
# Liste: [1, 3, 5, 7, 9, 11, 13, 15]
#
# Appel 1: milieu=3, liste[3]=7, 13>7 -> droite
# Appel 2: milieu=5, liste[5]=11, 13>11 -> droite
# Appel 3: milieu=6, liste[6]=13, 13==13 -> TROUVÉ! return 6
#
# Comparaison avec recherche linéaire:
# Recherche linéaire: O(n) - parcourt tous les éléments
#   Pour 1000 éléments: jusqu'à 1000 comparaisons
# Recherche binaire: O(log n) - divise par 2 à chaque étape
#   Pour 1000 éléments: maximum 10 comparaisons (log₂(1000) ≈ 10)
#
# Nombre de comparaisons:
# n=8 éléments -> max 3 comparaisons (log₂(8) = 3)
# n=16 -> max 4 comparaisons
# n=1000 -> max 10 comparaisons
# n=1,000,000 -> max 20 comparaisons!
#
# Trace complète pour rechercher 1:
# [1, 3, 5, 7, | 9, 11, 13, 15] -> milieu=7 -> 1<7 -> gauche
# [1, 3, | 5, 7] -> milieu=5 -> 1<5 -> gauche
# [1, | 3] -> milieu=3 -> 1<3 -> gauche
# [1] -> milieu=1 -> 1==1 -> TROUVÉ! return 0


[OK] MANIPULATION DE CHAÎNES

# === 1. COMPTER CARACTÈRE ===

def compter_char(chaine, char):
    if not chaine:
        return 0
    
    count = 1 if chaine[0] == char else 0
    return count + compter_char(chaine[1:], char)

print(compter_char("hello world", "l"))  # 3
print(compter_char("python", "o"))       # 1

# === 2. ENLEVER ESPACES ===

def enlever_espaces(s):
    if not s:
        return ""
    
    if s[0] == " ":
        return enlever_espaces(s[1:])
    
    return s[0] + enlever_espaces(s[1:])

print(enlever_espaces("h e l l o"))  # "hello"

# === 3. REMPLACER CARACTÈRE ===

def remplacer(s, ancien, nouveau):
    if not s:
        return ""
    
    premier = nouveau if s[0] == ancien else s[0]
    return premier + remplacer(s[1:], ancien, nouveau)

print(remplacer("hello", "l", "x"))  # "hexxo"

# === 4. GÉNÉRER SOUS-CHAÎNES ===

def sous_chaines(s):
    # Cas de base
    if len(s) == 0:
        return [""]
    
    # Cas récursif
    premiere_lettre = s[0]
    reste_sous_chaines = sous_chaines(s[1:])
    
    result = []
    for sc in reste_sous_chaines:
        result.append(sc)
        result.append(premiere_lettre + sc)
    
    return result

print(sous_chaines("abc"))
# ['', 'c', 'b', 'bc', 'a', 'ac', 'ab', 'abc']

# === SORTIE CONSOLE ===
# ['', 'c', 'b', 'bc', 'a', 'ac', 'ab', 'abc']
#
# Explication: Génère toutes les sous-chaînes possibles (2^n possibilités)
#
# Exécution détaillée de sous_chaines("abc"):
#
# sous_chaines("abc")
#   premiere_lettre = 'a'
#   reste_sous_chaines = sous_chaines("bc")
#     premiere_lettre = 'b'
#     reste_sous_chaines = sous_chaines("c")
#       premiere_lettre = 'c'
#       reste_sous_chaines = sous_chaines("")
#         Cas de base: return [""]
#       
#       Pour chaque sc in [""]:
#         Ajouter sc = ""
#         Ajouter 'c' + "" = "c"
#       return ["", "c"]
#     
#     Pour chaque sc in ["", "c"]:
#       Ajouter "" et 'b' + "" = "b"
#       Ajouter "c" et 'b' + "c" = "bc"
#     return ["", "c", "b", "bc"]
#   
#   Pour chaque sc in ["", "c", "b", "bc"]:
#     Ajouter "" et 'a' + "" = "a"
#     Ajouter "c" et 'a' + "c" = "ac"
#     Ajouter "b" et 'a' + "b" = "ab"
#     Ajouter "bc" et 'a' + "bc" = "abc"
#   return ["", "c", "b", "bc", "a", "ac", "ab", "abc"]
#
# Visualisation en arbre binaire (prendre ou ne pas prendre):
#                       ""
#                    /      \
#               (pas 'a')   (avec 'a')
#                 ""           "a"
#               /    \       /    \
#           (pas 'b') ('b') ('b') (pas 'b')
#            ""   "b"   "ab"  "a"
#           / \   / \   / \   / \
#          "" "c" "b" "bc" "ab" "abc" "a" "ac"
#
# Les 8 sous-chaînes (2^3 = 8):
# 1. ""    - ne prend aucune lettre
# 2. "c"   - prend seulement 'c'
# 3. "b"   - prend seulement 'b'
# 4. "bc"  - prend 'b' et 'c'
# 5. "a"   - prend seulement 'a'
# 6. "ac"  - prend 'a' et 'c'
# 7. "ab"  - prend 'a' et 'b'
# 8. "abc" - prend toutes les lettres
#
# Formule: Pour n caractères -> 2^n sous-chaînes
# "a" -> 2^1 = 2 sous-chaînes: ["", "a"]
# "ab" -> 2^2 = 4 sous-chaînes: ["", "b", "a", "ab"]
# "abc" -> 2^3 = 8 sous-chaînes [OK]
# "abcd" -> 2^4 = 16 sous-chaînes


[OK] ARBRES ET STRUCTURES RÉCURSIVES

# === 1. ARBRE BINAIRE ===

class Node:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droit = None

# Parcours en profondeur (DFS)
def parcours_profondeur(node):
    if node is None:
        return
    
    print(node.valeur, end=" ")
    parcours_profondeur(node.gauche)
    parcours_profondeur(node.droit)

# Créer arbre
#       1
#      / \
#     2   3
#    / \
#   4   5

root = Node(1)
root.gauche = Node(2)
root.droit = Node(3)
root.gauche.gauche = Node(4)
root.gauche.droit = Node(5)

parcours_profondeur(root)  # 1 2 4 5 3

# === SORTIE CONSOLE ===
# 1 2 4 5 3
#
# Visualisation de l'arbre:
#       1           <- Visité en 1er (racine)
#      / \
#     2   3         <- 2 visité en 2ème, 3 visité en 5ème
#    / \
#   4   5           <- 4 visité en 3ème, 5 visité en 4ème
#
# Ordre de parcours (Pré-ordre: Racine -> Gauche -> Droite):
# 1. Visite node(1) -> affiche "1"
# 2. Va à gauche -> visite node(2) -> affiche "2"
# 3. Va à gauche de 2 -> visite node(4) -> affiche "4"
# 4. node(4) n'a pas d'enfants -> remonte
# 5. Va à droite de 2 -> visite node(5) -> affiche "5"
# 6. node(5) n'a pas d'enfants -> remonte à 1
# 7. Va à droite de 1 -> visite node(3) -> affiche "3"
# 8. node(3) n'a pas d'enfants -> terminé
#
# Pile d'appels (ordre):
# parcours_profondeur(1)
#   ├─ print(1)
#   ├─ parcours_profondeur(2)
#   │   ├─ print(2)
#   │   ├─ parcours_profondeur(4)
#   │   │   ├─ print(4)
#   │   │   ├─ parcours_profondeur(None) -> return
#   │   │   └─ parcours_profondeur(None) -> return
#   │   └─ parcours_profondeur(5)
#   │       ├─ print(5)
#   │       ├─ parcours_profondeur(None) -> return
#   │       └─ parcours_profondeur(None) -> return
#   └─ parcours_profondeur(3)
#       ├─ print(3)
#       ├─ parcours_profondeur(None) -> return
#       └─ parcours_profondeur(None) -> return

# === 2. HAUTEUR DE L'ARBRE ===

def hauteur_arbre(node):
    # Cas de base: noeud vide
    if node is None:
        return 0
    
    # Cas récursif: max des hauteurs + 1
    hauteur_gauche = hauteur_arbre(node.gauche)
    hauteur_droite = hauteur_arbre(node.droit)
    
    return 1 + max(hauteur_gauche, hauteur_droite)

print(f"\nHauteur: {hauteur_arbre(root)}")  # 3

# === SORTIE CONSOLE ===
# Hauteur: 3
#
# Calcul détaillé pour notre arbre:
#       1           <- Niveau 1
#      / \
#     2   3         <- Niveau 2
#    / \
#   4   5           <- Niveau 3
#
# hauteur_arbre(1):
#   hauteur_gauche = hauteur_arbre(2)
#     hauteur_gauche = hauteur_arbre(4)
#       hauteur_gauche = hauteur_arbre(None) = 0
#       hauteur_droite = hauteur_arbre(None) = 0
#       retourne 1 + max(0, 0) = 1
#     hauteur_droite = hauteur_arbre(5)
#       hauteur_gauche = hauteur_arbre(None) = 0
#       hauteur_droite = hauteur_arbre(None) = 0
#       retourne 1 + max(0, 0) = 1
#     retourne 1 + max(1, 1) = 2
#   hauteur_droite = hauteur_arbre(3)
#     hauteur_gauche = hauteur_arbre(None) = 0
#     hauteur_droite = hauteur_arbre(None) = 0
#     retourne 1 + max(0, 0) = 1
#   retourne 1 + max(2, 1) = 3
#
# Explication visuelle:
# Node 4: hauteur = 1 (feuille)
# Node 5: hauteur = 1 (feuille)
# Node 3: hauteur = 1 (feuille)
# Node 2: hauteur = 1 + max(hauteur(4), hauteur(5)) = 1 + max(1,1) = 2
# Node 1: hauteur = 1 + max(hauteur(2), hauteur(3)) = 1 + max(2,1) = 3

# === 3. NOMBRE DE NOEUDS ===

def compter_noeuds(node):
    if node is None:
        return 0
    
    return 1 + compter_noeuds(node.gauche) + compter_noeuds(node.droit)

print(f"Nombre de noeuds: {compter_noeuds(root)}")  # 5

# === 4. SOMME DES VALEURS ===

def somme_arbre(node):
    if node is None:
        return 0
    
    return node.valeur + somme_arbre(node.gauche) + somme_arbre(node.droit)

print(f"Somme: {somme_arbre(root)}")  # 15

# === 5. RECHERCHER VALEUR ===

def rechercher_arbre(node, valeur):
    if node is None:
        return False
    
    if node.valeur == valeur:
        return True
    
    return (rechercher_arbre(node.gauche, valeur) or 
            rechercher_arbre(node.droit, valeur))

print(f"5 existe? {rechercher_arbre(root, 5)}")   # True
print(f"10 existe? {rechercher_arbre(root, 10)}")  # False


[OK] RÉCURSION AVEC DICTIONNAIRES

# === 1. SOMME DES VALEURS ===

def somme_dict_values(d):
    if not d:
        return 0
    
    # Obtenir première clé
    key = next(iter(d))
    value = d[key]
    
    # Reste du dictionnaire
    reste = {k: v for k, v in d.items() if k != key}
    
    return value + somme_dict_values(reste)

data = {'a': 10, 'b': 20, 'c': 30}
print(somme_dict_values(data))  # 60

# === 2. APLATIR DICTIONNAIRE IMBRIQUÉ ===

def aplatir_dict(d, parent_key='', sep='_'):
    items = []
    
    for k, v in d.items():
        new_key = f"{parent_key}{sep}{k}" if parent_key else k
        
        if isinstance(v, dict):
            items.extend(aplatir_dict(v, new_key, sep=sep).items())
        else:
            items.append((new_key, v))
    
    return dict(items)

nested_dict = {
    'a': 1,
    'b': {
        'c': 2,
        'd': {
            'e': 3
        }
    }
}

print(aplatir_dict(nested_dict))
# {'a': 1, 'b_c': 2, 'b_d_e': 3}

# === 3. COMPTER FEUILLES (VALEURS NON-DICT) ===

def compter_feuilles(d):
    if not isinstance(d, dict):
        return 1
    
    count = 0
    for value in d.values():
        count += compter_feuilles(value)
    
    return count

print(compter_feuilles(nested_dict))  # 3


[OK] ALGORITHMES AVANCÉS

# === 1. TRI FUSION (MERGE SORT) ===

def tri_fusion(liste):
    # Cas de base: liste de 0 ou 1 élément
    if len(liste) <= 1:
        return liste
    
    # Diviser en deux moitiés
    milieu = len(liste) // 2
    gauche = liste[:milieu]
    droite = liste[milieu:]
    
    # Trier récursivement chaque moitié
    gauche_triee = tri_fusion(gauche)
    droite_triee = tri_fusion(droite)
    
    # Fusionner les résultats
    return fusion(gauche_triee, droite_triee)

def fusion(gauche, droite):
    resultat = []
    i = j = 0
    
    # Fusionner tant que les deux listes ont des éléments
    while i < len(gauche) and j < len(droite):
        if gauche[i] <= droite[j]:
            resultat.append(gauche[i])
            i += 1
        else:
            resultat.append(droite[j])
            j += 1
    
    # Ajouter les éléments restants
    resultat.extend(gauche[i:])
    resultat.extend(droite[j:])
    
    return resultat

nombres = [38, 27, 43, 3, 9, 82, 10]
print(tri_fusion(nombres))  # [3, 9, 10, 27, 38, 43, 82]

# === SORTIE CONSOLE ===
# [3, 9, 10, 27, 38, 43, 82]
#
# Visualisation complète du tri fusion [38, 27, 43, 3, 9, 82, 10]:
#
# PHASE DE DIVISION (Divide):
# [38, 27, 43, 3, 9, 82, 10]
#         v diviser en 2
# [38, 27, 43] | [3, 9, 82, 10]
#     v              v
# [38] [27, 43] | [3, 9] [82, 10]
#  v    v         v       v
# [38] [27][43] [3][9] [82][10]  <- Listes de taille 1 (cas de base)
#
# PHASE DE FUSION (Conquer):
# [38] [27][43] [3][9] [82][10]
#  v    v fusion v  v fusion v
# [38] [27, 43]   [3, 9] [10, 82]
#   v fusion v      v fusion v
# [27, 38, 43]     [3, 9, 10, 82]
#      v fusion finale v
# [3, 9, 10, 27, 38, 43, 82]
#
# Détail de la fusion [27, 43] et [3, 9]:
# Étape 1: Comparer 27 vs 3 -> 3 est plus petit -> [3]
# Étape 2: Comparer 27 vs 9 -> 9 est plus petit -> [3, 9]
# Étape 3: Plus d'éléments à droite -> ajouter reste gauche -> [3, 9, 27, 43]
#
# Nombre d'opérations:
# - Divisions: log2(7) ≈ 3 niveaux
# - Fusions: 7 éléments à chaque niveau
# - Complexité totale: O(n log n) = O(7 × 3) = très efficace!

# === 2. TRI RAPIDE (QUICK SORT) ===

def tri_rapide(liste):
    # Cas de base
    if len(liste) <= 1:
        return liste
    
    # Choisir pivot (ici: premier élément)
    pivot = liste[0]
    
    # Partitionner
    gauche = [x for x in liste[1:] if x <= pivot]
    droite = [x for x in liste[1:] if x > pivot]
    
    # Récursion
    return tri_rapide(gauche) + [pivot] + tri_rapide(droite)

nombres = [38, 27, 43, 3, 9, 82, 10]
print(tri_rapide(nombres))  # [3, 9, 10, 27, 38, 43, 82]

# === 3. TOURS DE HANOÏ ===

def tours_hanoi(n, source, destination, auxiliaire):
    """
    Résout le problème des tours de Hanoï
    n: nombre de disques
    source: tour source
    destination: tour destination
    auxiliaire: tour auxiliaire
    """
    # Cas de base
    if n == 1:
        print(f"Déplacer disque 1 de {source} vers {destination}")
        return
    
    # Déplacer n-1 disques de source vers auxiliaire
    tours_hanoi(n - 1, source, auxiliaire, destination)
    
    # Déplacer le plus grand disque
    print(f"Déplacer disque {n} de {source} vers {destination}")
    
    # Déplacer n-1 disques de auxiliaire vers destination
    tours_hanoi(n - 1, auxiliaire, destination, source)

print("Tours de Hanoï avec 3 disques:")
tours_hanoi(3, 'A', 'C', 'B')

# === SORTIE CONSOLE ===
# Tours de Hanoï avec 3 disques:
# Déplacer disque 1 de A vers C
# Déplacer disque 2 de A vers B
# Déplacer disque 1 de C vers B
# Déplacer disque 3 de A vers C
# Déplacer disque 1 de B vers A
# Déplacer disque 2 de B vers C
# Déplacer disque 1 de A vers C
#
# Visualisation étape par étape (3 disques):
# État initial:
#   A      B      C
#  |||     |      |      A = Source
#  =|=     |      |      B = Auxiliaire
# ===== - | - - -|- - -  C = Destination
#
# Étape 1: Déplacer disque 1 de A vers C
#   A      B      C
#   |      |      |
#  =|=     |     |||
# ===== - | - - -|- - -
#
# Étape 2: Déplacer disque 2 de A vers B
#   A      B      C
#   |      |      |
#   |     =|=    |||
# ===== - | - - -|- - -
#
# Étape 3: Déplacer disque 1 de C vers B
#   A      B      C
#   |     |||     |
#   |     =|=     |
# ===== - | - - -|- - -
#
# Étape 4: Déplacer disque 3 de A vers C
#   A      B      C
#   |     |||     |
#   |     =|=     |
#   | - - -|- - ===== 
#
# Étape 5: Déplacer disque 1 de B vers A
#   A      B      C
#  |||     |      |
#   |     =|=     |
#   | - - -|- - ===== 
#
# Étape 6: Déplacer disque 2 de B vers C
#   A      B      C
#  |||     |     =|=
#   |      |      |
#   | - - -|- - ===== 
#
# Étape 7: Déplacer disque 1 de A vers C
#   A      B      C
#   |      |     |||
#   |      |     =|=
#   | - - -|- - ===== 
#
# Résolu! Tous les disques sont sur C.
#
# Analyse récursive:
# Pour déplacer 3 disques de A vers C:
# 1. Déplacer 2 disques de A vers B (utilise C comme auxiliaire)
# 2. Déplacer le disque 3 de A vers C
# 3. Déplacer 2 disques de B vers C (utilise A comme auxiliaire)
#
# Nombre de mouvements = 2^n - 1 = 2^3 - 1 = 7 mouvements

# === 4. GÉNÉRATION DE PARENTHÈSES VALIDES ===

def generer_parentheses(n):
    """
    Génère toutes les combinaisons valides de n paires de parenthèses
    """
    def backtrack(s, gauche, droite):
        # Cas de base: chaîne complète
        if len(s) == 2 * n:
            resultat.append(s)
            return
        
        # Ajouter parenthèse ouvrante si possible
        if gauche < n:
            backtrack(s + '(', gauche + 1, droite)
        
        # Ajouter parenthèse fermante si possible
        if droite < gauche:
            backtrack(s + ')', gauche, droite + 1)
    
    resultat = []
    backtrack('', 0, 0)
    return resultat

print(generer_parentheses(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']

# === SORTIE CONSOLE ===
# ['((()))', '(()())', '(())()', '()(())', '()()()']
#
# Explication: Pour n=3 paires, générer toutes combinaisons valides:
#
# 1. '((()))' : 3 ouvrantes puis 3 fermantes
#    État: ((( puis ))) -> valide [OK]
#
# 2. '(()())' : imbriqué + côte à côte
#    État: (( puis ) puis ( puis )) -> valide [OK]
#
# 3. '(())()' : groupe imbriqué + groupe simple
#    État: (( puis )) puis () -> valide [OK]
#
# 4. '()(())' : groupe simple + groupe imbriqué
#    État: () puis (( puis )) -> valide [OK]
#
# 5. '()()()' : 3 groupes simples côte à côte
#    État: () puis () puis () -> valide [OK]
#
# Arbre de décision (simplifié pour n=2):
#                    ""
#                    v ajouter '('
#                   "("
#                 /     \
#         "(("           "()"
#         v ')'          v '('
#       "(()"           "()("
#         v ')'          v ')'
#      "(())"          "()()"
#
# Règles de validité:
# - Nombre de '(' doit être ≤ n
# - Nombre de ')' doit être ≤ nombre de '('
# - Longueur finale = 2n
#
# Pour n=3, l'arbre explore ces branches:
# ( -> (( -> ((( -> ((() -> ((()) -> ((()))  <- Solution 1
#                     -> (()( -> (()() -> (()())  <- Solution 2
#           -> (() -> (()) -> (())( -> (())() <- Solution 3
#   -> () -> ()( -> ()(( -> ()(() -> ()(()) <- Solution 4
#             -> ()() -> ()()( -> ()()() <- Solution 5

# === 5. LABYRINTHE (PATH FINDING) ===

def trouver_chemin(labyrinthe, x, y, chemin=[]):
    """
    Trouve un chemin dans un labyrinthe
    0 = mur, 1 = chemin libre, 2 = destination
    """
    # Vérifier limites
    if (x < 0 or x >= len(labyrinthe) or 
        y < 0 or y >= len(labyrinthe[0])):
        return False
    
    # Vérifier si c'est un mur ou déjà visité
    if labyrinthe[x][y] == 0 or (x, y) in chemin:
        return False
    
    # Ajouter position au chemin
    chemin = chemin + [(x, y)]
    
    # Cas de base: destination trouvée
    if labyrinthe[x][y] == 2:
        return chemin
    
    # Essayer toutes les directions
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # droite, bas, gauche, haut
    
    for dx, dy in directions:
        resultat = trouver_chemin(labyrinthe, x + dx, y + dy, chemin)
        if resultat:
            return resultat
    
    return False

# Exemple de labyrinthe
maze = [
    [1, 0, 1, 1, 1],
    [1, 1, 1, 0, 1],
    [0, 0, 1, 0, 1],
    [1, 1, 1, 1, 2]
]

chemin_trouve = trouver_chemin(maze, 0, 0)
print(f"Chemin: {chemin_trouve}")

# === SORTIE CONSOLE ===
# Chemin: [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 3), (3, 4)]
#
# Visualisation du labyrinthe avec solution:
# Légende: 1 = passage, 0 = mur, 2 = destination, • = chemin trouvé
#
# Labyrinthe original:
#   0   1   2   3   4
# 0 [1] [0] [1] [1] [1]
# 1 [1] [1] [1] [0] [1]
# 2 [0] [0] [1] [0] [1]
# 3 [1] [1] [1] [1] [2]
#
# Chemin trouvé (marqué avec •):
#   0   1   2   3   4
# 0 [•] [0] [1] [1] [1]
# 1 [•] [•] [•] [0] [1]
# 2 [0] [0] [•] [0] [1]
# 3 [1] [1] [•] [•] [•]
#
# Explication étape par étape:
# Départ: (0,0)
#
# 1. De (0,0) essayer: droite -> (0,1)? Non (mur)
#                     bas    -> (1,0)? Oui! [OK]
#    Chemin: [(0,0), (1,0)]
#
# 2. De (1,0) essayer: droite -> (1,1)? Oui! [OK]
#    Chemin: [(0,0), (1,0), (1,1)]
#
# 3. De (1,1) essayer: droite -> (1,2)? Oui! [OK]
#    Chemin: [(0,0), (1,0), (1,1), (1,2)]
#
# 4. De (1,2) essayer: droite -> (1,3)? Non (mur)
#                     bas    -> (2,2)? Oui! [OK]
#    Chemin: [(0,0), (1,0), (1,1), (1,2), (2,2)]
#
# 5. De (2,2) essayer: droite -> (2,3)? Non (mur)
#                     bas    -> (3,2)? Oui! [OK]
#    Chemin: [(0,0), (1,0), (1,1), (1,2), (2,2), (3,2)]
#
# 6. De (3,2) essayer: droite -> (3,3)? Oui! [OK]
#    Chemin: [(0,0), (1,0), (1,1), (1,2), (2,2), (3,2), (3,3)]
#
# 7. De (3,3) essayer: droite -> (3,4)? Oui et c'est 2! DESTINATION! [BRAVO]
#    Chemin final: [(0,0), (1,0), (1,1), (1,2), (2,2), (3,2), (3,3), (3,4)]
#
# Note: Le chemin commence en (0,0) corrigé en (1,0) puis suit le parcours


[OK] RÉCURSION TERMINALE (TAIL RECURSION)

# Définition
# Une récursion est "terminale" quand l'appel récursif est la dernière opération
# Python ne l'optimise PAS automatiquement (contrairement à d'autres langages)

# [X] PAS terminale
def factorielle_classique(n):
    if n <= 1:
        return 1
    return n * factorielle_classique(n - 1)  # Multiplication APRÈS l'appel

# [OK] Terminale (avec accumulateur)
def factorielle_terminale(n, acc=1):
    if n <= 1:
        return acc
    return factorielle_terminale(n - 1, n * acc)  # Appel est la dernière opération

print(factorielle_terminale(5))  # 120

# === SORTIE CONSOLE ===
# 120
#
# Comparaison des exécutions:
#
# [X] RÉCURSION NON-TERMINALE (factorielle_classique):
# factorielle_classique(5)
#   = 5 * factorielle_classique(4)      <- doit attendre le résultat
#   = 5 * (4 * factorielle_classique(3)) <- doit attendre le résultat
#   = 5 * (4 * (3 * factorielle_classique(2)))
#   = 5 * (4 * (3 * (2 * factorielle_classique(1))))
#   = 5 * (4 * (3 * (2 * 1)))
#   = 5 * (4 * (3 * 2))
#   = 5 * (4 * 6)
#   = 5 * 24
#   = 120
#
# Pile mémoire (5 frames empilés):
# ┌─────────────────────┐
# │ fact_classique(5)   │ attend fact(4)
# ├─────────────────────┤
# │ fact_classique(4)   │ attend fact(3)
# ├─────────────────────┤
# │ fact_classique(3)   │ attend fact(2)
# ├─────────────────────┤
# │ fact_classique(2)   │ attend fact(1)
# ├─────────────────────┤
# │ fact_classique(1)   │ retourne 1
# └─────────────────────┘
#
# [OK] RÉCURSION TERMINALE (factorielle_terminale):
# factorielle_terminale(5, 1)
#   = factorielle_terminale(4, 5)     <- résultat partiel dans acc
#   = factorielle_terminale(3, 20)    <- résultat partiel dans acc
#   = factorielle_terminale(2, 60)    <- résultat partiel dans acc
#   = factorielle_terminale(1, 120)   <- résultat partiel dans acc
#   = 120                             <- retourne acc directement
#
# Pile mémoire (théoriquement 1 frame si optimisé):
# ┌─────────────────────┐
# │ fact_terminale(1,120)│ retourne 120
# └─────────────────────┘
# En Python: toujours 5 frames car pas de TCO
#
# Avantage: Le calcul est fait AVANT l'appel récursif
# - acc = 1, n = 5 -> prochain acc = 5×1 = 5
# - acc = 5, n = 4 -> prochain acc = 4×5 = 20
# - acc = 20, n = 3 -> prochain acc = 3×20 = 60
# - acc = 60, n = 2 -> prochain acc = 2×60 = 120
# - acc = 120, n = 1 -> cas de base, retourne 120

# === SOMME TERMINALE ===

def somme_terminale(n, acc=0):
    if n <= 0:
        return acc
    return somme_terminale(n - 1, acc + n)

print(somme_terminale(100))  # 5050

# === FIBONACCI TERMINALE ===

def fibonacci_terminale(n, a=0, b=1):
    if n == 0:
        return a
    if n == 1:
        return b
    return fibonacci_terminale(n - 1, b, a + b)

print(fibonacci_terminale(10))  # 55

# === INVERSER LISTE TERMINALE ===

def inverser_terminale(liste, acc=[]):
    if not liste:
        return acc
    return inverser_terminale(liste[1:], [liste[0]] + acc)

print(inverser_terminale([1, 2, 3, 4, 5]))  # [5, 4, 3, 2, 1]


[OK] CONVERSION RÉCURSION <-> ITÉRATION

# === Exemple 1: Factorielle ===

# Récursif
def fact_recursive(n):
    if n <= 1:
        return 1
    return n * fact_recursive(n - 1)

# Itératif
def fact_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# === Exemple 2: Fibonacci ===

# Récursif
def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

# Itératif
def fib_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# === Exemple 3: Somme liste ===

# Récursif
def sum_recursive(liste):
    if not liste:
        return 0
    return liste[0] + sum_recursive(liste[1:])

# Itératif
def sum_iterative(liste):
    total = 0
    for element in liste:
        total += element
    return total

# === Quand choisir quoi? ===

# Utiliser RÉCURSION quand:
# [OK] Le problème est naturellement récursif (arbres, fractales)
# [OK] La solution est plus claire et lisible
# [OK] Pas de problème de profondeur (petites données)
# [OK] Exemples: parcours d'arbre, backtracking, divide-and-conquer

# Utiliser ITÉRATION quand:
# [OK] Performance critique
# [OK] Grandes quantités de données
# [OK] Risque de dépassement de pile
# [OK] Solution itérative plus naturelle
# [OK] Exemples: parcours simple de liste, calculs répétitifs


[OK] RÉCURSION MUTUELLE

# Deux ou plusieurs fonctions s'appellent mutuellement

# === Exemple 1: Pair/Impair ===

def est_pair(n):
    if n == 0:
        return True
    return est_impair(n - 1)

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

print(est_pair(4))    # True
print(est_impair(7))  # True

# === Exemple 2: Parcours d'arbre alterné ===

def parcours_niveaux_impairs(node, niveau=1):
    if node is None:
        return
    
    if niveau % 2 == 1:
        print(node.valeur, end=" ")
    
    parcours_niveaux_pairs(node.gauche, niveau + 1)
    parcours_niveaux_pairs(node.droit, niveau + 1)

def parcours_niveaux_pairs(node, niveau=1):
    if node is None:
        return
    
    if niveau % 2 == 0:
        print(node.valeur, end=" ")
    
    parcours_niveaux_impairs(node.gauche, niveau + 1)
    parcours_niveaux_impairs(node.droit, niveau + 1)

# === Exemple 3: État de jeu ===

def joueur_a(points_a, points_b):
    print(f"Joueur A: {points_a} vs {points_b}")
    
    if points_a >= 10:
        print("Joueur A gagne!")
        return
    
    # Joueur A gagne un point
    joueur_b(points_a + 1, points_b)

def joueur_b(points_a, points_b):
    print(f"Joueur B: {points_a} vs {points_b}")
    
    if points_b >= 10:
        print("Joueur B gagne!")
        return
    
    # Joueur B gagne un point
    joueur_a(points_a, points_b + 1)


[OK] MÉMOÏSATION ET OPTIMISATION

# === 1. Mémoïsation manuelle ===

def fib_memo_manual(n, cache=None):
    # Initialiser cache
    if cache is None:
        cache = {}
    
    # Vérifier cache
    if n in cache:
        return cache[n]
    
    # Cas de base
    if n <= 1:
        return n
    
    # Calculer et stocker
    cache[n] = fib_memo_manual(n - 1, cache) + fib_memo_manual(n - 2, cache)
    return cache[n]

# === 2. Décorateur de mémoïsation ===

def memoize(func):
    cache = {}
    
    def wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    
    return wrapper

@memoize
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(100))  # Rapide!

# === 3. LRU Cache (Python standard) ===

from functools import lru_cache

@lru_cache(maxsize=128)
def calcul_lourd(n):
    if n <= 1:
        return n
    return calcul_lourd(n - 1) + calcul_lourd(n - 2)

# Voir statistiques du cache
print(calcul_lourd(50))
print(calcul_lourd.cache_info())
# CacheInfo(hits=48, misses=51, maxsize=128, currsize=51)

# Vider le cache
calcul_lourd.cache_clear()

# === 4. Cache avec expiration ===

import time

def cache_avec_ttl(ttl_seconds):
    def decorator(func):
        cache = {}
        timestamps = {}
        
        def wrapper(*args):
            current_time = time.time()
            
            # Vérifier si en cache et pas expiré
            if args in cache:
                if current_time - timestamps[args] < ttl_seconds:
                    return cache[args]
            
            # Calculer et cacher
            result = func(*args)
            cache[args] = result
            timestamps[args] = current_time
            
            return result
        
        return wrapper
    return decorator

@cache_avec_ttl(ttl_seconds=5)
def fonction_avec_cache(n):
    print(f"Calcul pour {n}")
    if n <= 1:
        return n
    return fonction_avec_cache(n - 1) + fonction_avec_cache(n - 2)


[OK] BACKTRACKING (RETOUR SUR TRACE)

# Technique pour explorer toutes les solutions possibles

# === 1. Problème du N-Queens (N Reines) ===

def n_queens(n):
    """Place n reines sur un échiquier n×n sans qu'elles s'attaquent"""
    
    def est_valide(board, row, col):
        # Vérifier colonne
        for i in range(row):
            if board[i] == col:
                return False
        
        # Vérifier diagonale gauche
        for i in range(row):
            if abs(board[i] - col) == abs(i - row):
                return False
        
        return True
    
    def backtrack(board, row):
        # Cas de base: toutes les reines placées
        if row == n:
            solutions.append(board[:])
            return
        
        # Essayer chaque colonne
        for col in range(n):
            if est_valide(board, row, col):
                board[row] = col
                backtrack(board, row + 1)
                board[row] = -1  # Backtrack
    
    solutions = []
    backtrack([-1] * n, 0)
    return solutions

# Trouver toutes les solutions pour 4 reines
solutions_4 = n_queens(4)
print(f"Nombre de solutions pour 4 reines: {len(solutions_4)}")

# === SORTIE CONSOLE ===
# Nombre de solutions pour 4 reines: 2
#
# Problème des N-Queens: Placer n reines sur un échiquier n×n
# sans qu'aucune ne puisse attaquer une autre
#
# Règles d'attaque des reines:
# - Ligne horizontale (même rangée)
# - Ligne verticale (même colonne)
# - Diagonales (-> <- -> <-)
#
# Solutions pour 4 reines (échiquier 4×4):
#
# Solution 1: [1, 3, 0, 2]
# Signification: board[row] = colonne où placer la reine
# - Rangée 0: reine en colonne 1
# - Rangée 1: reine en colonne 3
# - Rangée 2: reine en colonne 0
# - Rangée 3: reine en colonne 2
#
# Visualisation:
#   col 0  1  2  3
# row 0  .  Q  .  .
# row 1  .  .  .  Q
# row 2  Q  .  .  .
# row 3  .  .  Q  .
#
# Vérification: Aucune reine ne peut en attaquer une autre [OK]
#
# Solution 2: [2, 0, 3, 1]
#   col 0  1  2  3
# row 0  .  .  Q  .
# row 1  Q  .  .  .
# row 2  .  .  .  Q
# row 3  .  Q  .  .
#
# Exécution détaillée du backtracking:
#
# backtrack(board=[-1,-1,-1,-1], row=0)
#   Pour col de 0 à 3:
#   
#   col=0: Placer reine en (0,0)
#     est_valide(board, 0, 0) -> True [OK]
#     board[0] = 0: [0,-1,-1,-1]
#     backtrack(board, row=1)
#       col=0: Invalide (même colonne que reine en (0,0))
#       col=1: Invalide (diagonale avec (0,0))
#       col=2: Placer en (1,2)
#         board[1] = 2: [0,2,-1,-1]
#         backtrack(board, row=2)
#           col=0: Invalide (diagonale avec (1,2))
#           col=1: Placer en (2,1)? Non, diagonale avec (0,0)
#           col=2: Invalide (même colonne)
#           col=3: Invalide (diagonale)
#           Aucune position valide -> backtrack
#         board[1] = -1
#       col=3: Placer en (1,3)
#         board[1] = 3: [0,3,-1,-1]
#         backtrack(board, row=2)
#           col=1: Placer en (2,1)
#             board[2] = 1: [0,3,1,-1]
#             backtrack(board, row=3)
#               col=2: Invalide (diagonale)
#               col=3: Invalide (même colonne que (1,3))
#               Aucune position -> backtrack
#   
#   col=1: Placer reine en (0,1)
#     board[0] = 1: [1,-1,-1,-1]
#     backtrack(board, row=1)
#       col=0: Invalide (diagonale)
#       col=1: Invalide (même colonne)
#       col=2: Invalide (diagonale)
#       col=3: Placer en (1,3)
#         board[1] = 3: [1,3,-1,-1]
#         backtrack(board, row=2)
#           col=0: Placer en (2,0)
#             board[2] = 0: [1,3,0,-1]
#             backtrack(board, row=3)
#               col=2: Placer en (3,2)
#                 board[3] = 2: [1,3,0,2]
#                 row == 4 -> SOLUTION TROUVÉE! [OK]
#                 solutions.append([1,3,0,2])
#
#   ... continue pour col=2 et col=3 ...
#
#   col=2: Trouve solution [2,0,3,1] [OK]
#
# Résultat: 2 solutions pour n=4
#
# Statistiques pour différentes valeurs de n:
# n=1: 1 solution (triviale)
# n=2: 0 solution (impossible!)
# n=3: 0 solution (impossible!)
# n=4: 2 solutions [OK]
# n=5: 10 solutions
# n=6: 4 solutions
# n=7: 40 solutions
# n=8: 92 solutions (échiquier classique)
# n=10: 724 solutions
# n=12: 14,200 solutions
#
# Exemple de position invalide:
#   col 0  1  2  3
# row 0  Q  .  .  .
# row 1  .  Q  .  .  [X] (diagonale avec (0,0))
#
# Validation d'une position:
# Pour placer une reine en (row, col), vérifier:
# 1. Aucune reine sur la même colonne
# 2. Aucune reine sur les diagonales
#    - Diagonale -><-: abs(row1-row2) == abs(col1-col2)
#
# Complexité: O(n!) dans le pire cas
# Avec élagage intelligent: beaucoup plus rapide en pratique

# === 2. Sudoku Solver ===

def resoudre_sudoku(grille):
    """Résout une grille de Sudoku 9×9"""
    
    def est_valide(grille, row, col, num):
        # Vérifier ligne
        if num in grille[row]:
            return False
        
        # Vérifier colonne
        if num in [grille[i][col] for i in range(9)]:
            return False
        
        # Vérifier carré 3×3
        start_row, start_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(start_row, start_row + 3):
            for j in range(start_col, start_col + 3):
                if grille[i][j] == num:
                    return False
        
        return True
    
    def backtrack():
        # Trouver case vide
        for i in range(9):
            for j in range(9):
                if grille[i][j] == 0:
                    # Essayer chaque nombre
                    for num in range(1, 10):
                        if est_valide(grille, i, j, num):
                            grille[i][j] = num
                            
                            if backtrack():
                                return True
                            
                            grille[i][j] = 0  # Backtrack
                    
                    return False
        
        return True  # Grille complète
    
    backtrack()
    return grille

# === 3. Somme de sous-ensemble (Subset Sum) ===

def somme_sous_ensemble(nombres, cible):
    """Trouve tous les sous-ensembles dont la somme = cible"""
    
    def backtrack(index, chemin, somme_actuelle):
        # Cas de base: somme trouvée
        if somme_actuelle == cible:
            solutions.append(chemin[:])
            return
        
        # Cas de base: dépassement ou fin
        if somme_actuelle > cible or index >= len(nombres):
            return
        
        # Inclure élément courant
        chemin.append(nombres[index])
        backtrack(index + 1, chemin, somme_actuelle + nombres[index])
        chemin.pop()  # Backtrack
        
        # Ne pas inclure élément courant
        backtrack(index + 1, chemin, somme_actuelle)
    
    solutions = []
    backtrack(0, [], 0)
    return solutions

resultats = somme_sous_ensemble([2, 3, 5, 7], 10)
print(f"Sous-ensembles avec somme 10: {resultats}")
# [[2, 3, 5], [3, 7]]

# === SORTIE CONSOLE ===
# Sous-ensembles avec somme 10: [[2, 3, 5], [3, 7]]
#
# Problème: Trouver tous les sous-ensembles dont la somme = cible (10)
# Ensemble: [2, 3, 5, 7]
#
# Exécution détaillée avec backtracking:
#
# backtrack(index=0, chemin=[], somme=0)
#   Element: 2
#   
#   Branche 1: INCLURE 2
#     backtrack(1, [2], 2)
#       Element: 3
#       
#       Branche 1.1: INCLURE 3
#         backtrack(2, [2,3], 5)
#           Element: 5
#           
#           Branche 1.1.1: INCLURE 5
#             backtrack(3, [2,3,5], 10)
#               somme == 10 -> SOLUTION TROUVÉE! [[2,3,5]] [OK]
#               return
#           
#           Branche 1.1.2: NE PAS INCLURE 5
#             backtrack(3, [2,3], 5)
#               Element: 7
#               
#               INCLURE 7: somme=12 > 10 -> abandon
#               NE PAS INCLURE 7: fin liste
#       
#       Branche 1.2: NE PAS INCLURE 3
#         backtrack(2, [2], 2)
#           Element: 5
#           
#           INCLURE 5: backtrack(3, [2,5], 7)
#             Element: 7
#             INCLURE 7: somme=14 > 10 -> abandon
#             NE PAS INCLURE 7: fin
#           
#           NE PAS INCLURE 5: backtrack(3, [2], 2)
#             Element: 7
#             INCLURE 7: somme=9 < 10 -> pas solution
#             NE PAS INCLURE 7: fin
#   
#   Branche 2: NE PAS INCLURE 2
#     backtrack(1, [], 0)
#       Element: 3
#       
#       Branche 2.1: INCLURE 3
#         backtrack(2, [3], 3)
#           Element: 5
#           
#           INCLURE 5: somme=8 < 10 -> continue
#             backtrack(3, [3,5], 8)
#               Element: 7
#               INCLURE 7: somme=15 > 10 -> abandon
#               NE PAS INCLURE 7: fin
#           
#           NE PAS INCLURE 5: backtrack(3, [3], 3)
#             Element: 7
#             
#             INCLURE 7: backtrack(4, [3,7], 10)
#               somme == 10 -> SOLUTION TROUVÉE! [[3,7]] [OK]
#               return
#             
#             NE PAS INCLURE 7: fin
#       
#       Branche 2.2: NE PAS INCLURE 3
#         ... continue exploration ...
#
# Résultat: [[2, 3, 5], [3, 7]]
#
# Arbre de décision complet:
#                        []
#                    /        \
#                [2]            []
#              /    \         /    \
#          [2,3]    [2]    [3]      []
#          /   \    / \    / \      / \
#      [2,3,5] [2,3] ...  [3,7] [3,5] ...
#         |              [OK]    |
#      somme=10             somme=10
#         [OK]
#
# Vérification des solutions:
# Solution 1: [2, 3, 5]
#   2 + 3 + 5 = 10 [OK]
#
# Solution 2: [3, 7]
#   3 + 7 = 10 [OK]
#
# Sous-ensembles testés (partiels):
# [] -> somme=0
# [2] -> somme=2
# [2,3] -> somme=5
# [2,3,5] -> somme=10 [OK] SOLUTION
# [2,3,5,7] -> somme=17 > 10 [X] abandon
# [2,3,7] -> somme=12 > 10 [X]
# [2,5] -> somme=7
# [2,5,7] -> somme=14 > 10 [X]
# [2,7] -> somme=9
# [3] -> somme=3
# [3,5] -> somme=8
# [3,5,7] -> somme=15 > 10 [X]
# [3,7] -> somme=10 [OK] SOLUTION
# [5] -> somme=5
# [5,7] -> somme=12 > 10 [X]
# [7] -> somme=7
#
# Optimisation: Si somme > cible, on arrête (élagage)
# Sans élagage: teste 2^4 = 16 sous-ensembles
# Avec élagage: teste moins de combinaisons
#
# Autre exemple avec [1, 2, 3, 4], cible=7:
# Solutions: [[1,2,4], [3,4]]
# 1+2+4 = 7 [OK]
# 3+4 = 7 [OK]

# === 4. Génération de combinaisons ===

def combinaisons(n, k):
    """Génère toutes les combinaisons de k nombres parmi 1..n"""
    
    def backtrack(debut, chemin):
        # Cas de base: k éléments trouvés
        if len(chemin) == k:
            solutions.append(chemin[:])
            return
        
        # Essayer chaque nombre
        for i in range(debut, n + 1):
            chemin.append(i)
            backtrack(i + 1, chemin)
            chemin.pop()  # Backtrack
    
    solutions = []
    backtrack(1, [])
    return solutions

print(combinaisons(5, 3))
# [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], ...]

# === SORTIE CONSOLE ===
# [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], 
#  [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
#
# Problème: Générer toutes les combinaisons de k=3 éléments parmi n=5
# C(5,3) = 5!/(3!×2!) = 10 combinaisons
#
# Exécution détaillée de combinaisons(5, 3):
# Objectif: Choisir 3 nombres parmi {1, 2, 3, 4, 5}
#
# backtrack(debut=1, chemin=[])
#   Pour i de 1 à 5:
#   
#   i=1: Ajouter 1
#     backtrack(debut=2, chemin=[1])
#       Pour i de 2 à 5:
#       
#       i=2: Ajouter 2
#         backtrack(debut=3, chemin=[1,2])
#           Pour i de 3 à 5:
#           
#           i=3: Ajouter 3
#             backtrack(debut=4, chemin=[1,2,3])
#               len([1,2,3]) == 3 -> SOLUTION [[1,2,3]] [OK]
#               return
#           
#           i=4: Ajouter 4
#             backtrack(debut=5, chemin=[1,2,4])
#               len([1,2,4]) == 3 -> SOLUTION [[1,2,4]] [OK]
#               return
#           
#           i=5: Ajouter 5
#             backtrack(debut=6, chemin=[1,2,5])
#               len([1,2,5]) == 3 -> SOLUTION [[1,2,5]] [OK]
#               return
#       
#       i=3: Ajouter 3
#         backtrack(debut=4, chemin=[1,3])
#           Pour i de 4 à 5:
#           
#           i=4: Ajouter 4
#             backtrack(debut=5, chemin=[1,3,4])
#               len([1,3,4]) == 3 -> SOLUTION [[1,3,4]] [OK]
#           
#           i=5: Ajouter 5
#             backtrack(debut=6, chemin=[1,3,5])
#               len([1,3,5]) == 3 -> SOLUTION [[1,3,5]] [OK]
#       
#       i=4: Ajouter 4
#         backtrack(debut=5, chemin=[1,4])
#           i=5: Ajouter 5
#             backtrack(debut=6, chemin=[1,4,5])
#               len([1,4,5]) == 3 -> SOLUTION [[1,4,5]] [OK]
#   
#   i=2: Ajouter 2
#     backtrack(debut=3, chemin=[2])
#       i=3: Ajouter 3
#         backtrack(debut=4, chemin=[2,3])
#           i=4: Ajouter 4
#             backtrack(debut=5, chemin=[2,3,4])
#               len([2,3,4]) == 3 -> SOLUTION [[2,3,4]] [OK]
#           i=5: Ajouter 5
#             backtrack(debut=6, chemin=[2,3,5])
#               len([2,3,5]) == 3 -> SOLUTION [[2,3,5]] [OK]
#       
#       i=4: Ajouter 4
#         backtrack(debut=5, chemin=[2,4])
#           i=5: Ajouter 5
#             backtrack(debut=6, chemin=[2,4,5])
#               len([2,4,5]) == 3 -> SOLUTION [[2,4,5]] [OK]
#   
#   i=3: Ajouter 3
#     backtrack(debut=4, chemin=[3])
#       i=4: Ajouter 4
#         backtrack(debut=5, chemin=[3,4])
#           i=5: Ajouter 5
#             backtrack(debut=6, chemin=[3,4,5])
#               len([3,4,5]) == 3 -> SOLUTION [[3,4,5]] [OK]
#
# Résultat: 10 combinaisons
#
# Visualisation en arbre (partiel):
#                      []
#           /      /      \      \      \
#        [1]    [2]     [3]    [4]    [5]
#       / | \   / | \    |      |
#     [1,2][1,3][1,4] [2,3][2,4][3,4]
#     /|\  /|\  |    /|\  |     |
# [1,2,3] ...  [1,4,5] ...  [3,4,5]
#   [OK]                           [OK]
#
# Les 10 combinaisons:
# 1. [1, 2, 3] - commence par 1, puis 2, puis 3
# 2. [1, 2, 4] - commence par 1, puis 2, puis 4
# 3. [1, 2, 5] - commence par 1, puis 2, puis 5
# 4. [1, 3, 4] - commence par 1, puis 3, puis 4
# 5. [1, 3, 5] - commence par 1, puis 3, puis 5
# 6. [1, 4, 5] - commence par 1, puis 4, puis 5
# 7. [2, 3, 4] - commence par 2, puis 3, puis 4
# 8. [2, 3, 5] - commence par 2, puis 3, puis 5
# 9. [2, 4, 5] - commence par 2, puis 4, puis 5
# 10. [3, 4, 5] - commence par 3, puis 4, puis 5
#
# Formule: C(n, k) = n! / (k! × (n-k)!)
# C(5, 3) = 5! / (3! × 2!) = 120 / (6 × 2) = 120 / 12 = 10 [OK]
#
# Différence combinaison vs permutation:
# Combinaison: l'ordre ne compte PAS
#   C(5,3) = 10: [1,2,3] = [2,1,3] = [3,2,1]
# Permutation: l'ordre compte
#   P(5,3) = 60: [1,2,3] ≠ [2,1,3] ≠ [3,2,1]
#
# Exemples avec autres valeurs:
# C(4, 2) = 4!/(2!×2!) = 6 combinaisons
#   [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
#
# C(6, 2) = 6!/(2!×4!) = 15 combinaisons
# C(10, 5) = 252 combinaisons
#
# Application: Loto, poker, loteries
# Loto 6/49: choisir 6 numéros parmi 49
# C(49, 6) = 13,983,816 combinaisons possibles!


[OK] RÉCURSION AVEC GÉNÉRATEURS

# Utiliser yield pour générer valeurs récursivement

# === 1. Générer nombres ===

def compter_recursive(n):
    if n <= 0:
        return
    yield n
    yield from compter_recursive(n - 1)

for num in compter_recursive(5):
    print(num, end=" ")  # 5 4 3 2 1

# === SORTIE CONSOLE ===
# 5 4 3 2 1
#
# Comment fonctionne yield dans la récursion:
#
# compter_recursive(5)
#   yield 5          <- produit 5
#   yield from compter_recursive(4)
#     yield 4        <- produit 4
#     yield from compter_recursive(3)
#       yield 3      <- produit 3
#       yield from compter_recursive(2)
#         yield 2    <- produit 2
#         yield from compter_recursive(1)
#           yield 1  <- produit 1
#           yield from compter_recursive(0)
#             return <- cas de base, arrête
#
# Avantage des générateurs récursifs:
# - Paresseux (lazy): génère valeurs une par une
# - Économie de mémoire: pas besoin de stocker toute la liste
# - Peut générer séquences infinies
#
# Comparaison avec liste normale:
# Liste: compter(5) -> [5,4,3,2,1] -> stocke tout en mémoire
# Générateur: compter_gen(5) -> génère 5, puis 4, puis 3... à la demande

# === 2. Parcours d'arbre en profondeur ===

def parcours_arbre_generateur(node):
    if node is None:
        return
    
    yield node.valeur
    yield from parcours_arbre_generateur(node.gauche)
    yield from parcours_arbre_generateur(node.droit)

# Utilisation
# for valeur in parcours_arbre_generateur(root):
#     print(valeur)

# === 3. Générer permutations ===

def permutations_gen(liste):
    if len(liste) <= 1:
        yield liste
    else:
        for i in range(len(liste)):
            for perm in permutations_gen(liste[:i] + liste[i+1:]):
                yield [liste[i]] + perm

for perm in permutations_gen([1, 2, 3]):
    print(perm)

# === SORTIE CONSOLE ===
# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 1, 2]
# [3, 2, 1]
#
# Avantage du générateur: Produit les valeurs à la demande (lazy evaluation)
# au lieu de créer toute la liste en mémoire
#
# Exécution détaillée de permutations_gen([1, 2, 3]):
#
# Premier appel à next():
#   permutations_gen([1, 2, 3])
#     len([1,2,3]) > 1 -> pas cas de base
#     i=0: liste[0]=1, reste=[2,3]
#       Pour perm in permutations_gen([2, 3]):
#         permutations_gen([2, 3])
#           len([2,3]) > 1 -> pas cas de base
#           i=0: liste[0]=2, reste=[3]
#             Pour perm in permutations_gen([3]):
#               permutations_gen([3])
#                 len([3]) <= 1 -> cas de base
#                 yield [3] <- Premier yield!
#             perm=[3] -> yield [2] + [3] = [2, 3]
#           i=1: liste[1]=3, reste=[2]
#             Pour perm in permutations_gen([2]):
#               yield [2]
#             perm=[2] -> yield [3] + [2] = [3, 2]
#       perm=[2,3] -> yield [1] + [2, 3] = [1, 2, 3] [OK] PRODUIT
#
# Deuxième appel à next():
#   Continue où on s'était arrêté...
#   perm=[3,2] -> yield [1] + [3, 2] = [1, 3, 2] [OK] PRODUIT
#
# Troisième appel à next():
#   i=1: liste[1]=2, reste=[1,3]
#     Pour perm in permutations_gen([1, 3]):
#       i=0: yield [1, 3]
#     perm=[1,3] -> yield [2] + [1, 3] = [2, 1, 3] [OK] PRODUIT
#
# ... et ainsi de suite pour les 6 permutations
#
# Comparaison générateur vs liste:
#
# Version liste (non-lazy):
# def permutations_list(liste):
#     if len(liste) <= 1:
#         return [liste]
#     result = []
#     for i in range(len(liste)):
#         for perm in permutations_list(reste):
#             result.append([liste[i]] + perm)
#     return result
#
# perms = permutations_list([1,2,3])  # Calcule TOUT immédiatement
# # Mémoire: stocke [[1,2,3], [1,3,2], ..., [3,2,1]] (6 listes)
# for p in perms:
#     print(p)
#
# Version générateur (lazy):
# for perm in permutations_gen([1,2,3]):  # Génère à la demande
#     print(perm)  # Affiche puis oublie, économise mémoire
#
# Avantages du générateur:
# 1. Mémoire: O(n) au lieu de O(n! × n)
#    - Pour [1..10]: économise ~36 millions de listes!
# 2. Commence immédiatement: pas besoin d'attendre toutes les permutations
# 3. Peut arrêter tôt:
#    for perm in permutations_gen([1,2,3,4,5]):
#        print(perm)
#        if condition:
#            break  # Arrête sans générer les 120 permutations
#
# Trace d'exécution avec yield:
# État 1: yield [1,2,3] -> pause -> for loop affiche
# État 2: reprend après yield -> continue boucle
# État 3: yield [1,3,2] -> pause -> for loop affiche
# État 4: reprend après yield -> continue
# ... et ainsi de suite
#
# Visualisation de la pile pour le premier yield:
# permutations_gen([1,2,3]) <- En attente
#   ├─ permutations_gen([2,3]) <- En attente
#   │   └─ permutations_gen([3]) <- yield [3]
#   │       v remonte
#   │   <- yield [2,3]
#   v remonte
# <- yield [1,2,3] [OK] LIVRÉ AU FOR LOOP
#
# Utilisation avancée:
# gen = permutations_gen([1, 2, 3])
# print(next(gen))  # [1, 2, 3]
# print(next(gen))  # [1, 3, 2]
# # Peut itérer manuellement, stopper, reprendre
#
# Application pratique:
# - Traiter d'énormes ensembles de permutations
# - Pipeline de transformations paresseuses
# - Recherche avec early termination

# === 4. Parcours de répertoires ===

import os

def parcourir_dossiers(chemin):
    """Générateur récursif pour parcourir tous les fichiers"""
    try:
        for element in os.listdir(chemin):
            chemin_complet = os.path.join(chemin, element)
            
            if os.path.isfile(chemin_complet):
                yield chemin_complet
            elif os.path.isdir(chemin_complet):
                yield from parcourir_dossiers(chemin_complet)
    except PermissionError:
        pass

# Utilisation
# for fichier in parcourir_dossiers('/chemin'):
#     print(fichier)


[OK] PATTERNS RÉCURSIFS AVANCÉS

# === 1. Divide and Conquer (Diviser pour régner) ===

def trouver_max_divide_conquer(liste, debut, fin):
    """Trouve le maximum en divisant la liste"""
    
    # Cas de base: un seul élément
    if debut == fin:
        return liste[debut]
    
    # Cas de base: deux éléments
    if fin == debut + 1:
        return max(liste[debut], liste[fin])
    
    # Diviser
    milieu = (debut + fin) // 2
    
    # Conquérir
    max_gauche = trouver_max_divide_conquer(liste, debut, milieu)
    max_droite = trouver_max_divide_conquer(liste, milieu + 1, fin)
    
    # Combiner
    return max(max_gauche, max_droite)

nombres = [3, 41, 52, 26, 38, 57, 9, 49]
print(trouver_max_divide_conquer(nombres, 0, len(nombres) - 1))  # 57

# === 2. Programmation Dynamique (Top-Down) ===

def longueur_plus_longue_sous_sequence(s1, s2, memo=None):
    """Trouve la longueur de la plus longue sous-séquence commune (LCS)"""
    
    if memo is None:
        memo = {}
    
    # Créer clé unique
    key = (len(s1), len(s2))
    
    if key in memo:
        return memo[key]
    
    # Cas de base
    if not s1 or not s2:
        return 0
    
    # Cas récursifs
    if s1[0] == s2[0]:
        # Caractères identiques: inclure et continuer
        result = 1 + longueur_plus_longue_sous_sequence(s1[1:], s2[1:], memo)
    else:
        # Caractères différents: essayer les deux options
        option1 = longueur_plus_longue_sous_sequence(s1[1:], s2, memo)
        option2 = longueur_plus_longue_sous_sequence(s1, s2[1:], memo)
        result = max(option1, option2)
    
    memo[key] = result
    return result

print(longueur_plus_longue_sous_sequence("ABCDEF", "ADBEF"))  # 4 (ABEF)

# === 3. Tree Traversal (Parcours d'arbre) ===

# In-order (gauche, racine, droite)
def inorder(node):
    if node is None:
        return []
    return inorder(node.gauche) + [node.valeur] + inorder(node.droit)

# Pre-order (racine, gauche, droite)
def preorder(node):
    if node is None:
        return []
    return [node.valeur] + preorder(node.gauche) + preorder(node.droit)

# Post-order (gauche, droite, racine)
def postorder(node):
    if node is None:
        return []
    return postorder(node.gauche) + postorder(node.droit) + [node.valeur]

# === 4. Graph Traversal (Parcours de graphe) ===

def dfs_graphe(graphe, noeud, visite=None):
    """Parcours en profondeur d'un graphe"""
    
    if visite is None:
        visite = set()
    
    if noeud in visite:
        return
    
    print(noeud, end=" ")
    visite.add(noeud)
    
    for voisin in graphe.get(noeud, []):
        dfs_graphe(graphe, voisin, visite)

# Exemple de graphe (adjacence)
graphe = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print("DFS depuis A:")
dfs_graphe(graphe, 'A')  # A B D E F C

# === SORTIE CONSOLE ===
# DFS depuis A:
# A B D E F C
#
# Structure du graphe (rappel):
# graphe = {
#   'A': ['B', 'C'],      A est connecté à B et C
#   'B': ['D', 'E'],      B est connecté à D et E
#   'C': ['F'],           C est connecté à F
#   'D': [],              D n'a pas de voisins
#   'E': ['F'],           E est connecté à F
#   'F': []               F n'a pas de voisins
# }
#
# Visualisation du graphe:
#       A
#      / \
#     B   C
#    / \   \
#   D   E   F
#        \ /
#        (E->F, C->F : F a deux parents)
#
# Exécution détaillée de dfs_graphe(graphe, 'A'):
# visite = set()
#
# Appel 1: dfs_graphe(graphe, 'A', visite={})
#   'A' not in visite [OK]
#   print('A')           <- Affiche A
#   visite.add('A')      visite = {'A'}
#   
#   Pour voisin in ['B', 'C']:
#     
#     Appel 2: dfs_graphe(graphe, 'B', visite={'A'})
#       'B' not in visite [OK]
#       print('B')       <- Affiche B
#       visite.add('B')  visite = {'A', 'B'}
#       
#       Pour voisin in ['D', 'E']:
#         
#         Appel 3: dfs_graphe(graphe, 'D', visite={'A','B'})
#           'D' not in visite [OK]
#           print('D')   <- Affiche D
#           visite.add('D')  visite = {'A', 'B', 'D'}
#           
#           Pour voisin in []:
#             (pas de voisins)
#           return
#         
#         Appel 4: dfs_graphe(graphe, 'E', visite={'A','B','D'})
#           'E' not in visite [OK]
#           print('E')   <- Affiche E
#           visite.add('E')  visite = {'A', 'B', 'D', 'E'}
#           
#           Pour voisin in ['F']:
#             
#             Appel 5: dfs_graphe(graphe, 'F', visite={'A','B','D','E'})
#               'F' not in visite [OK]
#               print('F')   <- Affiche F
#               visite.add('F')  visite = {'A','B','D','E','F'}
#               
#               Pour voisin in []:
#                 (pas de voisins)
#               return
#           
#           return
#       
#       return
#     
#     Appel 6: dfs_graphe(graphe, 'C', visite={'A','B','D','E','F'})
#       'C' not in visite [OK]
#       print('C')       <- Affiche C
#       visite.add('C')  visite = {'A','B','D','E','F','C'}
#       
#       Pour voisin in ['F']:
#         
#         dfs_graphe(graphe, 'F', visite={'A','B','D','E','F','C'})
#           'F' in visite -> return immédiatement (déjà visité!)
#       
#       return
#   
#   return
#
# Résultat affiché: A B D E F C
#
# Ordre de visite expliqué:
# 1. A - nœud de départ
# 2. B - premier voisin de A
# 3. D - premier voisin de B (feuille, remonte)
# 4. E - second voisin de B
# 5. F - voisin de E (première fois qu'on le visite)
# 6. C - second voisin de A
#    (F déjà visité via E, donc on le saute)
#
# Trace avec profondeur d'indentation:
# dfs_graphe('A')                  depth=0
#   print('A')
#   dfs_graphe('B')                depth=1
#     print('B')
#     dfs_graphe('D')              depth=2
#       print('D')
#       (pas de voisins)
#     dfs_graphe('E')              depth=2
#       print('E')
#       dfs_graphe('F')            depth=3
#         print('F')
#         (pas de voisins)
#   dfs_graphe('C')                depth=1
#     print('C')
#     dfs_graphe('F')              depth=2
#       (déjà visité, skip)
#
# Visualisation du parcours avec ordre:
#       A(1)
#      /    \
#   B(2)    C(6)
#   / \      \
# D(3) E(4)  F(5) <- déjà visité quand C essaie de le visiter
#       \   /
#        F
#
# État du set visite à chaque étape:
# Étape 1: {} -> {'A'} après visite de A
# Étape 2: {'A'} -> {'A','B'} après visite de B
# Étape 3: {'A','B'} -> {'A','B','D'} après visite de D
# Étape 4: {'A','B','D'} -> {'A','B','D','E'} après visite de E
# Étape 5: {'A','B','D','E'} -> {'A','B','D','E','F'} après visite de F
# Étape 6: {'A','B','D','E','F'} -> {'A','B','D','E','F','C'} après visite de C
#
# Comparaison avec BFS (parcours en largeur):
# DFS (profondeur): A B D E F C (va au plus profond d'abord)
# BFS (largeur): A B C D E F (visite niveau par niveau)
#
# Autre exemple de départ:
# dfs_graphe(graphe, 'B') -> B D E F
# dfs_graphe(graphe, 'C') -> C F
#
# Propriétés du DFS:
# - Utilise la pile (récursion)
# - Explore un chemin jusqu'au bout
# - Complexité: O(V + E) où V=sommets, E=arêtes
# - Mémoire: O(V) pour le set visite
#
# Applications:
# - Détecter cycles dans un graphe
# - Tri topologique
# - Trouver composantes connexes
# - Résoudre labyrinthes
# - Parcourir arbres de fichiers


[OK] ERREURS COURANTES ET SOLUTIONS

# === 1. Oublier le cas de base ===

# [X] ERREUR
def mauvais(n):
    return n + mauvais(n - 1)  # RecursionError!

# [OK] CORRECT
def bon(n):
    if n <= 0:  # CAS DE BASE
        return 0
    return n + bon(n - 1)

# === 2. Cas de base incorrect ===

# [X] ERREUR - Cas de base jamais atteint
def mauvais_factorielle(n):
    if n == 1:  # Problème si n = 0
        return 1
    return n * mauvais_factorielle(n - 1)

# [OK] CORRECT
def bon_factorielle(n):
    if n <= 1:  # Gère 0 et 1
        return 1
    return n * bon_factorielle(n - 1)

# === 3. Modification de paramètre mutable ===

# [X] PROBLÈME
def ajouter_liste(liste, element):
    if element <= 0:
        return liste
    liste.append(element)  # Modifie liste originale!
    return ajouter_liste(liste, element - 1)

ma_liste = []
result = ajouter_liste(ma_liste, 3)
print(ma_liste)  # Modifiée!

# [OK] SOLUTION 1: Copier
def ajouter_liste_safe(liste, element):
    if element <= 0:
        return liste
    nouvelle_liste = liste + [element]  # Nouvelle liste
    return ajouter_liste_safe(nouvelle_liste, element - 1)

# [OK] SOLUTION 2: Paramètre par défaut
def ajouter_liste_v2(element, liste=None):
    if liste is None:
        liste = []
    if element <= 0:
        return liste
    return ajouter_liste_v2(element - 1, liste + [element])

# === 4. Récursion trop profonde ===

# [X] ERREUR
def somme_profonde(n):
    if n <= 0:
        return 0
    return n + somme_profonde(n - 1)

# somme_profonde(10000)  # RecursionError!

# [OK] SOLUTION 1: Augmenter limite (temporaire)
import sys
sys.setrecursionlimit(15000)

# [OK] SOLUTION 2: Utiliser itération
def somme_iterative(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

# [OK] SOLUTION 3: Formule mathématique
def somme_formule(n):
    return n * (n + 1) // 2

# === 5. Slicing inefficace ===

# [X] INEFFICACE - Copie la liste à chaque appel
def somme_slice(liste):
    if not liste:
        return 0
    return liste[0] + somme_slice(liste[1:])  # O(n) à chaque fois!

# [OK] EFFICACE - Utiliser index
def somme_index(liste, i=0):
    if i >= len(liste):
        return 0
    return liste[i] + somme_index(liste, i + 1)

# === 6. Pas de retour de valeur ===

# [X] ERREUR
def mauvais_max(liste):
    if len(liste) == 1:
        return liste[0]
    max_reste = mauvais_max(liste[1:])
    if liste[0] > max_reste:
        liste[0]  # Oups! Pas de return

# [OK] CORRECT
def bon_max(liste):
    if len(liste) == 1:
        return liste[0]
    max_reste = bon_max(liste[1:])
    return liste[0] if liste[0] > max_reste else max_reste


[OK] DEBUGGING ET VISUALISATION

# === 1. Tracer les appels ===

def factorielle_trace(n, indent=0):
    """Factorielle avec trace d'exécution"""
    prefix = "  " * indent
    print(f"{prefix}-> factorielle({n})")
    
    if n <= 1:
        print(f"{prefix}<- retourne 1")
        return 1
    
    result = n * factorielle_trace(n - 1, indent + 1)
    print(f"{prefix}<- retourne {result}")
    return result

print("Trace de factorielle(4):")
factorielle_trace(4)

# === SORTIE CONSOLE ===
# Trace de factorielle(4):
# -> factorielle(4)
#   -> factorielle(3)
#     -> factorielle(2)
#       -> factorielle(1)
#       <- retourne 1
#     <- retourne 2
#   <- retourne 6
# <- retourne 24
#
# Explication visuelle avec indentation:
# Niveau 0: -> factorielle(4) appelé
# Niveau 1:   -> factorielle(3) appelé (indent=1)
# Niveau 2:     -> factorielle(2) appelé (indent=2)
# Niveau 3:       -> factorielle(1) appelé (indent=3)
# Niveau 3:       <- retourne 1 (cas de base)
# Niveau 2:     <- retourne 2 (2 × 1)
# Niveau 1:   <- retourne 6 (3 × 2)
# Niveau 0: <- retourne 24 (4 × 6)
#
# Chaque niveau d'indentation représente la profondeur dans la pile:
# "" = profondeur 0
# "  " = profondeur 1 (2 espaces)
# "    " = profondeur 2 (4 espaces)
# "      " = profondeur 3 (6 espaces)
#
# Chronologie:
# Temps 1: Descente vers le cas de base (->)
# Temps 2: Remontée avec calculs (<-)

# === 2. Compter les appels ===

def fibonacci_compte(n, compteur=None):
    """Fibonacci qui compte le nombre d'appels"""
    if compteur is None:
        compteur = {'count': 0}
    
    compteur['count'] += 1
    
    if n <= 1:
        return n
    
    return fibonacci_compte(n - 1, compteur) + fibonacci_compte(n - 2, compteur)

compteur = {'count': 0}
result = fibonacci_compte(10, compteur)
print(f"Résultat: {result}, Appels: {compteur['count']}")  # 177 appels!

# === SORTIE CONSOLE ===
# Résultat: 55, Appels: 177
#
# Analyse détaillée des 177 appels pour fibonacci(10):
#
# fibonacci(10) nécessite:
# - fibonacci(9) et fibonacci(8)
#
# fibonacci(9) nécessite:
# - fibonacci(8) et fibonacci(7)
#
# fibonacci(8) nécessite:
# - fibonacci(7) et fibonacci(6)
# ... et ainsi de suite
#
# Statistiques d'appels:
# fib(0) appelé: 55 fois
# fib(1) appelé: 89 fois
# fib(2) appelé: 55 fois
# fib(3) appelé: 34 fois
# fib(4) appelé: 21 fois
# fib(5) appelé: 13 fois
# fib(6) appelé: 8 fois
# fib(7) appelé: 5 fois
# fib(8) appelé: 3 fois
# fib(9) appelé: 2 fois
# fib(10) appelé: 1 fois
# TOTAL: 177 appels
#
# Visualisation partielle de l'arbre pour fib(5):
#                       fib(5)
#                      /      \
#                 fib(4)        fib(3)
#                /     \        /     \
#           fib(3)   fib(2)  fib(2)  fib(1)
#           /   \    /   \   /   \      |
#       fib(2) fib(1) 1  0  1   0      1
#       /   \    |
#      1    0    1
#
# Appels pour fib(5) = 15
# Appels pour fib(10) = 177 (croissance exponentielle!)
#
# Avec mémoïsation:
fibonacci_efficace(10)
print(f"Cache: {fibonacci_efficace.cache_info()}")
# Cache: CacheInfo(hits=8, misses=11, maxsize=None, currsize=11)
#
# Avec mémoïsation: seulement 11 appels uniques + 8 hits cache = 19 opérations
# Sans mémoïsation: 177 appels
# Gain: 177/19 ≈ 9.3x plus rapide!

# === 3. Décorateur de debug ===

def debug_recursive(func):
    """Décorateur pour tracer les appels récursifs"""
    def wrapper(n, _depth=0):
        indent = "  " * _depth
        print(f"{indent}-> {func.__name__}({n})")
        
        result = func(n)
        
        print(f"{indent}<- {result}")
        return result
    
    return wrapper

@debug_recursive
def somme_debug(n):
    if n <= 0:
        return 0
    return n + somme_debug(n - 1)

# === 4. Visualiser l'arbre d'appels ===

def visualiser_arbre_appels(func, n, prefix="", is_last=True):
    """Visualise l'arbre des appels récursifs"""
    connector = "└── " if is_last else "├── "
    print(f"{prefix}{connector}{func.__name__}({n})")
    
    if n <= 0:
        return
    
    new_prefix = prefix + ("    " if is_last else "│   ")
    
    # Simuler les appels (adapté pour Fibonacci)
    if n > 1:
        visualiser_arbre_appels(func, n - 1, new_prefix, False)
        visualiser_arbre_appels(func, n - 2, new_prefix, True)

print("\nArbre d'appels pour fibonacci(4):")
visualiser_arbre_appels(fibonacci, 4)

# === SORTIE CONSOLE ===
# Arbre d'appels pour fibonacci(4):
# └── fibonacci(4)
#     ├── fibonacci(3)
#     │   ├── fibonacci(2)
#     │   │   ├── fibonacci(1)
#     │   │   └── fibonacci(0)
#     │   └── fibonacci(1)
#     └── fibonacci(2)
#         ├── fibonacci(1)
#         └── fibonacci(0)
#
# Explication de la structure:
# └── = dernier élément d'un niveau
# ├── = élément avec un frère suivant
# │   = ligne de continuation verticale
#     = espacement
#
# Lecture de l'arbre:
# fibonacci(4) se divise en:
#   1. fibonacci(3) qui se divise en:
#      - fibonacci(2) qui se divise en:
#        * fibonacci(1) -> retourne 1 (cas de base)
#        * fibonacci(0) -> retourne 0 (cas de base)
#      - fibonacci(1) -> retourne 1 (cas de base)
#   2. fibonacci(2) qui se divise en:
#      - fibonacci(1) -> retourne 1 (cas de base)
#      - fibonacci(0) -> retourne 0 (cas de base)
#
# Calcul des retours (de bas en haut):
# fib(0) = 0
# fib(1) = 1
# fib(2) = fib(1) + fib(0) = 1 + 0 = 1
# fib(2) = fib(1) + fib(0) = 1 + 0 = 1 (recalculé!)
# fib(3) = fib(2) + fib(1) = 1 + 1 = 2
# fib(4) = fib(3) + fib(2) = 2 + 1 = 3
#
# Note: fib(2) est calculé 2 fois, fib(1) est calculé 3 fois!
# C'est pourquoi la mémoïsation est cruciale pour Fibonacci.


[OK] EXERCICES PRATIQUES

# === Exercice 1: Calculer la somme des chiffres ===

def somme_chiffres(n):
    """
    Calcule la somme des chiffres d'un nombre
    Exemple: 123 -> 1 + 2 + 3 = 6
    """
    if n == 0:
        return 0
    return (n % 10) + somme_chiffres(n // 10)

print(somme_chiffres(12345))  # 15

# === SORTIE CONSOLE ===
# 15
#
# Exécution détaillée de somme_chiffres(12345):
# somme_chiffres(12345)
#   = (12345 % 10) + somme_chiffres(12345 // 10)
#   = 5 + somme_chiffres(1234)
#   = 5 + (4 + somme_chiffres(123))
#   = 5 + (4 + (3 + somme_chiffres(12)))
#   = 5 + (4 + (3 + (2 + somme_chiffres(1))))
#   = 5 + (4 + (3 + (2 + (1 + somme_chiffres(0)))))
#   = 5 + (4 + (3 + (2 + (1 + 0))))
#   = 5 + (4 + (3 + (2 + 1)))
#   = 5 + (4 + (3 + 3))
#   = 5 + (4 + 6)
#   = 5 + 10
#   = 15
#
# Visualisation étape par étape:
# 12345 -> dernier chiffre: 5, reste: 1234
# 1234  -> dernier chiffre: 4, reste: 123
# 123   -> dernier chiffre: 3, reste: 12
# 12    -> dernier chiffre: 2, reste: 1
# 1     -> dernier chiffre: 1, reste: 0
# 0     -> cas de base, retourne 0
#
# Somme: 5 + 4 + 3 + 2 + 1 = 15

# === Exercice 2: Vérifier si liste est triée ===

def est_triee(liste):
    """Vérifie si une liste est triée par ordre croissant"""
    if len(liste) <= 1:
        return True
    
    if liste[0] > liste[1]:
        return False
    
    return est_triee(liste[1:])

print(est_triee([1, 2, 3, 4, 5]))  # True
print(est_triee([1, 3, 2, 4]))     # False

# === Exercice 3: Convertir nombre en binaire ===

def decimal_vers_binaire(n):
    """Convertit un nombre décimal en binaire (string)"""
    if n == 0:
        return "0"
    if n == 1:
        return "1"
    
    return decimal_vers_binaire(n // 2) + str(n % 2)

print(decimal_vers_binaire(10))  # "1010"
print(decimal_vers_binaire(25))  # "11001"

# === SORTIE CONSOLE ===
# 1010
# 11001
#
# Exécution détaillée de decimal_vers_binaire(10):
# decimal_vers_binaire(10)
#   = decimal_vers_binaire(10 // 2) + str(10 % 2)
#   = decimal_vers_binaire(5) + "0"
#   = (decimal_vers_binaire(5 // 2) + str(5 % 2)) + "0"
#   = (decimal_vers_binaire(2) + "1") + "0"
#   = ((decimal_vers_binaire(2 // 2) + str(2 % 2)) + "1") + "0"
#   = ((decimal_vers_binaire(1) + "0") + "1") + "0"
#   = (("1" + "0") + "1") + "0"  <- cas de base: 1 retourne "1"
#   = ("10" + "1") + "0"
#   = "101" + "0"
#   = "1010"
#
# Méthode de conversion décimal -> binaire:
# 10 ÷ 2 = 5 reste 0  -> bit le plus à droite
# 5  ÷ 2 = 2 reste 1
# 2  ÷ 2 = 1 reste 0
# 1  ÷ 2 = 0 reste 1  -> bit le plus à gauche
# Lecture de bas en haut: 1010
#
# Exécution détaillée de decimal_vers_binaire(25):
# 25 ÷ 2 = 12 reste 1  -> "1"
# 12 ÷ 2 = 6  reste 0  -> "0"
# 6  ÷ 2 = 3  reste 0  -> "0"
# 3  ÷ 2 = 1  reste 1  -> "1"
# 1  ÷ 2 = 0  reste 1  -> "1" (cas de base)
# Résultat: "11001"
#
# Vérification:
# 1×2⁴ + 1×2³ + 0×2² + 0×2¹ + 1×2⁰
# = 16 + 8 + 0 + 0 + 1
# = 25 [OK]

# === Exercice 4: Compter voyelles ===

def compter_voyelles(s):
    """Compte le nombre de voyelles dans une chaîne"""
    if not s:
        return 0
    
    voyelles = "aeiouAEIOU"
    count = 1 if s[0] in voyelles else 0
    
    return count + compter_voyelles(s[1:])

print(compter_voyelles("Hello World"))  # 3

# === Exercice 5: PGCD (Plus Grand Commun Diviseur) ===

def pgcd(a, b):
    """Algorithme d'Euclide récursif"""
    if b == 0:
        return a
    return pgcd(b, a % b)

print(pgcd(48, 18))  # 6
print(pgcd(100, 35))  # 5

# === SORTIE CONSOLE ===
# 6
# 5
#
# Exécution détaillée de pgcd(48, 18) - Algorithme d'Euclide:
# pgcd(48, 18)
#   b != 0, donc appeler pgcd(18, 48 % 18)
#   = pgcd(18, 12)
#   b != 0, donc appeler pgcd(12, 18 % 12)
#   = pgcd(12, 6)
#   b != 0, donc appeler pgcd(6, 12 % 6)
#   = pgcd(6, 0)
#   b == 0, donc retourner a = 6  <- cas de base
#
# Visualisation avec les divisions:
# 48 = 18 × 2 + 12  -> pgcd(48, 18) = pgcd(18, 12)
# 18 = 12 × 1 + 6   -> pgcd(18, 12) = pgcd(12, 6)
# 12 = 6 × 2 + 0    -> pgcd(12, 6) = pgcd(6, 0) = 6
#
# Vérification: 48 = 6×8, 18 = 6×3 (6 est bien le PGCD)
#
# Exécution détaillée de pgcd(100, 35):
# pgcd(100, 35)
#   = pgcd(35, 100 % 35)
#   = pgcd(35, 30)
#   = pgcd(30, 35 % 30)
#   = pgcd(30, 5)
#   = pgcd(5, 30 % 5)
#   = pgcd(5, 0)
#   = 5  <- cas de base
#
# Visualisation:
# 100 = 35 × 2 + 30  -> pgcd(100, 35) = pgcd(35, 30)
# 35 = 30 × 1 + 5    -> pgcd(35, 30) = pgcd(30, 5)
# 30 = 5 × 6 + 0     -> pgcd(30, 5) = pgcd(5, 0) = 5
#
# Vérification: 100 = 5×20, 35 = 5×7 (5 est bien le PGCD)

# === Exercice 6: Tour de Hanoï (nombre de mouvements) ===

def compter_mouvements_hanoi(n):
    """Compte le nombre de mouvements pour n disques"""
    if n == 1:
        return 1
    return 2 * compter_mouvements_hanoi(n - 1) + 1

print(compter_mouvements_hanoi(3))  # 7 (2^3 - 1)
print(compter_mouvements_hanoi(5))  # 31 (2^5 - 1)

# === SORTIE CONSOLE ===
# 7
# 31
#
# Exécution détaillée de compter_mouvements_hanoi(3):
# compter_mouvements_hanoi(3)
#   = 2 × compter_mouvements_hanoi(2) + 1
#   = 2 × (2 × compter_mouvements_hanoi(1) + 1) + 1
#   = 2 × (2 × 1 + 1) + 1
#   = 2 × (2 + 1) + 1
#   = 2 × 3 + 1
#   = 6 + 1
#   = 7
#
# Formule: Pour n disques, mouvements = 2^n - 1
#
# Vérification avec la formule:
# n = 3: 2³ - 1 = 8 - 1 = 7 [OK]
# n = 5: 2⁵ - 1 = 32 - 1 = 31 [OK]
#
# Pourquoi cette formule?
# Pour déplacer n disques:
# 1. Déplacer (n-1) disques du haut -> 2^(n-1) - 1 mouvements
# 2. Déplacer le plus grand disque -> 1 mouvement
# 3. Déplacer (n-1) disques sur le grand -> 2^(n-1) - 1 mouvements
# Total: (2^(n-1) - 1) + 1 + (2^(n-1) - 1) = 2 × 2^(n-1) - 1 = 2^n - 1
#
# Tableau de mouvements:
# n = 1: 2¹ - 1 = 1 mouvement
# n = 2: 2² - 1 = 3 mouvements
# n = 3: 2³ - 1 = 7 mouvements
# n = 4: 2⁴ - 1 = 15 mouvements
# n = 5: 2⁵ - 1 = 31 mouvements
# n = 10: 2¹⁰ - 1 = 1,023 mouvements
# n = 20: 2²⁰ - 1 = 1,048,575 mouvements
# n = 64: 2⁶⁴ - 1 = 18,446,744,073,709,551,615 mouvements
#        (plus de 18 quintillions! À raison d'1 mouvement/seconde,
#         il faudrait 585 milliards d'années!)

# === Exercice 7: Chemin dans matrice ===

def chemins_matrice(m, n):
    """
    Compte le nombre de chemins pour aller de (0,0) à (m,n)
    en ne se déplaçant que vers la droite ou le bas
    """
    # Cas de base
    if m == 0 or n == 0:
        return 1
    
    # Cas récursif
    return chemins_matrice(m - 1, n) + chemins_matrice(m, n - 1)

print(chemins_matrice(2, 2))  # 6 chemins possibles

# === Exercice 8: Multiplication russe ===

def multiplication_russe(a, b):
    """Multiplication par addition récursive"""
    if a == 0:
        return 0
    if a == 1:
        return b
    
    if a % 2 == 0:
        return multiplication_russe(a // 2, b + b)
    else:
        return b + multiplication_russe(a // 2, b + b)

print(multiplication_russe(7, 8))  # 56

# === Exercice 9: Suite de Collatz ===

def collatz(n, steps=0):
    """
    Suite de Collatz (conjecture 3n+1)
    Retourne le nombre d'étapes pour atteindre 1
    """
    if n == 1:
        return steps
    
    if n % 2 == 0:
        return collatz(n // 2, steps + 1)
    else:
        return collatz(3 * n + 1, steps + 1)

print(collatz(10))  # 6 étapes
print(collatz(27))  # 111 étapes

# === SORTIE CONSOLE ===
# 6
# 111
#
# Exécution détaillée de collatz(10):
# Règles de la suite de Collatz:
# - Si n est pair: n -> n/2
# - Si n est impair: n -> 3n + 1
# - Continuer jusqu'à atteindre 1
#
# collatz(10, steps=0)
#   10 est pair -> 10/2 = 5
#   collatz(5, steps=1)
#     5 est impair -> 3×5 + 1 = 16
#     collatz(16, steps=2)
#       16 est pair -> 16/2 = 8
#       collatz(8, steps=3)
#         8 est pair -> 8/2 = 4
#         collatz(4, steps=4)
#           4 est pair -> 4/2 = 2
#           collatz(2, steps=5)
#             2 est pair -> 2/2 = 1
#             collatz(1, steps=6)
#               n == 1 -> retourne 6  <- cas de base
#
# Séquence complète: 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (6 étapes)
#
# Exécution de collatz(27) - exemple fascinant:
# 27 -> 82 -> 41 -> 124 -> 62 -> 31 -> 94 -> 47 -> 142 -> 71 -> 214 -> 107 -> 322
# -> 161 -> 484 -> 242 -> 121 -> 364 -> 182 -> 91 -> 274 -> 137 -> 412 -> 206 -> 103
# -> 310 -> 155 -> 466 -> 233 -> 700 -> 350 -> 175 -> 526 -> 263 -> 790 -> 395 -> 1186
# -> 593 -> 1780 -> 890 -> 445 -> 1336 -> 668 -> 334 -> 167 -> 502 -> 251 -> 754 -> 377
# -> 1132 -> 566 -> 283 -> 850 -> 425 -> 1276 -> 638 -> 319 -> 958 -> 479 -> 1438 -> 719
# -> 2158 -> 1079 -> 3238 -> 1619 -> 4858 -> 2429 -> 7288 -> 3644 -> 1822 -> 911 -> 2734
# -> 1367 -> 4102 -> 2051 -> 6154 -> 3077 -> 9232 -> 4616 -> 2308 -> 1154 -> 577 -> 1732
# -> 866 -> 433 -> 1300 -> 650 -> 325 -> 976 -> 488 -> 244 -> 122 -> 61 -> 184 -> 92 -> 46
# -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
#
# Total: 111 étapes! (Le nombre monte jusqu'à 9232!)
#
# Conjecture de Collatz:
# Pour TOUT entier positif, la suite finit toujours par atteindre 1.
# Cette conjecture n'a JAMAIS été prouvée mathématiquement!
# Testée jusqu'à 2⁶⁸ (268 millions de milliards) sans contre-exemple.
#
# Exemples d'autres séquences intéressantes:
# collatz(1) = 0 étapes (déjà à 1)
# collatz(2) = 1 étape (2 -> 1)
# collatz(3) = 7 étapes (3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1)
# collatz(6) = 8 étapes
# collatz(7) = 16 étapes (7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> ... -> 1)

# === Exercice 10: Nombre de façons de gravir escalier ===

def escalier(n):
    """
    Nombre de façons de monter n marches
    en faisant des pas de 1 ou 2 marches
    """
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    return escalier(n - 1) + escalier(n - 2)

print(escalier(5))  # 8 façons

# === SORTIE CONSOLE ===
# 8
#
# Exécution détaillée de escalier(5):
# escalier(5)
#   = escalier(4) + escalier(3)
#   = (escalier(3) + escalier(2)) + (escalier(2) + escalier(1))
#   = ((escalier(2) + escalier(1)) + 2) + (2 + 1)
#   = ((2 + 1) + 2) + (2 + 1)
#   = (3 + 2) + 3
#   = 5 + 3
#   = 8
#
# Explication du problème:
# Pour monter 5 marches en faisant des pas de 1 ou 2 marches:
#
# Les 8 façons possibles:
# 1. 1+1+1+1+1 = 5 (5 pas de 1)
# 2. 2+1+1+1 = 5   (1 pas de 2, puis 3 pas de 1)
# 3. 1+2+1+1 = 5   (1 pas de 1, 1 pas de 2, 2 pas de 1)
# 4. 1+1+2+1 = 5   (2 pas de 1, 1 pas de 2, 1 pas de 1)
# 5. 1+1+1+2 = 5   (3 pas de 1, 1 pas de 2)
# 6. 2+2+1 = 5     (2 pas de 2, 1 pas de 1)
# 7. 2+1+2 = 5     (1 pas de 2, 1 pas de 1, 1 pas de 2)
# 8. 1+2+2 = 5     (1 pas de 1, 2 pas de 2)
#
# Visualisation de la récursion:
#                    escalier(5)
#                   /           \
#            escalier(4)      escalier(3)
#            /        \        /         \
#      esc(3)      esc(2)  esc(2)     esc(1)
#      /    \      /    \   /   \        |
#   esc(2) esc(1) 2     1  2    1        1
#   /   \    |
#  2    1    1
#
# Logique récursive:
# Pour atteindre la marche n, on peut:
# - Venir de la marche (n-1) avec un pas de 1
# - Venir de la marche (n-2) avec un pas de 2
# Donc: façons(n) = façons(n-1) + façons(n-2)
#
# Note intéressante: C'est la suite de Fibonacci!
# escalier(1) = 1 = fib(2)
# escalier(2) = 2 = fib(3)
# escalier(3) = 3 = fib(4)
# escalier(4) = 5 = fib(5)
# escalier(5) = 8 = fib(6)
#
# Tableau des résultats:
# n marches -> nombre de façons
# 1 -> 1 façon  (1)
# 2 -> 2 façons (1+1, 2)
# 3 -> 3 façons (1+1+1, 1+2, 2+1)
# 4 -> 5 façons
# 5 -> 8 façons
# 6 -> 13 façons
# 10 -> 89 façons


[OK] COMPLEXITÉ TEMPORELLE

# Analyse de la complexité des fonctions récursives

# === O(n) - Linéaire ===
def somme_lineaire(n):
    if n <= 0:
        return 0
    return n + somme_lineaire(n - 1)
# Nombre d'appels: n
# Complexité: O(n)

# === O(n²) - Quadratique ===
def imprimer_triangle(n):
    if n <= 0:
        return
    imprimer_triangle(n - 1)
    print('*' * n)
# Travail à chaque niveau: O(n)
# Profondeur: n
# Complexité: O(n²)

# === O(2^n) - Exponentielle ===
def fibonacci_naif(n):
    if n <= 1:
        return n
    return fibonacci_naif(n - 1) + fibonacci_naif(n - 2)
# Arbre binaire complet
# Complexité: O(2^n) - TRÈS LENT!

# === O(n) avec mémoïsation ===
@lru_cache(maxsize=None)
def fibonacci_memo(n):
    if n <= 1:
        return n
    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)
# Chaque valeur calculée une seule fois
# Complexité: O(n)

# === O(log n) - Logarithmique ===
def puissance_optimisee(x, n):
    if n == 0:
        return 1
    if n == 1:
        return x
    
    if n % 2 == 0:
        half = puissance_optimisee(x, n // 2)
        return half * half
    else:
        return x * puissance_optimisee(x, n - 1)
# Divise n par 2 à chaque fois
# Complexité: O(log n)

# === O(n log n) - Tri fusion ===
def tri_fusion_complexity(liste):
    if len(liste) <= 1:
        return liste
    
    milieu = len(liste) // 2
    gauche = tri_fusion_complexity(liste[:milieu])
    droite = tri_fusion_complexity(liste[milieu:])
    
    return fusion(gauche, droite)
# Divise en 2: log n niveaux
# Fusion à chaque niveau: O(n)
# Complexité: O(n log n)


[OK] COMPLEXITÉ SPATIALE

# Espace utilisé par la pile d'appels

# === O(n) - Pile linéaire ===
def factorielle_espace(n):
    if n <= 1:
        return 1
    return n * factorielle_espace(n - 1)
# Profondeur de pile: n
# Espace: O(n)

# === O(log n) - Pile logarithmique ===
def recherche_binaire_espace(liste, x, debut=0, fin=None):
    if fin is None:
        fin = len(liste) - 1
    
    if debut > fin:
        return -1
    
    milieu = (debut + fin) // 2
    
    if liste[milieu] == x:
        return milieu
    elif x < liste[milieu]:
        return recherche_binaire_espace(liste, x, debut, milieu - 1)
    else:
        return recherche_binaire_espace(liste, x, milieu + 1, fin)
# Profondeur: log n
# Espace: O(log n)

# === O(1) - Récursion terminale (théorique) ===
def somme_terminale_espace(n, acc=0):
    if n <= 0:
        return acc
    return somme_terminale_espace(n - 1, acc + n)
# Théoriquement O(1) si optimisé
# En Python: O(n) car pas d'optimisation TCO


[OK] FRACTALES ET GRAPHIQUES RÉCURSIFS

# === 1. Triangle de Sierpiński (ASCII) ===

def sierpinski(n, char='*'):
    """Dessine un triangle de Sierpiński en ASCII"""
    if n == 0:
        return [char]
    
    triangle_precedent = sierpinski(n - 1, char)
    
    # Espaces pour centrer
    espaces = ' ' * (2 ** (n - 1))
    
    # Partie haute: triangle précédent centré
    partie_haute = [espaces + ligne + espaces for ligne in triangle_precedent]
    
    # Partie basse: deux triangles côte à côte
    partie_basse = [ligne + ' ' + ligne for ligne in triangle_precedent]
    
    return partie_haute + partie_basse

# Afficher
for ligne in sierpinski(3):
    print(ligne)

# === 2. Courbe de Koch (coordonnées) ===

def koch_snowflake(ordre, longueur=100):
    """
    Génère les points de la courbe de Koch
    Retourne une liste de coordonnées (x, y)
    """
    import math
    
    def koch_segment(p1, p2, ordre):
        if ordre == 0:
            return [p1, p2]
        
        # Diviser le segment en 3
        x1, y1 = p1
        x2, y2 = p2
        
        # Point à 1/3
        px1 = x1 + (x2 - x1) / 3
        py1 = y1 + (y2 - y1) / 3
        
        # Point à 2/3
        px2 = x1 + 2 * (x2 - x1) / 3
        py2 = y1 + 2 * (y2 - y1) / 3
        
        # Point du triangle (sommet)
        angle = math.atan2(y2 - y1, x2 - x1) - math.pi / 3
        px3 = px1 + (px2 - px1) * math.cos(angle) - (py2 - py1) * math.sin(angle)
        py3 = py1 + (px2 - px1) * math.sin(angle) + (py2 - py1) * math.cos(angle)
        
        # Récursion sur les 4 segments
        points = []
        points.extend(koch_segment((x1, y1), (px1, py1), ordre - 1)[:-1])
        points.extend(koch_segment((px1, py1), (px3, py3), ordre - 1)[:-1])
        points.extend(koch_segment((px3, py3), (px2, py2), ordre - 1)[:-1])
        points.extend(koch_segment((px2, py2), (x2, y2), ordre - 1))
        
        return points
    
    # Triangle initial
    return koch_segment((0, 0), (longueur, 0), ordre)

# === 3. Arbre fractal (ASCII) ===

def arbre_ascii(hauteur, char='|', branches='/\\'):
    """Dessine un arbre fractal en ASCII"""
    if hauteur <= 0:
        return []
    
    if hauteur == 1:
        return [char]
    
    # Tronc
    tronc = [char] * 2
    
    # Branches récursives
    sous_arbre = arbre_ascii(hauteur - 1, char, branches)
    
    # Construire les branches
    largeur = len(sous_arbre[-1]) if sous_arbre else 1
    branches_ligne = [
        ' ' * (largeur // 2) + branches[0] + ' ' * (largeur - largeur // 2 - 1) + branches[1]
    ]
    
    # Décaler le sous-arbre
    sous_arbre_decale = []
    for ligne in sous_arbre:
        sous_arbre_decale.append(' ' + ligne + ' ')
    
    return tronc + branches_ligne + sous_arbre_decale

# Afficher
for ligne in arbre_ascii(4):
    print(ligne)


[OK] JEUX ET PUZZLES

# === 1. Résoudre un labyrinthe (toutes les solutions) ===

def toutes_solutions_labyrinthe(maze, x=0, y=0, chemin=None):
    """
    Trouve toutes les solutions d'un labyrinthe
    0 = mur, 1 = passage, 2 = sortie
    """
    if chemin is None:
        chemin = []
    
    # Vérifier limites
    if x < 0 or x >= len(maze) or y < 0 or y >= len(maze[0]):
        return []
    
    # Vérifier mur ou déjà visité
    if maze[x][y] == 0 or (x, y) in chemin:
        return []
    
    # Nouveau chemin
    nouveau_chemin = chemin + [(x, y)]
    
    # Sortie trouvée
    if maze[x][y] == 2:
        return [nouveau_chemin]
    
    # Explorer toutes les directions
    solutions = []
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    for dx, dy in directions:
        solutions.extend(
            toutes_solutions_labyrinthe(maze, x + dx, y + dy, nouveau_chemin)
        )
    
    return solutions

# === 2. Jeu du Nim (stratégie optimale) ===

def nim_gagnant(tas, joueur_max=True, memo=None):
    """
    Détermine si le joueur actuel peut gagner au jeu du Nim
    tas: liste d'entiers représentant le nombre d'objets par tas
    """
    if memo is None:
        memo = {}
    
    # Clé pour mémoïsation
    key = (tuple(sorted(tas)), joueur_max)
    
    if key in memo:
        return memo[key]
    
    # Cas de base: plus d'objets
    if sum(tas) == 0:
        return not joueur_max  # Le joueur qui ne peut pas jouer perd
    
    # Essayer tous les coups possibles
    for i in range(len(tas)):
        for retrait in range(1, tas[i] + 1):
            nouveau_tas = tas[:]
            nouveau_tas[i] -= retrait
            
            # Si l'adversaire perd, on gagne
            if not nim_gagnant(nouveau_tas, not joueur_max, memo):
                memo[key] = True
                return True
    
    # Si tous les coups mènent à une victoire adverse, on perd
    memo[key] = False
    return False

print(nim_gagnant([3, 4, 5]))  # True ou False selon la position

# === 3. Tic-Tac-Toe (Minimax) ===

def minimax_tictactoe(board, joueur):
    """
    Algorithme Minimax pour Tic-Tac-Toe
    board: grille 3x3
    joueur: 'X' ou 'O'
    """
    def verifier_gagnant(board):
        # Lignes, colonnes, diagonales
        for i in range(3):
            if board[i][0] == board[i][1] == board[i][2] != ' ':
                return board[i][0]
            if board[0][i] == board[1][i] == board[2][i] != ' ':
                return board[0][i]
        
        if board[0][0] == board[1][1] == board[2][2] != ' ':
            return board[0][0]
        if board[0][2] == board[1][1] == board[2][0] != ' ':
            return board[0][2]
        
        return None
    
    def est_plein(board):
        return all(cell != ' ' for row in board for cell in row)
    
    def minimax(board, est_maximisant):
        gagnant = verifier_gagnant(board)
        
        # Cas terminaux
        if gagnant == 'X':
            return 1
        if gagnant == 'O':
            return -1
        if est_plein(board):
            return 0
        
        if est_maximisant:
            meilleur_score = float('-inf')
            for i in range(3):
                for j in range(3):
                    if board[i][j] == ' ':
                        board[i][j] = 'X'
                        score = minimax(board, False)
                        board[i][j] = ' '
                        meilleur_score = max(score, meilleur_score)
            return meilleur_score
        else:
            meilleur_score = float('inf')
            for i in range(3):
                for j in range(3):
                    if board[i][j] == ' ':
                        board[i][j] = 'O'
                        score = minimax(board, True)
                        board[i][j] = ' '
                        meilleur_score = min(score, meilleur_score)
            return meilleur_score
    
    # Trouver meilleur coup
    meilleur_score = float('-inf') if joueur == 'X' else float('inf')
    meilleur_coup = None
    
    for i in range(3):
        for j in range(3):
            if board[i][j] == ' ':
                board[i][j] = joueur
                score = minimax(board, joueur == 'O')
                board[i][j] = ' '
                
                if joueur == 'X':
                    if score > meilleur_score:
                        meilleur_score = score
                        meilleur_coup = (i, j)
                else:
                    if score < meilleur_score:
                        meilleur_score = score
                        meilleur_coup = (i, j)
    
    return meilleur_coup


[OK] PROBLÈMES MATHÉMATIQUES

# === 1. Coefficients binomiaux (Triangle de Pascal) ===

def coefficient_binomial(n, k):
    """
    Calcule C(n, k) = n! / (k! * (n-k)!)
    Formule récursive: C(n, k) = C(n-1, k-1) + C(n-1, k)
    """
    # Cas de base
    if k == 0 or k == n:
        return 1
    
    # Cas récursif
    return coefficient_binomial(n - 1, k - 1) + coefficient_binomial(n - 1, k)

print(coefficient_binomial(5, 2))  # 10

# Avec mémoïsation
@lru_cache(maxsize=None)
def coeff_binomial_memo(n, k):
    if k == 0 or k == n:
        return 1
    return coeff_binomial_memo(n - 1, k - 1) + coeff_binomial_memo(n - 1, k)

# === 2. Suite de Catalan ===

def nombre_catalan(n):
    """
    Nombres de Catalan: C(n) = somme(C(i) * C(n-1-i)) pour i de 0 à n-1
    Applications: arbres binaires, parenthésages, chemins...
    """
    if n <= 1:
        return 1
    
    resultat = 0
    for i in range(n):
        resultat += nombre_catalan(i) * nombre_catalan(n - 1 - i)
    
    return resultat

print([nombre_catalan(i) for i in range(10)])
# [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

# === 3. Partition d'un nombre ===

def partitions(n, max_val=None):
    """
    Compte le nombre de façons de partitionner un nombre
    Exemple: 4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1 (5 partitions)
    """
    if max_val is None:
        max_val = n
    
    if n == 0:
        return 1
    if n < 0 or max_val == 0:
        return 0
    
    # Inclure max_val ou ne pas l'inclure
    return partitions(n - max_val, max_val) + partitions(n, max_val - 1)

print(partitions(5))  # 7

# === 4. Suite de Tribonacci ===

def tribonacci(n):
    """
    Comme Fibonacci mais avec 3 termes précédents
    T(n) = T(n-1) + T(n-2) + T(n-3)
    """
    if n == 0:
        return 0
    if n <= 2:
        return 1
    
    return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)

print([tribonacci(i) for i in range(10)])
# [0, 1, 1, 2, 4, 7, 13, 24, 44, 81]

# === 5. Problème des pièces de monnaie ===

def compter_pieces(montant, pieces):
    """
    Compte le nombre de façons de faire un montant avec des pièces
    """
    if montant == 0:
        return 1
    if montant < 0 or not pieces:
        return 0
    
    # Utiliser la première pièce ou ne pas l'utiliser
    avec = compter_pieces(montant - pieces[0], pieces)
    sans = compter_pieces(montant, pieces[1:])
    
    return avec + sans

print(compter_pieces(10, [1, 2, 5]))  # Nombre de façons

# === 6. Ackermann (fonction à croissance rapide) ===

def ackermann(m, n):
    """
    Fonction d'Ackermann - croît TRÈS rapidement
    ATTENTION: Ne pas utiliser avec m > 3 et n > 10
    """
    if m == 0:
        return n + 1
    if n == 0:
        return ackermann(m - 1, 1)
    
    return ackermann(m - 1, ackermann(m, n - 1))

print(ackermann(3, 4))  # 125
# ackermann(4, 2) = 2^65536 - 3 (nombre astronomique!)


[OK] TRAITEMENT DE DONNÉES HIÉRARCHIQUES

# === 1. JSON/Dict profondément imbriqués ===

def chercher_cle_profonde(data, cle_cherchee):
    """Trouve toutes les valeurs associées à une clé dans un dict imbriqué"""
    resultats = []
    
    if isinstance(data, dict):
        for cle, valeur in data.items():
            if cle == cle_cherchee:
                resultats.append(valeur)
            # Récursion sur les valeurs
            resultats.extend(chercher_cle_profonde(valeur, cle_cherchee))
    
    elif isinstance(data, list):
        for element in data:
            resultats.extend(chercher_cle_profonde(element, cle_cherchee))
    
    return resultats

# Exemple
data_complexe = {
    'nom': 'Alice',
    'details': {
        'age': 30,
        'nom': 'Alice Smith',
        'contacts': {
            'email': 'alice@example.com',
            'nom': 'Contact Principal'
        }
    },
    'projets': [
        {'nom': 'Projet A', 'status': 'actif'},
        {'nom': 'Projet B', 'status': 'terminé'}
    ]
}

print(chercher_cle_profonde(data_complexe, 'nom'))
# ['Alice', 'Alice Smith', 'Contact Principal', 'Projet A', 'Projet B']

# === SORTIE CONSOLE ===
# ['Alice', 'Alice Smith', 'Contact Principal', 'Projet A', 'Projet B']
#
# Structure de data_complexe (rappel):
# {
#   'nom': 'Alice',                          <- Trouvé niveau 1
#   'details': {
#     'age': 30,
#     'nom': 'Alice Smith',                  <- Trouvé niveau 2
#     'contacts': {
#       'email': 'alice@example.com',
#       'nom': 'Contact Principal'           <- Trouvé niveau 3
#     }
#   },
#   'projets': [
#     {'nom': 'Projet A', 'status': 'actif'},     <- Trouvé niveau 2 (dans liste)
#     {'nom': 'Projet B', 'status': 'terminé'}    <- Trouvé niveau 2 (dans liste)
#   ]
# }
#
# Exécution détaillée de chercher_cle_profonde(data, 'nom'):
#
# Appel 1: chercher_cle_profonde(data_complexe, 'nom')
#   data est un dict [OK]
#   resultats = []
#   
#   Parcourir chaque clé:
#   
#   cle='nom', valeur='Alice'
#     cle == 'nom' -> Ajouter 'Alice'
#     resultats = ['Alice']
#     Récursion sur valeur 'Alice' (string)
#       'Alice' n'est ni dict ni list -> return []
#     resultats = ['Alice']
#   
#   cle='details', valeur={dict}
#     cle != 'nom'
#     Récursion sur valeur {dict}
#       chercher_cle_profonde({'age':30, 'nom':'Alice Smith', ...}, 'nom')
#         data est un dict [OK]
#         
#         cle='age', valeur=30
#           cle != 'nom', récursion sur 30 -> return []
#         
#         cle='nom', valeur='Alice Smith'
#           cle == 'nom' -> Ajouter 'Alice Smith'
#           resultats locaux = ['Alice Smith']
#           Récursion sur 'Alice Smith' -> return []
#         
#         cle='contacts', valeur={dict}
#           cle != 'nom'
#           Récursion sur {'email':..., 'nom':'Contact Principal'}
#             cle='email' -> pas 'nom'
#             cle='nom', valeur='Contact Principal'
#               cle == 'nom' -> Ajouter 'Contact Principal'
#               return ['Contact Principal']
#         
#         return ['Alice Smith', 'Contact Principal']
#     
#     resultats = ['Alice', 'Alice Smith', 'Contact Principal']
#   
#   cle='projets', valeur=[liste]
#     cle != 'nom'
#     Récursion sur [liste]
#       chercher_cle_profonde([{...}, {...}], 'nom')
#         data est une list [OK]
#         
#         Pour element = {'nom':'Projet A', 'status':'actif'}:
#           chercher_cle_profonde({...}, 'nom')
#             cle='nom', valeur='Projet A'
#               cle == 'nom' -> Ajouter 'Projet A'
#               return ['Projet A']
#             cle='status' -> pas 'nom'
#             return ['Projet A']
#         
#         Pour element = {'nom':'Projet B', 'status':'terminé'}:
#           chercher_cle_profonde({...}, 'nom')
#             cle='nom', valeur='Projet B'
#               cle == 'nom' -> Ajouter 'Projet B'
#               return ['Projet B']
#         
#         return ['Projet A', 'Projet B']
#     
#     resultats = ['Alice', 'Alice Smith', 'Contact Principal', 
#                  'Projet A', 'Projet B']
#
# return ['Alice', 'Alice Smith', 'Contact Principal', 'Projet A', 'Projet B']
#
# Visualisation de l'arbre de recherche:
#
# data_complexe
# ├─ 'nom': 'Alice' [OK] TROUVÉ
# ├─ 'details': {dict}
# │  ├─ 'age': 30
# │  ├─ 'nom': 'Alice Smith' [OK] TROUVÉ
# │  └─ 'contacts': {dict}
# │     ├─ 'email': 'alice@...'
# │     └─ 'nom': 'Contact Principal' [OK] TROUVÉ
# └─ 'projets': [list]
#    ├─ [0]: {dict}
#    │  ├─ 'nom': 'Projet A' [OK] TROUVÉ
#    │  └─ 'status': 'actif'
#    └─ [1]: {dict}
#       ├─ 'nom': 'Projet B' [OK] TROUVÉ
#       └─ 'status': 'terminé'
#
# Ordre de découverte (parcours en profondeur):
# 1. 'Alice' (niveau 1)
# 2. 'Alice Smith' (niveau 2, dans details)
# 3. 'Contact Principal' (niveau 3, dans details.contacts)
# 4. 'Projet A' (niveau 2, dans projets[0])
# 5. 'Projet B' (niveau 2, dans projets[1])
#
# Autres exemples avec la même structure:
# chercher_cle_profonde(data, 'age') -> [30]
# chercher_cle_profonde(data, 'status') -> ['actif', 'terminé']
# chercher_cle_profonde(data, 'email') -> ['alice@example.com']
# chercher_cle_profonde(data, 'inexistant') -> []
#
# Cas d'usage réels:
# - Parser des réponses API JSON complexes
# - Extraire des données de configurations imbriquées
# - Rechercher dans des arbres de documents
# - Analyser des logs structurés

# === 2. Système de fichiers ===

def taille_repertoire_recursive(chemin):
    """Calcule la taille totale d'un répertoire récursivement"""
    import os
    
    taille_totale = 0
    
    try:
        if os.path.isfile(chemin):
            return os.path.getsize(chemin)
        
        for element in os.listdir(chemin):
            chemin_complet = os.path.join(chemin, element)
            taille_totale += taille_repertoire_recursive(chemin_complet)
    
    except PermissionError:
        pass
    
    return taille_totale

# === 3. XML/HTML parsing ===

def extraire_texte_xml(element):
    """Extrait tout le texte d'un élément XML et ses enfants"""
    texte = element.text or ""
    
    for enfant in element:
        texte += extraire_texte_xml(enfant)
        texte += enfant.tail or ""
    
    return texte

# Exemple avec ElementTree (bibliothèque standard)
from xml.etree import ElementTree as ET

# xml_string = '<root><a>Text1</a><b><c>Text2</c></b></root>'
# root = ET.fromstring(xml_string)
# print(extraire_texte_xml(root))


[OK] PATTERNS D'OPTIMISATION

# === 1. Mémoïsation avec décorateur personnalisé ===

def memoize_advanced(func):
    """Décorateur de mémoïsation avancé avec statistiques"""
    cache = {}
    stats = {'hits': 0, 'misses': 0}
    
    def wrapper(*args, **kwargs):
        # Créer clé unique
        key = (args, tuple(sorted(kwargs.items())))
        
        if key in cache:
            stats['hits'] += 1
            return cache[key]
        
        stats['misses'] += 1
        result = func(*args, **kwargs)
        cache[key] = result
        return result
    
    wrapper.cache = cache
    wrapper.stats = stats
    wrapper.clear_cache = lambda: cache.clear()
    
    return wrapper

@memoize_advanced
def fonction_couteuse(n):
    if n <= 1:
        return n
    return fonction_couteuse(n - 1) + fonction_couteuse(n - 2)

result = fonction_couteuse(30)
print(f"Résultat: {result}")
print(f"Stats: {fonction_couteuse.stats}")

# === SORTIE CONSOLE ===
# Résultat: 832040
# Stats: {'hits': 28, 'misses': 31}
#
# Explication: fibonacci(30) avec mémoïsation personnalisée
#
# Résultat: 832040
# - C'est le 30ème nombre de Fibonacci
# - fib(0)=0, fib(1)=1, fib(2)=1, ..., fib(30)=832040
#
# Statistiques du cache:
# - hits: 28 -> Le cache a été utilisé 28 fois (valeurs déjà calculées)
# - misses: 31 -> Le cache n'avait pas la valeur 31 fois (nouveaux calculs)
#
# Détail des appels pour fibonacci(30):
#
# Premier appel: fonction_couteuse(30)
#   cache = {}
#   stats = {'hits': 0, 'misses': 0}
#   
#   30 not in cache -> MISS
#   stats['misses'] = 1
#   Calcule: fonction_couteuse(29) + fonction_couteuse(28)
#   cache[30] = résultat
#
# Appel récursif: fonction_couteuse(29)
#   29 not in cache -> MISS
#   stats['misses'] = 2
#   Calcule: fonction_couteuse(28) + fonction_couteuse(27)
#   cache[29] = résultat
#
# Appel récursif: fonction_couteuse(28)
#   28 not in cache -> MISS
#   stats['misses'] = 3
#   Calcule: fonction_couteuse(27) + fonction_couteuse(26)
#   cache[28] = résultat
#
# ... continue jusqu'à fib(0) et fib(1) ...
#
# Appel: fonction_couteuse(28) [seconde fois]
#   28 in cache -> HIT! [OK]
#   stats['hits'] = 1
#   return cache[28] immédiatement (pas de calcul)
#
# Analyse complète des appels:
#
# MISSES (31 au total): valeurs calculées pour la première fois
# fib(30), fib(29), fib(28), ..., fib(2), fib(1), fib(0)
# = 31 valeurs uniques
#
# HITS (28 au total): valeurs réutilisées depuis le cache
# Exemple d'arbre partiel:
#           fib(30)
#          /        \
#      fib(29)    fib(28) <- HIT #1 (déjà calculé pour fib(29))
#      /    \
#   fib(28) fib(27)
#   ^ MISS   /    \
#        fib(26) fib(25)
#        ^ MISS   /    \
#             fib(24) fib(23) <- tous deviennent des HITS ensuite
#
# Sans mémoïsation (fibonacci naïf):
# - Nombre d'appels pour fib(30) ≈ 2^30 ≈ 1,073,741,824 appels!
# - Temps d'exécution: plusieurs minutes voire heures
#
# Avec mémoïsation:
# - Nombre d'appels: 31 MISSES + 28 HITS = 59 appels total
# - Temps d'exécution: quelques millisecondes
#
# Gain de performance:
# 1,073,741,824 / 59 ≈ 18,197,828x plus rapide!
#
# Visualisation du cache au fil du temps:
# Étape 1: cache = {0: 0}
# Étape 2: cache = {0: 0, 1: 1}
# Étape 3: cache = {0: 0, 1: 1, 2: 1}
# Étape 4: cache = {0: 0, 1: 1, 2: 1, 3: 2}
# ...
# Étape 31: cache = {0: 0, 1: 1, 2: 1, ..., 30: 832040}
#
# Répartition hits/misses:
# - Premiers appels (0-30): tous MISS (31)
# - Appels suivants: réutilisation du cache (28 HITS)
#
# Exemple d'utilisation du cache:
# fib(5) = fib(4) + fib(3)
#   fib(4) = fib(3) + fib(2)  <- fib(3) calculé
#     fib(3) -> MISS, calcule et cache
#     fib(2) -> déjà en cache, HIT
#   fib(3) -> déjà en cache, HIT [OK] (évite recalcul)
#
# Contenu du cache après fib(30):
# {
#   0: 0,
#   1: 1,
#   2: 1,
#   3: 2,
#   4: 3,
#   5: 5,
#   ...
#   28: 317811,
#   29: 514229,
#   30: 832040
# }
#
# Note: Le cache persiste entre les appels!
# fonction_couteuse(30)  # 31 misses, 28 hits
# fonction_couteuse(25)  # 0 misses, 1 hit (déjà en cache!)
# fonction_couteuse(35)  # 5 misses, 33 hits (réutilise 0-30)

# === 2. Limite de profondeur personnalisée ===

def avec_limite_profondeur(max_depth):
    """Décorateur pour limiter la profondeur de récursion"""
    def decorator(func):
        def wrapper(*args, depth=0, **kwargs):
            if depth >= max_depth:
                raise RecursionError(f"Profondeur maximale atteinte: {max_depth}")
            
            return func(*args, depth=depth + 1, **kwargs)
        
        return wrapper
    return decorator

@avec_limite_profondeur(max_depth=100)
def factorielle_limitee(n, depth=0):
    if n <= 1:
        return 1
    return n * factorielle_limitee(n - 1, depth=depth)

# === 3. Conversion automatique récursion -> itération ===

def trampoliner(func):
    """
    Simule la récursion terminale avec une trampoline
    Évite le dépassement de pile
    """
    def wrapper(*args, **kwargs):
        result = func(*args, **kwargs)
        
        while callable(result):
            result = result()
        
        return result
    
    return wrapper

# Utilisation
def factorielle_trampoline(n, acc=1):
    if n <= 1:
        return acc
    return lambda: factorielle_trampoline(n - 1, n * acc)

@trampoliner
def fact_safe(n):
    return factorielle_trampoline(n)

print(fact_safe(1000))  # Pas de RecursionError!

# === SORTIE CONSOLE ===
# (un très grand nombre avec environ 2567 chiffres)
# 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
#
# Explication: Calcul de 1000! sans dépassement de pile
#
# Factorielle(1000) = 1000 × 999 × 998 × ... × 2 × 1
#
# Problème avec récursion classique:
# def factorielle_classique(n):
#     if n <= 1:
#         return 1
#     return n * factorielle_classique(n - 1)
#
# factorielle_classique(1000)
# -> RecursionError: maximum recursion depth exceeded
#
# Pourquoi? Limite par défaut en Python ≈ 1000 appels récursifs
# import sys
# sys.getrecursionlimit()  # Retourne typiquement 1000
#
# Solution avec Trampoline:
# La trampoline évite d'empiler les appels en les transformant en boucle
#
# Comment ça marche:
#
# 1. Au lieu d'appeler directement la fonction récursive:
#    return n * fact(n-1)
#
# 2. On retourne une fonction lambda (closure):
#    return lambda: fact_trampoline(n-1, n*acc)
#
# 3. Le décorateur @trampoliner exécute en boucle:
#    while callable(result):
#        result = result()  # Appel NON récursif!
#
# Exécution détaillée de fact_safe(5):
#
# @trampoliner
# def fact_safe(n):
#     return factorielle_trampoline(n)
#
# fact_safe(5)
#   result = factorielle_trampoline(5, 1)
#     n=5, acc=1
#     n > 1 -> return lambda: fact_trampoline(4, 5*1)
#   result = <lambda>  # callable=True
#   
#   Boucle while:
#     result = result()  # Appelle le lambda
#       = factorielle_trampoline(4, 5)
#         n=4, acc=5
#         n > 1 -> return lambda: fact_trampoline(3, 4*5)
#     result = <lambda>  # callable=True
#   
#     result = result()
#       = factorielle_trampoline(3, 20)
#         n=3, acc=20
#         n > 1 -> return lambda: fact_trampoline(2, 3*20)
#     result = <lambda>  # callable=True
#   
#     result = result()
#       = factorielle_trampoline(2, 60)
#         n=2, acc=60
#         n > 1 -> return lambda: fact_trampoline(1, 2*60)
#     result = <lambda>  # callable=True
#   
#     result = result()
#       = factorielle_trampoline(1, 120)
#         n=1, acc=120
#         n <= 1 -> return 120  # PAS un lambda!
#     result = 120  # callable=False
#   
#   Sortie de la boucle
#   return 120
#
# Pile d'appels pour fact_safe(5):
# fact_safe(5)
#   └─ trampoliner.wrapper()
#       └─ while loop (pas de récursion!)
#          factorielle_trampoline(5) -> lambda
#          factorielle_trampoline(4) -> lambda
#          factorielle_trampoline(3) -> lambda
#          factorielle_trampoline(2) -> lambda
#          factorielle_trampoline(1) -> 120
#
# Profondeur maximale de pile: 2 appels seulement!
# (fact_safe -> trampoliner.wrapper)
#
# Pour fact_safe(1000):
# - Profondeur de pile: 2 (constant!)
# - Nombre d'itérations de la boucle: 1000
# - Pas de RecursionError [OK]
#
# Comparaison des approches:
#
# Récursion classique:
# fact(1000) -> stack overflow à ~1000
# Profondeur: 1000 appels empilés
#
# Récursion terminale (théorique avec TCO):
# fact_tail(1000, 1) -> idéalement O(1) mémoire
# Python ne l'optimise PAS
# Profondeur: toujours 1000 appels
#
# Trampoline:
# fact_safe(1000) -> fonctionne! [OK]
# Profondeur: O(1) - seulement 2 appels
# Itérations: 1000 (dans la boucle)
#
# Taille du résultat:
# 1000! est un nombre ÉNORME:
# - Environ 2568 chiffres
# - ≈ 4.02 × 10^2567
# - Plus grand que le nombre d'atomes dans l'univers!
#
# Vérification pour petits nombres:
# fact_safe(5) = 120 [OK]
# fact_safe(10) = 3628800 [OK]
# fact_safe(20) = 2432902008176640000 [OK]
# fact_safe(1000) = (le nombre ci-dessus) [OK]
#
# Limitations:
# - Syntaxe un peu lourde (lambda partout)
# - Légèrement plus lent qu'une boucle for simple
# - Mais permet de garder le style récursif!


[OK] CAS D'USAGE RÉELS

# === 1. Validation de structure JSON Schema ===

def valider_schema(data, schema):
    """Valide récursivement une structure de données contre un schéma"""
    
    if schema['type'] == 'object':
        if not isinstance(data, dict):
            return False
        
        for key, sub_schema in schema.get('properties', {}).items():
            if key in data:
                if not valider_schema(data[key], sub_schema):
                    return False
        
        return True
    
    elif schema['type'] == 'array':
        if not isinstance(data, list):
            return False
        
        items_schema = schema.get('items', {})
        return all(valider_schema(item, items_schema) for item in data)
    
    elif schema['type'] == 'string':
        return isinstance(data, str)
    
    elif schema['type'] == 'number':
        return isinstance(data, (int, float))
    
    return True

# === 2. Évaluation d'expressions mathématiques ===

def evaluer_expression(expr):
    """
    Évalue une expression mathématique sous forme d'arbre
    expr: tuple (operateur, gauche, droite) ou nombre
    """
    # Cas de base: nombre
    if isinstance(expr, (int, float)):
        return expr
    
    operateur, gauche, droite = expr
    
    # Évaluer récursivement les sous-expressions
    val_gauche = evaluer_expression(gauche)
    val_droite = evaluer_expression(droite)
    
    # Appliquer l'opérateur
    if operateur == '+':
        return val_gauche + val_droite
    elif operateur == '-':
        return val_gauche - val_droite
    elif operateur == '*':
        return val_gauche * val_droite
    elif operateur == '/':
        return val_gauche / val_droite
    elif operateur == '**':
        return val_gauche ** val_droite

# Exemple: (3 + 5) * (10 - 2)
expression = ('*', ('+', 3, 5), ('-', 10, 2))
print(evaluer_expression(expression))  # 64

# === 3. Compression de données (RLE récursif) ===

def rle_encoder(s):
    """Run-Length Encoding récursif"""
    if not s:
        return []
    
    # Compter occurrences du premier caractère
    char = s[0]
    count = 1
    
    while count < len(s) and s[count] == char:
        count += 1
    
    # Récursion sur le reste
    return [(char, count)] + rle_encoder(s[count:])

def rle_decoder(encoded):
    """Décodage RLE récursif"""
    if not encoded:
        return ""
    
    char, count = encoded[0]
    return char * count + rle_decoder(encoded[1:])

original = "aaabbccccdd"
encoded = rle_encoder(original)
decoded = rle_decoder(encoded)

print(f"Original: {original}")
print(f"Encodé: {encoded}")
print(f"Décodé: {decoded}")

# === SORTIE CONSOLE ===
# Original: aaabbccccdd
# Encodé: [('a', 3), ('b', 2), ('c', 4), ('d', 2)]
# Décodé: aaabbccccdd
#
# Explication du Run-Length Encoding (RLE):
# Technique de compression qui remplace les séquences répétées
# par (caractère, nombre_de_répétitions)
#
# Encodage détaillé de "aaabbccccdd":
#
# rle_encoder("aaabbccccdd")
#   char = 'a', count = 3
#   [('a', 3)] + rle_encoder("bbccccdd")
#     char = 'b', count = 2
#     [('b', 2)] + rle_encoder("ccccdd")
#       char = 'c', count = 4
#       [('c', 4)] + rle_encoder("dd")
#         char = 'd', count = 2
#         [('d', 2)] + rle_encoder("")
#           Chaîne vide -> return []
#         return [('d', 2)]
#       return [('c', 4), ('d', 2)]
#     return [('b', 2), ('c', 4), ('d', 2)]
#   return [('a', 3), ('b', 2), ('c', 4), ('d', 2)]
#
# Visualisation pas à pas:
# "aaabbccccdd"
#  ^^^          -> 'a' apparaît 3 fois -> ('a', 3)
#     ^^        -> 'b' apparaît 2 fois -> ('b', 2)
#       ^^^^    -> 'c' apparaît 4 fois -> ('c', 4)
#           ^^  -> 'd' apparaît 2 fois -> ('d', 2)
#
# Décodage détaillé de [('a', 3), ('b', 2), ('c', 4), ('d', 2)]:
#
# rle_decoder([('a', 3), ('b', 2), ('c', 4), ('d', 2)])
#   char='a', count=3
#   "aaa" + rle_decoder([('b', 2), ('c', 4), ('d', 2)])
#     char='b', count=2
#     "bb" + rle_decoder([('c', 4), ('d', 2)])
#       char='c', count=4
#       "cccc" + rle_decoder([('d', 2)])
#         char='d', count=2
#         "dd" + rle_decoder([])
#           Liste vide -> return ""
#         return "dd"
#       return "cccc" + "dd" = "ccccdd"
#     return "bb" + "ccccdd" = "bbccccdd"
#   return "aaa" + "bbccccdd" = "aaabbccccdd"
#
# Efficacité de la compression:
# Original: "aaabbccccdd" = 11 caractères
# Encodé: 4 tuples = [('a',3), ('b',2), ('c',4), ('d',2)]
# Gain: 11 -> 4 éléments (63% de réduction dans la représentation)
#
# Cas où RLE est efficace:
# "aaaaaaaaaa" -> [('a', 10)] (excellente compression)
# "aaabbbcccdddeee" -> [('a',3), ('b',3), ('c',3), ('d',3), ('e',3)]
#
# Cas où RLE est inefficace:
# "abcdefgh" -> [('a',1), ('b',1), ('c',1), ...] (aucune compression)
#
# Applications réelles:
# - Compression d'images simples (fax, dessins)
# - Codecs vidéo (pour les zones uniformes)
# - Compression de données avec beaucoup de répétitions


[OK] RESSOURCES ET RÉFÉRENCES

# === Documentation officielle ===
# Python Recursion Limit:
# https://docs.python.org/3/library/sys.html#sys.setrecursionlimit

# functools.lru_cache:
# https://docs.python.org/3/library/functools.html#functools.lru_cache

# === Livres recommandés ===
# - "Introduction to Algorithms" (CLRS)
# - "The Algorithm Design Manual" (Skiena)
# - "Structure and Interpretation of Computer Programs" (SICP)

# === Concepts à étudier ensuite ===
# 1. Dynamic Programming (programmation dynamique)
# 2. Divide and Conquer (diviser pour régner)
# 3. Backtracking (retour sur trace)
# 4. Tree Traversal (parcours d'arbres)
# 5. Graph Algorithms (algorithmes de graphes)
# 6. Memoization techniques (techniques de mémoïsation)
# 7. Tail Call Optimization (optimisation des appels terminaux)


[OK] CHECKLIST POUR ÉCRIRE UNE FONCTION RÉCURSIVE

# [ ] 1. Identifier le cas de base
#        - Quand la récursion doit-elle s'arrêter?
#        - Y a-t-il plusieurs cas de base?

# [ ] 2. Définir le cas récursif
#        - Comment décomposer le problème?
#        - Les paramètres se rapprochent-ils du cas de base?

# [ ] 3. Assurer la convergence
#        - Chaque appel récursif progresse-t-il vers le cas de base?
#        - Pas de boucle infinie possible?

# [ ] 4. Vérifier les cas limites
#        - Valeurs négatives, zéro, None
#        - Listes vides, chaînes vides
#        - Types inattendus

# [ ] 5. Considérer la performance
#        - Calculs redondants? -> Mémoïsation
#        - Trop profond? -> Itération ou récursion terminale
#        - Complexité acceptable?

# [ ] 6. Tester exhaustivement
#        - Cas de base
#        - Cas simples
#        - Cas complexes
#        - Cas limites

# [ ] 7. Documenter
#        - Expliquer la logique
#        - Donner des exemples
#        - Mentionner les limites


[OK] ANTIPATTERNS À ÉVITER

# [X] 1. Pas de cas de base
def erreur_infinie(n):
    return erreur_infinie(n - 1)  # ERREUR!

# [X] 2. Cas de base inaccessible
def erreur_base(n):
    if n == 10:  # Jamais atteint si n != 10
        return 0
    return n + erreur_base(n + 1)

# [X] 3. Modification de liste mutable
def erreur_mutable(liste=[]):  # Défaut mutable!
    if len(liste) > 5:
        return liste
    liste.append(1)
    return erreur_mutable(liste)

# [X] 4. Slicing inefficace
def erreur_slice(liste):
    if not liste:
        return 0
    return liste[0] + erreur_slice(liste[1:])  # O(n) à chaque fois!

# [X] 5. Calculs redondants sans cache
def erreur_fib(n):  # O(2^n) - TRÈS LENT!
    if n <= 1:
        return n
    return erreur_fib(n - 1) + erreur_fib(n - 2)

# [OK] SOLUTIONS
def bon_slice(liste, index=0):
    if index >= len(liste):
        return 0
    return liste[index] + bon_slice(liste, index + 1)

@lru_cache(maxsize=None)
def bon_fib(n):
    if n <= 1:
        return n
    return bon_fib(n - 1) + bon_fib(n - 2)


[OK] QUIZ FINAL - TESTEZ VOS CONNAISSANCES

# === Question 1: Quelle est l'erreur? ===
def mystere(n):
    if n == 0:
        return 1
    return n * mystere(n)
# Réponse: Pas de progression vers le cas de base (n reste inchangé)

# === Question 2: Quelle est la complexité? ===
def fonction_x(n):
    if n <= 1:
        return n
    return fonction_x(n - 1) + fonction_x(n - 2)
# Réponse: O(2^n) - exponentielle

# === Question 3: Comment optimiser? ===
def lent(n):
    if n <= 1:
        return n
    return lent(n - 1) + lent(n - 2)

# Réponse: Mémoïsation
@lru_cache(maxsize=None)
def rapide(n):
    if n <= 1:
        return n
    return rapide(n - 1) + rapide(n - 2)

# === Question 4: Que retourne ceci? ===
def quiz(n):
    if n <= 0:
        return 0
    return 1 + quiz(n // 2)

print(quiz(16))
# Réponse: 5 (compte le nombre de divisions par 2 jusqu'à 0)
# C'est essentiellement log2(n) + 1

# === SORTIE CONSOLE ===
# 5
#
# Exécution détaillée de quiz(16):
# quiz(16): 16 > 0 -> retourne 1 + quiz(16 // 2 = 8)
#   quiz(8): 8 > 0 -> retourne 1 + quiz(8 // 2 = 4)
#     quiz(4): 4 > 0 -> retourne 1 + quiz(4 // 2 = 2)
#       quiz(2): 2 > 0 -> retourne 1 + quiz(2 // 2 = 1)
#         quiz(1): 1 > 0 -> retourne 1 + quiz(1 // 2 = 0)
#           quiz(0): 0 <= 0 -> retourne 0 (cas de base)
#         = 1 + 0 = 1
#       = 1 + 1 = 2
#     = 1 + 2 = 3
#   = 1 + 3 = 4
# = 1 + 4 = 5
#
# Analyse:
# Cette fonction compte combien de fois on peut diviser n par 2 jusqu'à 0
# 16 -> 8 -> 4 -> 2 -> 1 -> 0  (5 divisions)
#
# C'est équivalent à calculer: floor(log₂(16)) + 1 = 4 + 1 = 5
#
# Autres exemples:
# quiz(1) = 1 (1 -> 0)
# quiz(2) = 2 (2 -> 1 -> 0)
# quiz(4) = 3 (4 -> 2 -> 1 -> 0)
# quiz(8) = 4 (8 -> 4 -> 2 -> 1 -> 0)
# quiz(15) = 4 (15 -> 7 -> 3 -> 1 -> 0)
# quiz(32) = 6 (32 -> 16 -> 8 -> 4 -> 2 -> 1 -> 0)
#
# Application: Calculer le nombre de bits nécessaires pour représenter n

# === Question 5: Récursion terminale? ===
def est_terminale(n):
    if n <= 1:
        return 1
    return n * est_terminale(n - 1)
# Réponse: NON - multiplication après l'appel récursif

def vraiment_terminale(n, acc=1):
    if n <= 1:
        return acc
    return vraiment_terminale(n - 1, n * acc)
# Réponse: OUI - appel récursif est la dernière opération


[OK] EXERCICES AVANCÉS AVEC SOLUTIONS

# === Exercice 1: Anagrammes ===

def generer_anagrammes(s):
    """Génère toutes les anagrammes d'une chaîne"""
    if len(s) <= 1:
        return [s]
    
    anagrammes = []
    
    for i, char in enumerate(s):
        reste = s[:i] + s[i+1:]
        
        for anagramme in generer_anagrammes(reste):
            anagrammes.append(char + anagramme)
    
    return anagrammes

print(generer_anagrammes("abc"))
# ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

# === SORTIE CONSOLE ===
# ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
#
# Exécution détaillée de generer_anagrammes("abc"):
#
# Niveau 1: Traiter "abc"
# Pour chaque caractère en position i:
#
# i=0, char='a', reste="bc"
#   Anagrammes de "bc":
#     i=0, char='b', reste="c" -> ["c"]
#       Résultat: ['bc']
#     i=1, char='c', reste="b" -> ["b"]
#       Résultat: ['cb']
#   Anagrammes de "bc" = ['bc', 'cb']
#   Ajouter 'a' devant: ['abc', 'acb']
#
# i=1, char='b', reste="ac"
#   Anagrammes de "ac":
#     i=0, char='a', reste="c" -> ["c"]
#       Résultat: ['ac']
#     i=1, char='c', reste="a" -> ["a"]
#       Résultat: ['ca']
#   Anagrammes de "ac" = ['ac', 'ca']
#   Ajouter 'b' devant: ['bac', 'bca']
#
# i=2, char='c', reste="ab"
#   Anagrammes de "ab":
#     i=0, char='a', reste="b" -> ["b"]
#       Résultat: ['ab']
#     i=1, char='b', reste="a" -> ["a"]
#       Résultat: ['ba']
#   Anagrammes de "ab" = ['ab', 'ba']
#   Ajouter 'c' devant: ['cab', 'cba']
#
# Résultat final: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
#
# Visualisation en arbre:
#                    "abc"
#          /           |            \
#      'a'+"bc"    'b'+"ac"      'c'+"ab"
#       /    \       /    \        /    \
#   "abc" "acb"  "bac" "bca"   "cab" "cba"
#
# Formule générale:
# Pour une chaîne de n caractères uniques:
# Nombre d'anagrammes = n! (factorielle)
# "abc" -> 3! = 6 anagrammes [OK]
# "abcd" -> 4! = 24 anagrammes
#
# Complexité:
# - Temporelle: O(n × n!) car on génère n! anagrammes de longueur n
# - Spatiale: O(n!) pour stocker tous les résultats

# === Exercice 2: Plus longue sous-séquence croissante ===

def lsc_recursive(liste, index=0, prev=float('-inf')):
    """Longueur de la plus longue sous-séquence strictement croissante"""
    # Cas de base: fin de liste
    if index >= len(liste):
        return 0
    
    # Option 1: Ne pas inclure l'élément courant
    sans = lsc_recursive(liste, index + 1, prev)
    
    # Option 2: Inclure l'élément courant (si possible)
    avec = 0
    if liste[index] > prev:
        avec = 1 + lsc_recursive(liste, index + 1, liste[index])
    
    return max(sans, avec)

print(lsc_recursive([10, 9, 2, 5, 3, 7, 101, 18]))  # 4 ([2, 3, 7, 101])

# === SORTIE CONSOLE ===
# 4
#
# Exécution détaillée de lsc_recursive([10, 9, 2, 5, 3, 7, 101, 18]):
# Trouver la plus longue sous-séquence strictement croissante
#
# Liste: [10, 9, 2, 5, 3, 7, 101, 18]
#         0   1  2  3  4  5   6    7
#
# Exploration récursive (arbre de décision simplifié):
#
# lsc(index=0, prev=-inf)
#   Option 1: NE PAS prendre 10
#     lsc(index=1, prev=-inf) -> continue...
#   Option 2: PRENDRE 10 (car 10 > -inf)
#     1 + lsc(index=1, prev=10)
#       Option: NE PAS prendre 9 (car 9 < 10)
#       Option: ne peut pas prendre 9
#       Continue avec 2...
#
# Meilleures sous-séquences trouvées:
# - [2, 5, 7, 101] = longueur 4 [OK] (optimal)
# - [2, 3, 7, 101] = longueur 4 [OK] (optimal)
# - [2, 5, 7, 18] = longueur 4 [OK]
# - [2, 3, 7, 18] = longueur 4 [OK]
#
# Trace d'une branche réussie [2, 3, 7, 101]:
# index=0, prev=-inf: ne prend pas 10
# index=1, prev=-inf: ne prend pas 9
# index=2, prev=-inf: PREND 2 (2 > -inf) -> longueur partielle = 1
# index=3, prev=2: ne prend pas 5
# index=4, prev=2: PREND 3 (3 > 2) -> longueur partielle = 2
# index=5, prev=3: PREND 7 (7 > 3) -> longueur partielle = 3
# index=6, prev=7: PREND 101 (101 > 7) -> longueur partielle = 4
# index=7, prev=101: ne peut pas prendre 18 (18 < 101)
# index=8: fin de liste -> retourne longueur = 4
#
# Visualisation des choix pour [10, 9, 2, 5, 3, 7, 101, 18]:
# [10] -> impossible de continuer (9<10, 2<10)
# [9] -> impossible de continuer (2<9)
# [2] -> peut continuer avec [5,7,101] ou [3,7,101]
#   [2,5] -> peut continuer avec [7,101] ou [7,18]
#     [2,5,7] -> peut continuer avec [101] ou [18]
#       [2,5,7,101] -> longueur = 4 [OK]
#       [2,5,7,18] -> longueur = 4 [OK]
#   [2,3] -> peut continuer avec [7,101] ou [7,18]
#     [2,3,7] -> peut continuer avec [101] ou [18]
#       [2,3,7,101] -> longueur = 4 [OK]
#       [2,3,7,18] -> longueur = 4 [OK]
#
# Complexité: O(2^n) sans mémoïsation (explore toutes les combinaisons)

# === Exercice 3: Somme de chemins dans matrice ===

def somme_chemins_matrice(matrice, x=0, y=0):
    """
    Trouve la somme minimale d'un chemin du coin supérieur gauche
    au coin inférieur droit (uniquement vers le bas ou la droite)
    """
    rows, cols = len(matrice), len(matrice[0])
    
    # Cas de base: destination atteinte
    if x == rows - 1 and y == cols - 1:
        return matrice[x][y]
    
    # Hors limites
    if x >= rows or y >= cols:
        return float('inf')
    
    # Récursion: minimum entre aller en bas ou à droite
    bas = somme_chemins_matrice(matrice, x + 1, y)
    droite = somme_chemins_matrice(matrice, x, y + 1)
    
    return matrice[x][y] + min(bas, droite)

grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
print(somme_chemins_matrice(grid))  # 7 (1->3->1->1->1)

# === SORTIE CONSOLE ===
# 7
#
# Visualisation de la grille avec coordonnées:
#       col0  col1  col2
# row0   [1]   [3]   [1]
# row1   [1]   [5]   [1]
# row2   [4]   [2]   [1]
#
# Départ: (0,0) = 1
# Arrivée: (2,2) = 1
# Mouvements possibles: uniquement BAS ou DROITE
#
# Tous les chemins possibles:
# 1. (0,0)->(0,1)->(0,2)->(1,2)->(2,2) : 1+3+1+1+1 = 7 [OK] OPTIMAL
# 2. (0,0)->(0,1)->(1,1)->(1,2)->(2,2) : 1+3+5+1+1 = 11
# 3. (0,0)->(0,1)->(1,1)->(2,1)->(2,2) : 1+3+5+2+1 = 12
# 4. (0,0)->(1,0)->(1,1)->(1,2)->(2,2) : 1+1+5+1+1 = 9
# 5. (0,0)->(1,0)->(1,1)->(2,1)->(2,2) : 1+1+5+2+1 = 10
# 6. (0,0)->(1,0)->(2,0)->(2,1)->(2,2) : 1+1+4+2+1 = 9
#
# Exécution détaillée avec récursion:
# somme_chemins_matrice(grid, 0, 0)
#   matrice[0][0] = 1
#   min(somme(0,1), somme(1,0)) + 1
#
#   somme(0, 1):  # Aller à droite
#     matrice[0][1] = 3
#     min(somme(0,2), somme(1,1)) + 3
#
#     somme(0, 2):  # Aller à droite
#       matrice[0][2] = 1
#       min(somme(0,3)=inf, somme(1,2)) + 1
#
#       somme(1, 2):  # Aller en bas
#         matrice[1][2] = 1
#         min(somme(1,3)=inf, somme(2,2)) + 1
#
#         somme(2, 2):  # Destination!
#           matrice[2][2] = 1
#           return 1
#
#         return 1 + 1 = 2
#       return 1 + 2 = 3
#     
#     somme(1, 1):  # Aller en bas
#       ... calculs similaires ...
#       return 7
#
#     return 3 + min(3, 7) = 3 + 3 = 6
#
#   somme(1, 0):  # Aller en bas
#     ... calculs ...
#     return 8
#
#   return 1 + min(6, 8) = 1 + 6 = 7
#
# Chemin optimal trouvé (somme = 7):
#   col0  col1  col2
# -> [1] -> [3] -> [1]
#               v
# [1]   [5]   [1]
#               v
# [4]   [2]   [1]
#
# Séquence: 1 -> 3 -> 1 -> 1 -> 1 = 7

# === Exercice 4: Décodage de messages ===

def decoder_message(code):
    """
    Décode un message où 1='A', 2='B', ..., 26='Z'
    Compte le nombre de façons de décoder
    Exemple: "12" peut être "AB" (1,2) ou "L" (12)
    """
    def decode_helper(s, index, memo):
        # Cas de base: fin de chaîne
        if index == len(s):
            return 1
        
        # Mémoïsation
        if index in memo:
            return memo[index]
        
        # Chiffre 0 invalide seul
        if s[index] == '0':
            return 0
        
        # Option 1: Prendre 1 chiffre
        ways = decode_helper(s, index + 1, memo)
        
        # Option 2: Prendre 2 chiffres (si valide)
        if index + 1 < len(s):
            deux_chiffres = int(s[index:index+2])
            if deux_chiffres <= 26:
                ways += decode_helper(s, index + 2, memo)
        
        memo[index] = ways
        return ways
    
    return decode_helper(code, 0, {})

print(decoder_message("12"))   # 2 ("AB" ou "L")
print(decoder_message("226"))  # 3 ("BZ", "VF", "BBF")

# === SORTIE CONSOLE ===
# 2
# 3
#
# Codage: 1=A, 2=B, 3=C, ..., 26=Z
#
# Exécution détaillée de decoder_message("12"):
# "12" peut être décodé de 2 façons:
#
# Façon 1: "1" + "2"
#   "1" = 'A'
#   "2" = 'B'
#   Résultat: "AB"
#
# Façon 2: "12"
#   "12" = 'L' (12ème lettre)
#   Résultat: "L"
#
# Arbre de décision pour "12":
#                "12"
#               /    \
#         "1"|"2"   "12"|""
#           |         |
#          "AB"      "L"
#
# Total: 2 façons
#
# Exécution détaillée de decoder_message("226"):
# "226" peut être décodé de 3 façons:
#
# Façon 1: "2" + "2" + "6"
#   "2" = 'B'
#   "2" = 'B'
#   "6" = 'F'
#   Résultat: "BBF"
#
# Façon 2: "22" + "6"
#   "22" = 'V' (22ème lettre)
#   "6" = 'F'
#   Résultat: "VF"
#
# Façon 3: "2" + "26"
#   "2" = 'B'
#   "26" = 'Z' (26ème lettre)
#   Résultat: "BZ"
#
# Arbre de décision pour "226":
#                    "226"
#                   /     \
#            "2"|"26"    "22"|"6"
#             /    \         |
#      "2"|"6"  "26"|""    "6"|""
#        |         |         |
#      "BBF"      "BZ"      "VF"
#
# Total: 3 façons
#
# Trace récursive avec mémoïsation pour "226":
# decode_helper("226", 0, {})
#   "2" n'est pas '0' [OK]
#   Option 1: Prendre "2" (1 chiffre)
#     ways = decode_helper("226", 1, {})
#       "2" n'est pas '0' [OK]
#       Option 1a: Prendre "2"
#         ways = decode_helper("226", 2, {})
#           "6" n'est pas '0' [OK]
#           Option: Prendre "6"
#             ways = decode_helper("226", 3, {})
#               index == len -> return 1 <- "BBF" trouvé
#           return 1
#       Option 1b: Prendre "22" (≤26 [OK])
#         ways += decode_helper("226", 3, {})
#           index == len -> return 1 <- "VF" trouvé
#       memo[1] = 1 + 1 = 2
#       return 2
#   Option 2: Prendre "22" (2 chiffres, ≤26 [OK])
#     ways += decode_helper("226", 2, {})
#       "6" n'est pas '0' [OK]
#       Option: Prendre "6"
#         return 1 <- "BZ" trouvé
#   memo[0] = 2 + 1 = 3
#   return 3
#
# Cas invalides:
# "06" -> 0 façon (commence par 0)
# "230" -> 0 façon ("30" > 26)
# "27" -> 1 façon ("2"+"7" = "BG" seulement, car "27" > 26)

# === Exercice 5: Découper chaîne en mots ===

def decouper_en_mots(s, dictionnaire):
    """
    Vérifie si une chaîne peut être découpée en mots du dictionnaire
    """
    def helper(s, memo):
        # Cas de base
        if not s:
            return True
        
        if s in memo:
            return memo[s]
        
        # Essayer tous les préfixes possibles
        for i in range(1, len(s) + 1):
            prefixe = s[:i]
            
            if prefixe in dictionnaire:
                if helper(s[i:], memo):
                    memo[s] = True
                    return True
        
        memo[s] = False
        return False
    
    return helper(s, {})

dico = {"chat", "souris", "chien", "le", "la"}
print(decouper_en_mots("lechat", dico))        # True
print(decouper_en_mots("lechatsouris", dico))  # True
print(decouper_en_mots("lezebra", dico))       # False

# === SORTIE CONSOLE ===
# True
# True
# False
#
# Exécution détaillée de decouper_en_mots("lechat", dico):
# Dictionnaire: {"chat", "souris", "chien", "le", "la"}
#
# helper("lechat", {})
#   Essayer préfixe "l": pas dans dico
#   Essayer préfixe "le": dans dico [OK]
#     helper("chat", {"lechat": ?})
#       Essayer "c": pas dans dico
#       Essayer "ch": pas dans dico
#       Essayer "cha": pas dans dico
#       Essayer "chat": dans dico [OK]
#         helper("", {"lechat": ?, "chat": ?})
#           Chaîne vide -> return True <- Solution trouvée!
#         memo["chat"] = True
#         return True
#     memo["lechat"] = True
#     return True
#
# Résultat: True
# Découpage: "le" + "chat" [OK]
#
# Exécution détaillée de decouper_en_mots("lechatsouris", dico):
# helper("lechatsouris", {})
#   Essayer préfixe "le": dans dico [OK]
#     helper("chatsouris", {})
#       Essayer "chat": dans dico [OK]
#         helper("souris", {})
#           Essayer "souris": dans dico [OK]
#             helper("", {})
#               return True <- Solution trouvée!
#           memo["souris"] = True
#           return True
#       memo["chatsouris"] = True
#       return True
#   memo["lechatsouris"] = True
#   return True
#
# Résultat: True
# Découpage: "le" + "chat" + "souris" [OK]
#
# Exécution détaillée de decouper_en_mots("lezebra", dico):
# helper("lezebra", {})
#   Essayer préfixe "l": pas dans dico
#   Essayer préfixe "le": dans dico [OK]
#     helper("zebra", {})
#       Essayer "z": pas dans dico
#       Essayer "ze": pas dans dico
#       Essayer "zeb": pas dans dico
#       Essayer "zebr": pas dans dico
#       Essayer "zebra": pas dans dico
#       Aucun préfixe valide trouvé
#       memo["zebra"] = False
#       return False
#   Essayer préfixe "lez": pas dans dico
#   Essayer préfixe "leze": pas dans dico
#   Essayer préfixe "lezeb": pas dans dico
#   Essayer préfixe "lezebr": pas dans dico
#   Essayer préfixe "lezebra": pas dans dico
#   Aucune solution trouvée
#   memo["lezebra"] = False
#   return False
#
# Résultat: False
# Impossible de découper "lezebra" avec les mots du dictionnaire
#
# Arbre de décision pour "lechat":
#        "lechat"
#       /        \
#   "le"|"chat"  autres essais
#       |
#   "chat"|""
#       |
#      True
#
# Avantage de la mémoïsation:
# Si on teste "lechatchat", on ne recalcule pas "chat" deux fois

# === Exercice 6: Expressions parenthésées ===

def evaluer_parentheses(expr):
    """
    Évalue toutes les façons possibles de parenthéser une expression
    Retourne liste de tous les résultats possibles
    """
    # Cas de base: simple nombre
    if expr.isdigit():
        return [int(expr)]
    
    resultats = []
    
    # Essayer chaque opérateur comme pivot
    for i, char in enumerate(expr):
        if char in '+-*':
            # Diviser l'expression
            gauche = evaluer_parentheses(expr[:i])
            droite = evaluer_parentheses(expr[i+1:])
            
            # Combiner tous les résultats
            for g in gauche:
                for d in droite:
                    if char == '+':
                        resultats.append(g + d)
                    elif char == '-':
                        resultats.append(g - d)
                    elif char == '*':
                        resultats.append(g * d)
    
    return resultats

print(evaluer_parentheses("2-1-1"))  # [0, 2] ((2-1)-1=0, 2-(1-1)=2)
print(evaluer_parentheses("2*3-4*5"))  # [-34, -14, -10, -10, 10]

# === SORTIE CONSOLE ===
# [0, 2]
# [-34, -14, -10, -10, 10]
#
# Exécution détaillée de evaluer_parentheses("2-1-1"):
#
# Façon 1: Diviser au premier '-' (position 1)
#   Gauche: "2" -> [2]
#   Droite: "1-1"
#     Diviser au '-' (position 1 de "1-1")
#       Gauche: "1" -> [1]
#       Droite: "1" -> [1]
#       1 - 1 = 0
#     Résultat: [0]
#   2 - 0 = 2
#   Résultat partiel: [2]
#
# Façon 2: Diviser au second '-' (position 3)
#   Gauche: "2-1"
#     Diviser au '-' (position 1 de "2-1")
#       Gauche: "2" -> [2]
#       Droite: "1" -> [1]
#       2 - 1 = 1
#     Résultat: [1]
#   Droite: "1" -> [1]
#   1 - 1 = 0
#   Résultat partiel: [0]
#
# Résultat final: [0, 2]
#
# Visualisation des parenthésages:
# ((2-1)-1) = (1-1) = 0 [OK]
# (2-(1-1)) = (2-0) = 2 [OK]
#
# Exécution détaillée de evaluer_parentheses("2*3-4*5"):
# Expression: 2 * 3 - 4 * 5
# Positions des opérateurs: * à 1, - à 3, * à 5
#
# Tous les parenthésages possibles:
#
# 1. Diviser au '*' (pos 1): (2) * (3-4*5)
#    Gauche: [2]
#    Droite: evaluer("3-4*5")
#      Diviser au '-': (3) - (4*5)
#        4*5 = 20 -> 3-20 = -17
#      Diviser au '*': (3-4) * (5)
#        3-4 = -1 -> -1*5 = -5
#    Résultats droite: [-17, -5]
#    2 * -17 = -34 [OK]
#    2 * -5 = -10 [OK]
#
# 2. Diviser au '-' (pos 3): (2*3) - (4*5)
#    Gauche: evaluer("2*3") = [6]
#    Droite: evaluer("4*5") = [20]
#    6 - 20 = -14 [OK]
#
# 3. Diviser au '*' (pos 5): (2*3-4) * (5)
#    Gauche: evaluer("2*3-4")
#      Diviser au '*': (2) * (3-4)
#        3-4 = -1 -> 2*-1 = -2
#      Diviser au '-': (2*3) - (4)
#        2*3 = 6 -> 6-4 = 2
#    Résultats gauche: [-2, 2]
#    Droite: [5]
#    -2 * 5 = -10 [OK]
#    2 * 5 = 10 [OK]
#
# Résultat final: [-34, -14, -10, -10, 10]
#
# Parenthésages correspondants:
# (2*(3-(4*5))) = 2*(3-20) = 2*-17 = -34
# ((2*3)-(4*5)) = 6-20 = -14
# (2*((3-4)*5)) = 2*(-1*5) = 2*-5 = -10
# (((2*3)-4)*5) = (6-4)*5 = 2*5 = 10
#
# Note: -10 apparaît deux fois car il peut être obtenu par:
# - (2*((3-4)*5))
# - Autre combinaison équivalente

# === Exercice 7: Sac à dos (Knapsack) ===

def sac_a_dos(poids, valeurs, capacite, index=0):
    """
    Problème du sac à dos: maximiser la valeur sans dépasser la capacité
    """
    # Cas de base
    if index >= len(poids) or capacite <= 0:
        return 0
    
    # Option 1: Ne pas prendre l'objet
    sans = sac_a_dos(poids, valeurs, capacite, index + 1)
    
    # Option 2: Prendre l'objet (si possible)
    avec = 0
    if poids[index] <= capacite:
        avec = valeurs[index] + sac_a_dos(
            poids, valeurs, capacite - poids[index], index + 1
        )
    
    return max(sans, avec)

poids = [2, 3, 4, 5]
valeurs = [3, 4, 5, 6]
capacite = 8
print(sac_a_dos(poids, valeurs, capacite))  # 10

# === SORTIE CONSOLE ===
# 10
#
# Problème du sac à dos (Knapsack):
# Objets disponibles:
# - Objet 0: poids=2, valeur=3
# - Objet 1: poids=3, valeur=4
# - Objet 2: poids=4, valeur=5
# - Objet 3: poids=5, valeur=6
# Capacité maximale: 8
#
# Objectif: Maximiser la valeur sans dépasser capacité 8
#
# Exécution récursive:
# sac_a_dos([2,3,4,5], [3,4,5,6], cap=8, index=0)
#
#   Option 1: Ne pas prendre objet 0
#     sac_a_dos(..., cap=8, index=1)
#       ... continue l'exploration ...
#
#   Option 2: Prendre objet 0 (poids=2, valeur=3)
#     3 + sac_a_dos(..., cap=8-2=6, index=1)
#       
#       Option 2.1: Ne pas prendre objet 1
#         sac_a_dos(..., cap=6, index=2)
#
#       Option 2.2: Prendre objet 1 (poids=3, valeur=4)
#         4 + sac_a_dos(..., cap=6-3=3, index=2)
#           
#           Option 2.2.1: Ne pas prendre objet 2 (poids=4 > cap=3)
#             sac_a_dos(..., cap=3, index=3)
#               Ne peut pas prendre objet 3 (poids=5 > cap=3)
#               return 0
#             return 0
#
#           return 4 + 0 = 4
#         return 4
#       return 3 + 4 = 7
#
# Toutes les combinaisons explorées:
#
# 1. Ne rien prendre: valeur=0, poids=0
# 2. Objet 0 seul: valeur=3, poids=2
# 3. Objet 1 seul: valeur=4, poids=3
# 4. Objet 2 seul: valeur=5, poids=4
# 5. Objet 3 seul: valeur=6, poids=5
# 6. Objets 0+1: valeur=7, poids=5 [OK]
# 7. Objets 0+2: valeur=8, poids=6 [OK]
# 8. Objets 0+3: valeur=9, poids=7 [OK]
# 9. Objets 1+2: valeur=9, poids=7 [OK]
# 10. Objets 1+3: valeur=10, poids=8 [OK] OPTIMAL!
# 11. Objets 2+3: valeur=11, poids=9 [X] (dépasse capacité)
# 12. Objets 0+1+2: valeur=12, poids=9 [X] (dépasse)
# 13. Objets 0+1+3: valeur=13, poids=10 [X] (dépasse)
# 14. Objets 0+2+3: valeur=14, poids=11 [X] (dépasse)
# 15. Objets 1+2+3: valeur=15, poids=12 [X] (dépasse)
#
# Solution optimale: Objets 1+3
# - Objet 1: poids=3, valeur=4
# - Objet 3: poids=5, valeur=6
# Total: poids=8 (exact!), valeur=10 [OK]
#
# Arbre de décision (simplifié):
#                    index=0, cap=8
#                   /              \
#        sans obj0              avec obj0 (val+3)
#        index=1, cap=8         index=1, cap=6
#        /        \             /            \
#   sans obj1  avec obj1   sans obj1     avec obj1
#   ...        (val+4)      ...          (val+7)
#              cap=5                     cap=3
#              /    \                    /    \
#         sans    avec                sans   avec
#         obj3    obj3               obj2   obj2
#                (val+10)                   (impossible)
#                cap=0 [OK]
#
# Complexité: O(2^n) sans mémoïsation (explore toutes les combinaisons)

# Version avec mémoïsation
def sac_a_dos_memo(poids, valeurs, capacite):
    memo = {}
    
    def helper(index, cap):
        if index >= len(poids) or cap <= 0:
            return 0
        
        if (index, cap) in memo:
            return memo[(index, cap)]
        
        sans = helper(index + 1, cap)
        
        avec = 0
        if poids[index] <= cap:
            avec = valeurs[index] + helper(index + 1, cap - poids[index])
        
        memo[(index, cap)] = max(sans, avec)
        return memo[(index, cap)]
    
    return helper(0, capacite)

# === Exercice 8: Génération de parenthésages ===

def parenthesages_valides(expression):
    """
    Génère tous les parenthésages valides d'une expression
    """
    if len(expression) == 1:
        return [expression]
    
    resultats = []
    
    # Essayer chaque position pour diviser
    for i in range(1, len(expression), 2):  # Sauter les opérateurs
        for j in range(i + 1, len(expression), 2):
            gauche = parenthesages_valides(expression[:j])
            droite = parenthesages_valides(expression[j:])
            
            for g in gauche:
                for d in droite:
                    resultats.append(f"({g}{expression[j]}{d})")
    
    return resultats

# === Exercice 9: Chemins uniques avec obstacles ===

def chemins_avec_obstacles(grille):
    """
    Compte les chemins dans une grille avec obstacles
    0 = libre, 1 = obstacle
    """
    def helper(x, y):
        # Hors limites ou obstacle
        if (x >= len(grille) or y >= len(grille[0]) or 
            grille[x][y] == 1):
            return 0
        
        # Destination
        if x == len(grille) - 1 and y == len(grille[0]) - 1:
            return 1
        
        # Bas + Droite
        return helper(x + 1, y) + helper(x, y + 1)
    
    if not grille or grille[0][0] == 1:
        return 0
    
    return helper(0, 0)

grille_avec_obs = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]
print(chemins_avec_obstacles(grille_avec_obs))  # 2

# === SORTIE CONSOLE ===
# 2
#
# Visualisation de la grille avec obstacles:
# Légende: 0 = libre, 1 = obstacle
#
#   col0  col1  col2
# 0  [0]  [0]  [0]
# 1  [0]  [X]  [0]    X = obstacle
# 2  [0]  [0]  [0]
#
# Départ: (0,0) en haut à gauche
# Arrivée: (2,2) en bas à droite
# Mouvements: uniquement BAS ou DROITE
#
# Chemins possibles (seulement 2):
#
# Chemin 1: Contourner l'obstacle par le haut
# (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)
#   v       v       v       v       v
# Visuel:
#   [S] -> [•] -> [•]
#   [0]   [X]   [•]
#   [0]   [0] -> [A]
# Longueur: 5 déplacements
#
# Chemin 2: Contourner l'obstacle par le bas
# (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2)
#   v       v       v       v       v
# Visuel:
#   [S]   [0]   [0]
#   [•]   [X]   [0]
#   [•] -> [•] -> [A]
# Longueur: 5 déplacements
#
# Exécution récursive détaillée:
# helper(0, 0)
#   (0,0) n'est pas obstacle [OK]
#   Pas la destination
#   Essayer BAS: helper(1, 0)
#     (1,0) n'est pas obstacle [OK]
#     Pas la destination
#     Essayer BAS: helper(2, 0)
#       (2,0) n'est pas obstacle [OK]
#       Pas la destination
#       Essayer BAS: helper(3, 0) -> hors limites -> return 0
#       Essayer DROITE: helper(2, 1)
#         (2,1) n'est pas obstacle [OK]
#         Pas la destination
#         Essayer BAS: helper(3, 1) -> hors limites -> return 0
#         Essayer DROITE: helper(2, 2)
#           (2,2) est la DESTINATION! -> return 1 [OK] Chemin 2!
#         return 1
#       return 1
#     Essayer DROITE: helper(1, 1)
#       (1,1) EST obstacle -> return 0 [X]
#     return 1 + 0 = 1
#   Essayer DROITE: helper(0, 1)
#     (0,1) n'est pas obstacle [OK]
#     Pas la destination
#     Essayer BAS: helper(1, 1)
#       (1,1) EST obstacle -> return 0 [X]
#     Essayer DROITE: helper(0, 2)
#       (0,2) n'est pas obstacle [OK]
#       Pas la destination
#       Essayer BAS: helper(1, 2)
#         (1,2) n'est pas obstacle [OK]
#         Pas la destination
#         Essayer BAS: helper(2, 2)
#           (2,2) est la DESTINATION! -> return 1 [OK] Chemin 1!
#         Essayer DROITE: helper(1, 3) -> hors limites -> return 0
#         return 1 + 0 = 1
#       Essayer DROITE: helper(0, 3) -> hors limites -> return 0
#       return 1 + 0 = 1
#     return 0 + 1 = 1
#   return 1 + 1 = 2
#
# Résultat: 2 chemins possibles
#
# Si l'obstacle était en (1,0):
# [0] [0] [0]
# [X] [0] [0]
# [0] [0] [0]
# Résultat: 1 chemin (uniquement par le haut)
#
# Si l'obstacle était en (1,2):
# [0] [0] [0]
# [0] [0] [X]
# [0] [0] [0]
# Résultat: 1 chemin (uniquement par le bas)

# === Exercice 10: Longueur de la plus longue palindrome ===

def longueur_palindrome(s):
    """Trouve la longueur de la plus longue sous-séquence palindrome"""
    def helper(s, debut, fin, memo):
        if debut > fin:
            return 0
        if debut == fin:
            return 1
        
        key = (debut, fin)
        if key in memo:
            return memo[key]
        
        # Si les extrémités correspondent
        if s[debut] == s[fin]:
            result = 2 + helper(s, debut + 1, fin - 1, memo)
        else:
            # Essayer sans le début ou sans la fin
            result = max(
                helper(s, debut + 1, fin, memo),
                helper(s, debut, fin - 1, memo)
            )
        
        memo[key] = result
        return result
    
    return helper(s, 0, len(s) - 1, {})

print(longueur_palindrome("bbbab"))  # 4 ("bbbb")
print(longueur_palindrome("cbbd"))   # 2 ("bb")

# === SORTIE CONSOLE ===
# 4
# 2
#
# Exécution détaillée de longueur_palindrome("bbbab"):
# Objectif: Trouver la plus longue sous-séquence palindrome
# Note: sous-séquence ≠ sous-chaîne (pas besoin d'être contigu)
#
# Chaîne: "bbbab"
# Indices:  0 1 2 3 4
#
# helper("bbbab", debut=0, fin=4, {})
#   s[0]='b', s[4]='b' -> égaux! [OK]
#   result = 2 + helper("bbbab", 1, 3, {})
#     s[1]='b', s[3]='a' -> différents
#     option1 = helper("bbbab", 2, 3, {})
#       s[2]='b', s[3]='a' -> différents
#       option1a = helper("bbbab", 3, 3, {})
#         debut == fin -> return 1 (un caractère)
#       option1b = helper("bbbab", 2, 2, {})
#         debut == fin -> return 1
#       return max(1, 1) = 1
#     option2 = helper("bbbab", 1, 2, {})
#       s[1]='b', s[2]='b' -> égaux! [OK]
#       result = 2 + helper("bbbab", 2, 1, {})
#         debut > fin -> return 0
#       return 2 + 0 = 2
#     return max(1, 2) = 2
#   result = 2 + 2 = 4
#
# Sous-séquence palindrome trouvée: "bbbb" (indices 0,1,2,3)
# Explication: b + bb + b = bbbb (longueur 4)
#
# Visualisation:
# "bbbab"
#  vvv v  
# "bbbb" <- palindrome (on ignore le 'a' en position 3)
#
# Exécution détaillée de longueur_palindrome("cbbd"):
# Chaîne: "cbbd"
# Indices:  0 1 2 3
#
# helper("cbbd", 0, 3, {})
#   s[0]='c', s[3]='d' -> différents
#   option1 = helper("cbbd", 1, 3, {})
#     s[1]='b', s[3]='d' -> différents
#     option1a = helper("cbbd", 2, 3, {})
#       s[2]='b', s[3]='d' -> différents
#       option1a-1 = helper("cbbd", 3, 3, {})
#         debut == fin -> return 1
#       option1a-2 = helper("cbbd", 2, 2, {})
#         debut == fin -> return 1
#       return max(1, 1) = 1
#     option1b = helper("cbbd", 1, 2, {})
#       s[1]='b', s[2]='b' -> égaux! [OK]
#       result = 2 + helper("cbbd", 2, 1, {})
#         debut > fin -> return 0
#       return 2 + 0 = 2
#     return max(1, 2) = 2
#   option2 = helper("cbbd", 0, 2, {})
#     ... calculs similaires ...
#     return 1
#   return max(2, 1) = 2
#
# Sous-séquence palindrome trouvée: "bb" (indices 1,2)
#
# Autres exemples:
# "racecar" -> 7 (toute la chaîne est palindrome)
# "abcdef" -> 1 (n'importe quel caractère seul)
# "aabaa" -> 5 (toute la chaîne: "aabaa")
# "abacabad" -> 7 ("aba c aba" ou "aba d aba")
#
# Différence sous-séquence vs sous-chaîne:
# Sous-chaîne: doit être contigu
#   "bbbab" -> plus longue sous-chaîne palindrome = "bbb" (3)
# Sous-séquence: peut sauter des caractères
#   "bbbab" -> plus longue sous-séquence palindrome = "bbbb" (4) [OK]


[OK] PROJETS COMPLETS

# === Projet 1: Évaluateur d'expressions mathématiques ===

class EvaluateurExpression:
    """Évaluateur complet d'expressions avec récursion"""
    
    def __init__(self, expression):
        self.expr = expression.replace(" ", "")
        self.index = 0
    
    def evaluer(self):
        """Point d'entrée principal"""
        return self.expression()
    
    def expression(self):
        """Évalue une expression (addition/soustraction)"""
        result = self.terme()
        
        while self.index < len(self.expr) and self.expr[self.index] in '+-':
            op = self.expr[self.index]
            self.index += 1
            
            if op == '+':
                result += self.terme()
            else:
                result -= self.terme()
        
        return result
    
    def terme(self):
        """Évalue un terme (multiplication/division)"""
        result = self.facteur()
        
        while self.index < len(self.expr) and self.expr[self.index] in '*/':
            op = self.expr[self.index]
            self.index += 1
            
            if op == '*':
                result *= self.facteur()
            else:
                result /= self.facteur()
        
        return result
    
    def facteur(self):
        """Évalue un facteur (nombre ou expression entre parenthèses)"""
        # Parenthèses
        if self.index < len(self.expr) and self.expr[self.index] == '(':
            self.index += 1  # Sauter '('
            result = self.expression()
            self.index += 1  # Sauter ')'
            return result
        
        # Nombre
        return self.nombre()
    
    def nombre(self):
        """Extrait un nombre"""
        debut = self.index
        
        while (self.index < len(self.expr) and 
               (self.expr[self.index].isdigit() or self.expr[self.index] == '.')):
            self.index += 1
        
        return float(self.expr[debut:self.index])

# Utilisation
evaluateur = EvaluateurExpression("3 + 5 * (2 - 8)")
print(evaluateur.evaluer())  # -27.0

# === SORTIE CONSOLE ===
# -27.0
#
# Analyse complète de l'expression "3 + 5 * (2 - 8)":
#
# Étape 1: Nettoyage
# Expression originale: "3 + 5 * (2 - 8)"
# Après nettoyage: "3+5*(2-8)"
#
# Étape 2: Évaluation récursive avec priorité des opérateurs
# Priorité: Parenthèses > Multiplication/Division > Addition/Soustraction
#
# evaluer() appelle expression()
#   expression() traite les + et -
#     Appelle terme() pour obtenir "3"
#       terme() traite les * et /
#         Appelle facteur() pour obtenir 3
#           facteur() lit le nombre 3
#           return 3
#       return 3
#     Trouve '+' à l'index 1
#     Appelle terme() pour "5*(2-8)"
#       facteur() lit 5
#       Trouve '*' à l'index 3
#       Appelle facteur() pour "(2-8)"
#         Trouve '(' -> appel récursif à expression()
#           Appelle terme() pour "2-8"
#             facteur() lit 2
#             return 2
#           Trouve '-' à l'index 1 (dans "2-8")
#           Appelle terme() pour "8"
#             facteur() lit 8
#             return 8
#           return 2 - 8 = -6
#         return -6
#       return 5 * -6 = -30
#     return 3 + -30 = -27
#
# Résultat: -27.0
#
# Vérification manuelle:
# 3 + 5 * (2 - 8)
# = 3 + 5 * (-6)      <- d'abord les parenthèses
# = 3 + (-30)         <- puis la multiplication
# = -27               <- enfin l'addition [OK]
#
# Ordre d'évaluation (pile d'appels):
# 1. expression()
# 2.   terme() -> 3
# 3.   terme() pour "5*(2-8)"
# 4.     facteur() -> 5
# 5.     facteur() pour "(2-8)"
# 6.       expression() pour "2-8"  <- Récursion!
# 7.         terme() -> 2
# 8.         terme() -> 8
# 9.         retourne 2-8 = -6
# 10.    retourne 5*-6 = -30
# 11. retourne 3+-30 = -27
#
# Autres exemples:
# "2+3*4" -> 14 (3*4=12, puis 2+12=14)
# "(2+3)*4" -> 20 (2+3=5, puis 5*4=20)
# "10/2+3" -> 8.0 (10/2=5, puis 5+3=8)
# "2*(3+4)*(5-1)" -> 56 (3+4=7, 5-1=4, 2*7*4=56)

# === Projet 2: Générateur de labyrinthe ===

class GenerateurLabyrinthe:
    """Génère un labyrinthe parfait avec récursion"""
    
    def __init__(self, largeur, hauteur):
        self.largeur = largeur
        self.hauteur = hauteur
        # 0 = mur, 1 = chemin
        self.grille = [[0] * largeur for _ in range(hauteur)]
    
    def generer(self, x=0, y=0):
        """Génère le labyrinthe récursivement (DFS)"""
        self.grille[x][y] = 1
        
        # Directions: haut, droite, bas, gauche
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        import random
        random.shuffle(directions)
        
        for dx, dy in directions:
            nx, ny = x + dx * 2, y + dy * 2
            
            # Vérifier limites
            if (0 <= nx < self.hauteur and 0 <= ny < self.largeur and 
                self.grille[nx][ny] == 0):
                
                # Créer passage
                self.grille[x + dx][y + dy] = 1
                
                # Récursion
                self.generer(nx, ny)
    
    def afficher(self):
        """Affiche le labyrinthe"""
        for ligne in self.grille:
            print(''.join(['█' if cell == 0 else ' ' for cell in ligne]))

# Utilisation
# lab = GenerateurLabyrinthe(21, 21)
# lab.generer()
# lab.afficher()

# === Projet 3: Arbre de décision ===

class NoeudDecision:
    """Noeud d'un arbre de décision"""
    
    def __init__(self, question=None, reponse=None):
        self.question = question
        self.reponse = reponse
        self.oui = None
        self.non = None

class ArbreDecision:
    """Arbre de décision avec parcours récursif"""
    
    def __init__(self):
        self.racine = self.construire_arbre()
    
    def construire_arbre(self):
        """Construit un arbre de décision exemple"""
        # Exemple: Devine l'animal
        racine = NoeudDecision("Est-ce que ça vole?")
        
        racine.oui = NoeudDecision("Est-ce petit?")
        racine.oui.oui = NoeudDecision(reponse="Oiseau")
        racine.oui.non = NoeudDecision(reponse="Avion")
        
        racine.non = NoeudDecision("Est-ce que ça nage?")
        racine.non.oui = NoeudDecision(reponse="Poisson")
        racine.non.non = NoeudDecision("Est-ce que ça a 4 pattes?")
        racine.non.non.oui = NoeudDecision(reponse="Chat")
        racine.non.non.non = NoeudDecision(reponse="Serpent")
        
        return racine
    
    def parcourir(self, noeud=None):
        """Parcourt l'arbre récursivement"""
        if noeud is None:
            noeud = self.racine
        
        # Feuille: réponse finale
        if noeud.reponse:
            print(f"C'est: {noeud.reponse}!")
            return
        
        # Noeud intermédiaire: poser question
        print(noeud.question)
        reponse = input("(oui/non): ").strip().lower()
        
        if reponse == "oui":
            self.parcourir(noeud.oui)
        else:
            self.parcourir(noeud.non)

# Utilisation
# arbre = ArbreDecision()
# arbre.parcourir()


[OK] ASTUCES DE PRO

# === 1. Visualiser récursion avec graphviz ===
"""
Pour visualiser vos arbres récursifs:
pip install graphviz

from graphviz import Digraph

def visualiser_appels_fib(n, graph=None, parent=None):
    if graph is None:
        graph = Digraph()
    
    node_id = f"fib_{n}_{id(n)}"
    graph.node(node_id, f"fib({n})")
    
    if parent:
        graph.edge(parent, node_id)
    
    if n > 1:
        visualiser_appels_fib(n-1, graph, node_id)
        visualiser_appels_fib(n-2, graph, node_id)
    
    return graph

# graph = visualiser_appels_fib(5)
# graph.render('fibonacci_calls', view=True)
"""

# === 2. Profiling de fonctions récursives ===

import cProfile
import pstats

def profiler_fonction(func, *args):
    """Profile une fonction récursive"""
    profiler = cProfile.Profile()
    profiler.enable()
    
    result = func(*args)
    
    profiler.disable()
    stats = pstats.Stats(profiler)
    stats.sort_stats('cumulative')
    stats.print_stats(10)
    
    return result

# Utilisation
# profiler_fonction(fibonacci, 20)

# === 3. Tracer avec sys.settrace ===

import sys

def tracer_recursion(func):
    """Trace tous les appels récursifs"""
    appels = []
    
    def trace_calls(frame, event, arg):
        if event == 'call' and frame.f_code.co_name == func.__name__:
            args = frame.f_locals.copy()
            appels.append(args)
        return trace_calls
    
    def wrapper(*args, **kwargs):
        appels.clear()
        sys.settrace(trace_calls)
        result = func(*args, **kwargs)
        sys.settrace(None)
        
        print(f"Nombre d'appels: {len(appels)}")
        return result
    
    return wrapper

@tracer_recursion
def fact_trace(n):
    if n <= 1:
        return 1
    return n * fact_trace(n - 1)

# === 4. Convertir récursion en générateur ===

def fibonacci_gen(n):
    """Générateur pour Fibonacci sans récursion"""
    a, b = 0, 1
    for _ in range(n + 1):
        yield a
        a, b = b, a + b

# Utilisation
for i, fib in enumerate(fibonacci_gen(10)):
    print(f"F({i}) = {fib}")


[OK] CONCLUSION

# La récursivité est un outil puissant mais à utiliser avec sagesse:

# [OK] QUAND UTILISER LA RÉCURSIVITÉ:
# - Problèmes naturellement récursifs (arbres, graphes)
# - Code plus clair et lisible
# - Backtracking et divide-and-conquer
# - Structures de données récursives

# [X] QUAND ÉVITER LA RÉCURSIVITÉ:
# - Grandes profondeurs (risque de stack overflow)
# - Performance critique sans mémoïsation
# - Solution itérative plus simple

# [OBJECTIF] RÈGLES D'OR:
# 1. TOUJOURS définir un cas de base clair
# 2. S'assurer que chaque appel progresse vers le cas de base
# 3. Considérer la mémoïsation pour éviter recalculs
# 4. Tester avec petites valeurs d'abord
# 5. Documenter la logique récursive

# [RAPIDE] POUR ALLER PLUS LOIN:
# - Tail Call Optimization (TCO)
# - Continuation-Passing Style (CPS)
# - Trampolines
# - Co-récursion
# - Récursion mutuelle avancée

# Bon code récursif! [BRAVO]
