import math

# =============================================
# Exercice 1 : Fibonacci récursif
# =============================================

def fibo(n):
    """Fonction récursive qui renvoie le n-ième terme de Fibonacci
    u0 = 1, u1 = 1, u_n = u_{n-1} + u_{n-2} pour n >= 2"""
    
    # Cas de base : on arrête la récursion
    if n == 0 or n == 1:
        return 1
    
    # Appel récursif : on réduit le problème
    return fibo(n-1) + fibo(n-2)


print("fibo(10) =", fibo(10))
print("fibo(20) =", fibo(20))
# fibo(30) est très long -> on voit que la fonction ralentit énormément


# =============================================
# Exercice 2 : Euclide récursif
# =============================================

def Euclide(a, b):
    """Calcule le PGCD de a et b de façon récursive
    (algorithme d'Euclide)"""
    
    # Cas de base
    if b == 0:
        return a
    
    # Appel récursif : on remplace (a,b) par (b, a%b)
    return Euclide(b, a % b)


print("PGCD(48, 18) =", Euclide(48, 18))


# =============================================
# Exercice 3 : Conversion en base 2 (récursif)
# =============================================

def base2(n):
    """Convertit n en binaire sous forme de liste [bits]
    Exemple : base2(6) -> [1,1,0]  (car 6 = 110 en binaire)"""
    
    # Cas de base
    if n == 0:
        return [0]
    if n == 1:
        return [1]
    
    # Appel récursif : on prend le reste (bit de poids faible)
    # et on divise n par 2
    return base2(n // 2) + [n % 2]


print("base2(6) =", base2(6))
print("base2(13) =", base2(13))


# =============================================
# Exercice 4 : Dichotomie récursive
# =============================================

def dicho(L, m):
    """Recherche dichotomique récursive dans une liste triée L"""
    
    # Cas particuliers demandés
    if len(L) == 0:
        return False
    if len(L) == 1:
        return L[0] == m
    if len(L) == 2:
        return L[0] == m or L[1] == m
    
    # Cas général
    milieu = len(L) // 2
    if L[milieu] == m:
        return True
    elif L[milieu] > m:
        # On cherche dans la moitié gauche
        return dicho(L[:milieu], m)
    else:
        # On cherche dans la moitié droite
        return dicho(L[milieu:], m)


# Test
L_test = [2*i for i in range(50)]   # liste triée : 0, 2, 4, ..., 98
print("10 dans L_test ?", dicho(L_test, 10))
print("11 dans L_test ?", dicho(L_test, 11))


# =============================================
# Exercice 5 : Dessins récursifs
# =============================================

def dessin(n):
    """Affiche un triangle d'étoiles décroissant (n lignes)"""
    if n == 0:
        return
    print("*" * n)          # on affiche la ligne actuelle
    dessin(n-1)             # puis on appelle avec n-1


print("\nDessin(4) :")
dessin(4)


def dessin2(n):
    """Affiche un triangle d'étoiles croissant (n lignes)"""
    if n == 0:
        return
    dessin2(n-1)            # d'abord on fait les lignes du dessus
    print("*" * n)          # puis on affiche la ligne actuelle


print("\nDessin2(4) :")
dessin2(4)


# =============================================
# Exercice 6 : Dessin3 avec fonction auxiliaire
# =============================================

def dessin3aux(n, k):
    """Affiche une figure à n lignes, décalée de k espaces"""
    if n == 0:
        return
    
    # On affiche la ligne actuelle avec k espaces puis \ puis des espaces puis /
    espaces = " " * k
    print(espaces + "\\" + " " * (2*(n-1)) + "/")
    
    dessin3aux(n-1, k+1)   # on passe à la ligne suivante avec +1 espace


def dessin3(n):
    """Affiche la figure complète sans décalage initial"""
    dessin3aux(n, 0)


print("\nDessin3(4) :")
dessin3(4)


# =============================================
# Exercice 7 : Complexité
# =============================================

"""
Exercice 7 - Complexité :

1. Complexité du Crible d'Ératosthène :
   - On a environ n/ln(n) nombres premiers <= n
   - Pour chaque premier p, on barre environ n/p multiples
   - Complexité globale ≈ O(n ln(ln n))

2. Fonction PremierSuivant(n) :
   - Elle renvoie le plus petit nombre premier strictement supérieur à n.
   - Complexité dans le pire cas : O(n ln(ln n)) car on appelle Crible(2n)
"""