def f(x):
    x = 2* x
    f(x)
    return x

###
def fact(n : int) -> int :
    p = 1
    for i in range(2, n+1):
        p = p * i
    return p




def fact_rec(n : int) -> int :
    """
    Entrée : n (entier positif ou nul)
    Sortie : n!
    """
    if n == 0:
        return 1
    else:
        return n * fact_rec(n - 1)


###
def suite1(n):
    if n==0:
        return 6
    else :
        return 4*suite1(n-1)-7


def suite2(n):
    if n==0:
        return 6
    else :
        return 4*suite1(n-1)-7*n




def fibonacci(n):
    u = 0
    v = 1
    for i in range(2, n+1 ):
        w = v     # sauvegarde
        v = v + u
        u = w
    return v



def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)





def pascal(n, p):
    ''' renvoie le coeff binomial p parmi n '''
    if p > n:
        return 0
    elif p == 0 or p == n:
        return 1
    return pascal(n-1,p) + pascal(n-1, p-1)







###
def compte_a_rec(chaine, a):
    if len(chaine) == 1:
        if chaine[0] == a:
            return 1
        else:
            return 0
    else:
        if chaine[0] == a:
            return 1 + compte_a_rec(chaine[1:], a)
        else:
            return compte_a_rec(chaine[1:], a)


















###

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





def triangle_bas(n):
    if n > 0:
        print("*" * n)
        triangle_bas(n-1)



def triangle_haut(n):
    if n > 0:
        triangle_haut(n-1)
        print("*" * n)

def figure(n):
    if n > 0:
        print("*" * n)
        figure(n-1)
        print("*" * n)

def mystere(ch):
    """
    Affiche une chaine à l'envers
    """
    if len(ch) >0 :
        mystere(ch[1:])
        print(ch[0], end='')

###
def doublons_rec(L:list) -> list:
    if len(L) <= 1:
        return L
    if L[0] != L[1]:
        return [L[0]] + doublons_rec(L[1:])
    return doublons_rec(L[1:])


def doublons(L: list) -> list:
    G = []
    i = 0
    while i < len(L) - 1:
        if L[i] != L[i+1]:
            G.append(L[i])
        i = i + 1
    G.append(L[i])
    return G


###


def dicho_it(L,e):
    a = 0
    b = len(L)-1
    while a <= b:
        m=(a+b)//2
        if L[m]==e:
            return m
        if L[m]<e:
            a=m+1
        else:
            b=m-1
    return False


def rech_dicho_rec(L, e, deb, fin):
    if deb == fin :
        if L[deb]== e:
            return deb
        else :
            return False
    m = (deb + fin)//2
    if L[m] == e :
        return m
    elif L[m] > e :
        return rech_dicho_rec(L, e, deb, m-1)
    else :
        return rech_dicho_rec(L, e, m+1, fin)