#########################################
######## TP informatique bio-sép ########
########        2025-2026        ########
#########################################


#########################################
######## Thème 8 : Récursivité ##########
#########################################


## Q1 : fonction puissance

def puissance(x,n) :
    if n==0 : return 1
    return x*puissance(x,n-1)

## Q2a : suite arithmético-géométrique, itératif

def ag_iter(a,b,u0,n) :
    for _ in range(n) :
        u0 = a*u0+b
    return u0

## Q2b : suite arithmético-géométrique, récursif

def ag_recu(a,b,u0,n) :
    if n == 0 : return u0
    return a*ag(a,b,u0,n-1)+b

## Q3a : Un+1 = f(Un), itératif

def suite_iter(u0,f,n) :
    for _ in range(n) :
        u0 = f(u0)
    return u0

## Q3b : Un+1 = f(Un), récursif

def suite_recu(u0,f,n) :
    if n==0 : return u0
    return f(suite_recu(u0,f,n-1))

## Q3c : tests avec f(x) = 16x(1-x)/5

def f(x) :
    return 16*x*(1-x)/5

print(suite_iter(.5,f,12))
print(suite_recu(.5,f,12))

## Q4a : suite de Fibonacci, itératif

def Fibo_iter(n) :
    f0, f1 = 1, 1
    for _ in range(n) :
        f0, f1 = f1, f1+f0
    return f0

## Q4b : suite de Fibonacci, récursif

def Fibo_recu(n) :
    if n <= 1 : return 1
    return Fibo_recu(n-1)+Fibo_recu(n-2)

## Q4c : affichage des termes consécutifs

def affich_Fibo_i(n) :
    for k in range(n+1) :
        print(Fibo_iter(k))

def affich_Fibo_r(n) :
    for k in range(n+1) :
        print(Fibo_recu(k))

# On constate la lenteur des calculs par la méthode
# récursive, lorsque n augmente.

## Q4d : amélioration de la récursivité
## Utilisation d'un dictionnaire
## Méthode générale HORS-PROGRAMME

def Fibo_memo(n) :
    dico = {}
    def f(k) :
        if k in dico :
            return dico[k]
        else :
            if k <= 1 :
                v = 1
            else :
                v = f(k-1)+f(k-2)
        dico[k] = v
        return v
    return f(n)

## Q5 : Récursivité sur des listes ou des chaînes
## La longueur des objets doit strictement diminuer
## à chaque étape

## Q5a : remplacement des termes négatifs

def remplace(L) :
    if len(L) == 0 : return L
    a = L[0]
    if a < 0 : return [0]+remplace(L[1:])
    else : return [a]+remplace(L[1:])

## Q5b : Liste des termes d'une suite récurrente
## du type Un+1 = f(Un)

def liste_suite(u0,f,n) :
    if n==0 : return [u0]
    return [u0]+liste_suite(f(u0),f,n-1)

## Q5c : maximum d'une liste

def maxi(L) :
    if len(L) == 1 : return L[0]
    return max(L[0],maxi(L[1:]))

## Q5d : nombre d'occurences

def noccur(L,e) :
    if len(L) == 0 : return 0
    a = L[0]
    return noccur(L[1:],e) + (a==e)

## Q5e : réplication d'une liste

def replique(L,n) :
    if n == 0 :
        return []
    return L + replique(L,n-1)

## Q5f : retournement d'une liste

def flip(L) :
    if len(L) == 0 : return []
    return flip(L[1:])+[L[0]]

## Q5g : Hörner en récursif

def horner(P,a) :
    '''le polynome P est represente par la liste [a0,a1,...,an]'''
    if len(P) == 0 :
        return 0
    Q = P[1:]
    return P[0]+a*horner(Q,a)

## Q5h : remplacement dans une chaîne

def remplace_caractere(chaine) :
    if len(chaine) == 0 :
        return ''
    l0 = chaine[0]
    if l0 == 'e' :
        l0 = 'o'
    return l0 + remplace_caractere(chaine[1:])

print(remplace_caractere('abeille'))