"""
Thème 8 : récursivité
"""

import numpy as np
import random as rd
## Q1

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

## Q2a) Programmation itérative suite A-G

def agi(a,b,u0,n): # ag itératif
    u = u0
    for k in range(n):
        u = a*u+b
    return u
## Q2b) Version récursive
def agr(a,b,u0,n): # ag récursif
    if n==0:
        return u0
    else:
        return a*agr(a,b,u0,n-1)+b

# test :
u0,a,b,n = 1,-0.5,4,12
print(agi(a,b,u0,n))
print(agr(a,b,u0,n))


## Programmation suite récurrente


def uIter(u0,n,f):
    u=u0
    for k in range(n):
        u=f(u)
    return u

def uRec(u0,n,f):
    if n==0:
        return u0
    else: # on peut voir un comme le terme
          # de rang n-1 de la même suite
          # que (S) initialisée à u1=f(u0)
        return uRec(f(u0),n-1,f)

# Solution plus intuitive :
def uRec(u0,n,f):
    if n==0:
        return u0
    else:
        return f(uRec(u0,n-1,f))
# Vérif :
def f(x):
    return 16/5*x*(1-x)
u0,n=1/2,12
u,v = uIter(u0,n,f), uRec(u0,n,f)
print(u,v)

## Suite récurrente linéaire à deux pas


def Fibo(n):
    U=[1,1] # liste des n premiers termes
    for k in range(1,n): # je veux un seul
        x = U[-1]+U[-2]  # passage dans la
        U.append(x)      # boucle pour n=2
    return U[n]

# remarque: Fibo(37) = 39088169
# le calcul de F37 prend en moyenne 2.85 microsecondes

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

# Rem 1 : le calcul de F37 prend en moyenne
# 4.24 secondes : 2 000 000 de fois plus lent
# que par une programmation itérative.
# Conclusion : la récursivité ne résout pas
# tous les problèmes : il faut toujours
# chercher un bon compromis entre simplicité
# et efficacité.

# Rem 2 : avec nos connaissances en maths,
# on peut calculer l'expression exacte de Fn
# Fn = [r2**(n+1)-r1**(n+1)]/s
# où s=sqrt(5), r2 = (1+s)/2, r1=(1-s)/2
# comme -1/2<1/s*r1**(n+1)<0, Fibo(n) est
# l'entier le plus  proche de x = 1/s*r2**(n+1)

def Fibo3(n):
    s = np.sqrt(5)
    r2,r1 = (1+s)/2,(1-s)/2
    x = r2**(n+1)/s
    n1 = int(x)
    if (x-n1<0.5):
        return n1
    else:
        return n1+1

## Programmation récursive sur objets structurés
## Q5 a) subtitution d'éléments d'une liste

def remplace(L):
    if len(L)==1:
        return [max(0,L[0])]
    else:
        return [max(0,L[0])]+remplace(L[1:])
# rem : max(0,x) = (x/2 + |x|/2)

## Q5 b) liste des termes d'une suite rec.
def listeSuite(u0,n,f):
    if n==0:
        return [u0]
    else:
        return [u0]+listeSuite(f(u0),n-1,f)

## Q5 c) maximum d'une liste
def maxi(L):
    if len(L)==1:
        return L[0]
    else:
        return max(L[0], maxi(L[1:]))

## Q5 d) nombre d'occurrences dans une liste
def noccur(L,e):
    # Rappel : les listes sont itérables
    if len(L)==1:
        return (0+L[0]==e) # vaut 1 si L[0]=e, 0 sinon
    else:
        return (L[0]==e) + noccur(L[1:],e)

## Q5 e) réplication d'une liste
def replique(L,n):
    if n ==1:
        return L
    else:
        return L + replique(L,n-1)

## Q5 f) renversement des termes d'une liste
# rappel : la liste renversée de L s'obtient
# facilement par slicing : L[::-1].
def flip(L):
    if len(L)==1:
        return L
    else:
        return [L[-1]]+flip(L[:-1])

## Q6 g) Calcul de P(alpha), P polynôme

def eval(P,a):
     # rappel : un poly est représenté par la
     # liste de ses coeffs rangés par ordre
     # croissant des degrés
     if len(P)==1:
         return P[0] # cas où P est constant
     else:
         return P[0] +a*eval(P[1:],a)


def evalP(P,a):
    # Calcul Jack Lang de P(a) : je m'en fiche
    # du coût, c'est pas moi qui paye.
    S=0
    n = len(P)
    for k in range(n):
        S+=P[k]*a**k
    return S

def evaliter(P,a):
    # Calcul Hörner de P(a) :
    # j'optimise les coûts de caclul.
    S=P[-1]
    for coeff in P[::-1][1:]:
        S = a*S+ coeff
    return S

##  Q7 h) substition dans des chaines de carac
# même chose que Q7 a),  mais la grande différence
# entre les listes et les chaines de caractères
# est que LES CHAINES NE SONT PAS MUTABLES

def remplace(chaine):
    if len(chaine)==0:
        return ''
    else:
        c = chaine[0]
        if c=='e':
            return 'o'+remplace(chaine[1:])
        else:
            return c+remplace(chaine[1:])