# -*- coding: utf-8 -*-
"""
TP8 : Récursivité - Corrigé

PCSI2 - Albert Schweitzer - Le Raincy
"""


##Q2
def suite(f, u0:float, n:int) -> float:
    '''
    Renvoie le nieme terme de la suite définie
    par u(k+1) = f(u(k)). Fonction récursive
    '''
    if n == 0:
        return u0
    else:
        return f(suite(f, u0, n-1))
from math import sin
print(suite(sin, 1, 10))

##Q3
def PGCD(a:int, b:int) -> int:
    '''
    Renvoie le PGCD de a et b. Fonction réc.
    Précondition : a>= b >= 0
    '''
    if b == 0:
        return a
    else:
        return PGCD(b, a%b)

##Q4
def binom(n:int, p:int) -> int:
    '''
    Renvoie p parmi n. Fonction récursive. Précondition : p, n >= 0
    '''
    if p > n:
        return 0
    if n == 0 or p == 0 or p == n:
        return 1
    else:
        return binom(n-1, p) + binom(n-1, p-1)

##Q5
def fibo_rec1(n:int) -> int:
    '''Renvoie la valeur de Fn.
    Fonction récursive.
    Précondition n>= 0
    '''
    assert n>=0, 'indice négatif'
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibo_rec1(n-1) + fibo_rec1(n-2)

##Q6-7
''' Si n >= 2, alors C(n) = C(n-1) + C(n-2) + 1. On raisonne par récurrence ! On a donc une complexité exponentielle !!
'''

##Q8
def fibo_iter(n:int) -> int:
    '''Renvoie Fn.
    Version itérative.
    Précondition n>=0
    '''
    assert n>=0, 'indice négatif'
    if n == 0:
        return 0
    a = 0 #F(n-2)
    b = 1 #F(n-1)
    for i in range(n-1):
        c = a + b #F(n)
        #On décale
        a = b
        b = c
    return b

'''
On a cette fois une complexité linéaire : O(n).
'''
##Q9
valeurs = [0 , 1]
def fibo_rec2(n:int) -> int:
    '''Fonction récursive qui renvoie Fn
    en sauvegardant les valeurs calculées
    dans la liste valeurs
    '''
    if len(valeurs) > n:
        return valeurs[n]
    else:
        v = fibo_rec2(n-1) + fibo_rec2(n-2)
        valeurs.append(v)
        return v

##Q10
"""
Elle renvoie True si L est triée par ordre croissant et False sinon
"""

##Q11
def max_liste(L):
    if len(L) == 1:
        return L[0]
    else:
        m = max_liste(L[1:])
        if m > L[0]:
            return m
        else:
            return L[0]

##Q12
def max_liste(L):
    def max_aux(L, i):
        """
        Renvoie le maximum de L[i:]
        """
        if i == len(L) - 1:
            return L[i]
        else:
            m = max_aux(L, i + 1)
            if m > L[i]:
                return m
            else:
                return L[i]
        return max_aux(L, 0)

##Q13
def recherche(L, e):
    def aux(L, e, i):
        """
        Renvoie True si e est dans L[i:]
        """
        if i >= len(L):
            return False
        else:
            if L[i] == e:
                return True
            else:
                return aux(L, e, i+1)
    return aux(L, e, 0)

##Q14
def recherche_dicho_aux(L:list, g:int, d:int, e) -> bool:
    '''
    Renvoie True si e est dans L[g:d].
    Fonction récursive et dichotomique
    '''
    if g >= d: #La liste est vide
        return False
    else:
        m = (g+d)//2
        if L[m] == e:
            return True
        elif L[m] > e:
            return recherche_dicho_aux(L, g, m, e)
        else:
            return recherche_dicho_aux(L, m + 1, d, e)

##Q15
def recherche_dicho(L:list, e) -> bool:
    return recherche_dicho_aux(L, 0, len(L), e)
##Q16
def prem_occ(L:list, e) -> int:
    '''
    Renvoie l'indice de la première occurence
    de e dans L ou bien -1 si e n'est pas dans L
    '''
    def aux(g:int, d:int) -> int:
        '''
        Renvoie l'indice de la première occurence
    de e dans L[g:d+1] ou bien -1 si e n'est pas dans L[g:d+1]
        '''
        if g == d:
            if L[g] == e:
                return g
            else:
                return -1
        else:
            m = (g+d)//2
            if L[m] >= e:
                return aux(g, m)
            else:
                return aux(m+1, d)
    return aux(0, len(L)-1)

##Q17
'''
C'est une suite géométrique ! u(n) = a^(n+1).
'''

##Q18
def u(a:float, n:int) -> float:
    '''Fonction récursive qui renvoie a**(n+1)
    Précondition n>=0
    '''
    assert n>= 0, 'puissance négative'
    if n == 0:
        return a
    else:
        return a*u(a,n-1)

##Q19
'''
On effectue 1 multiplication à chaque appel de
u(a,n) lorsque n>0, donc on fait 128 multiplications.
'''

##Q20-Q21
'''
Pour n>=1, on a C(n) = C(n-1) + 1 et C(0) = 1
Donc C(n) = n+1.
On a une complexité linéaire.
'''

##Q22
def puissanceR(a:float, n:int) -> float:
    '''Renvoie a**n en utilisant la dichotomie
    Précondition n>= 0
    '''
    assert n>= 0, 'puissance négative'
    if n == 0:
        return 1
    elif n%2 == 0:
        b = puissanceR(a, n//2)
        return b**2
    else:
        c = puissanceR(a, n//2)
        return c**2 * a

##Q23
'''
Pour calculer a**128, on calcule ((((((a**2)**2)**2)**2)**2)**2)**2,
donc on fait 7 multiplications.
'''

##Q24-Q25
'''
Pour n>= 1, si n est pair, D(n) = D(n//2) + 1
si n est impair, D(n) = D(n//2) + 2
On prend donc M = 2
On montre par récurrence que D(n) <= M*(log(n) + 1) pour n>= 1
'''

##Q26
'''
Init : P(0) est évidemment vraie.
H : on prend n >= 0, on suppose que P(k) est vraie pour k<=n.
En exécutant puissanceR avec n+1, on exécute une fois puissanceR avec (n+1)//2 qui termine et renvoie a**((n+1)//2) par HR. L'instruction va donc bien terminer et on vérifie dans les deux cas qu'on obtient bien a**(n+1)
'''

##Q27
'''
Il n'y a que la liste vide.
'''

##Q28
'''
Les sous-listes de L sont soit déjà des sous-listes de
L[:len(L)-1], soit ce sont des sous-listes de L[:len(L)-1] avec L[-1] ajouté à la fin.
'''

##Q29
def souslistes(L:list) -> list:
    '''Renvoie les sous-listes de L
    Fonction récursive
    '''
    if len(L) == 0:
        return [[]]
    else:
        M = L[:len(L)-1]
        ssl = souslistes(M)
        n = len(ssl)
        for i in range(n):
            avec_dernier = ssl[i] + [L[-1]] #Créé une nouvelle liste
            ssl.append(avec_dernier)
        return ssl

##Q30
'''
On montre par récurrence la propriété :
P(n) : l'instruction souslistes(L) termine et
 renvoie la liste des sous-listes de la liste L
 pour n'importe quelle liste L de taille n

I : Pour n= 0, c'est évident.
H : on prend n>=0, on suppose que P(n) est vraie.
etc...
'''

##Q31
import matplotlib . pyplot as plt
import numpy as np

##Q32
alpha = np.pi/3

def Koch(n, A, B):
    if n == 1:
        plt.plot([np.real(A), np.real(B)], [np.imag(A), np.imag(B)])
    else:
        u = (B-A)/3
        C = A + u
        D = A + 2*u
        E = C + u*(np.cos (alpha ) +1j*np.sin ( alpha ))
        Koch(n-1, A, C)
        Koch(n-1, C, E)
        Koch(n-1, E, D)
        Koch(n-1, D, B)

##Q33
A = 0 + 0j
B = 4 + 0j
C = B*(np.cos (alpha ) -1j*np.sin ( alpha ))
n = 1
Koch(n, A, B)
Koch(n, C, A)
Koch(n, B, C)
plt.axis('equal')
plt.show()


##Q34-Q35
'''
Si n>= 1, C(n) = 4C(n-1) + 4 : on fait 4 appels
à Koch(n-1,.,.) et 4 affectations.
On a aussi C(0) = 1.
C'est une suite arithmético-géométrique. La raison
est 4, donc C(n) = O(4^n).
'''