## Exercice 1

def somme_harmonique(n):
    if n == 1:
        return 1
    else:
        return somme_harmonique(n-1) + 1/n

# ou (le else est inutile puisque return arrête l'exécution de la fonction) :

def somme_harmonique(n):
    if n == 1:
        return 1
    return somme_harmonique(n-1) + 1/n

# En fait en Python on peut même écrire :

def somme_harmonique(n):
    return 1 if n == 1 else somme_harmonique(n-1) + 1/n


## Exercice 2

def syracuse(n):
    print(n, end=" ")
    if n == 1:
        return None    # ne renvoie rien
    elif n % 2 == 0:
        syracuse(n//2)
    else:
        syracuse(n*3+1)


## Exercice 3
        
def bonjour(n):
    if n > 0:
        print("Bonjour")
        bonjour(n-1)


## Exercice 4

def etoiles1(n):
    if n > 0:
       print('*' * n)
       etoiles1(n-1)

def etoiles2(n):
    if n > 0:
       etoiles2(n-1)
       print('*' * n)


## Exercice 5

def dichotomie(f, a, b, epsilon):
    if b-a < epsilon:
        return a, b
    m = (a+b) / 2
    if f(a)*f(m) > 0:
        return dichotomie(f, m, b, epsilon)
    else:
        return dichotomie(f, a, m, epsilon)


## Exercice 6

# 1)

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

# 2) Quand on exécute fibonacci(3), la fonction appelle fibonacci(2) et 
# fibonacci(1), donc en comptant l'appel initial on a 3 appels.

# Quand on exécute fibonacci(4), la fonction appelle fibonacci(3) et 
# fibonacci(2), donc on a 1 + 3 + 1 = 5 appels.

# Quand on exécute fibonacci(5), la fonction appelle fibonacci(4) et 
# fibonacci(3), donc on a 1 + 5 + 3 = 9 appels.

# 4)

N = 0

def fibonacci(n):
    global N
    N = N + 1
    if n == 1 or n == 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

##>>> N = 0
##>>> fibonacci(40)
##102334155
##>>> N
##204668309

## Le nombre d'appels récursifs effectués pour calculer F_n est 2*F_n - 1 (on
## peut le démontrer par récurrence double).

# 5)

d = {1: 1, 2: 1}

def fibonacci(n):
    if n not in d:
        d[n] = fibonacci(n-1) + fibonacci(n-2)
    return d[n]


## Exercice 7

dico_bino = {(0,0): 1}

def binomial(n, p):  # avec la formule de Pascal
    if not 0 <= p <= n:
        return 0
    if (n,p) not in dico_bino:
        dico_bino[(n,p)] = binomial(n-1, p) + binomial(n-1, p-1)
    return dico_bino[(n,p)]


## Exercice 8

# 1)

def produit_cartesien_2(L1, L2):
    produit = []
    for x1 in L1:
        for x2 in L2:
            produit.append([x1, x2])
    return produit

# 2)

def produit_cartesien(L):
    n = len(L)
    if n == 0:
        return [[]]
    produit_rec = produit_cartesien(L[:n-1])
    produit = []
    for p in produit_rec:
        for x in L[n-1]:
            produit.append(p+[x])
    return produit