##TP - Récursivité

##1.Définition
"""
R.A.S.
"""

##2.D'autres exemples
"""
Question 1 :
"""
def suite(n):
    if n==0 :
        return 3
    else :
        return (1/2)*(suite(n)+(5/suite(n)))

##3.Récursivité sur les listes
"""
Question 2
"""
def somme(L):
    if len(L)==0 :
        return 0
    else :
        return L[0]+somme(L[1:])

"""
Question 3
"""
def produit(L):
    if len(L)==0 :
        return 1
    else :
        return L[0]+produit(L[1:])

"""
Question 4
"""
def maximum(L):
    if len(L)==1 :
        return L[0]
    else :
        m = maximum(L[1:])
        if m<L[0] :
            return L[0]
        else :
            return m

##4.Récursivité sur les chaînes de caractères
##Premières fonctions
"""
Question 5
"""
def estPresent(s,l):
    if s=="" :
        return False
    else :
        s[0]==l or estPresent(s[1:],l)

"""
Question 6
"""
def nbOccurences(s,l):
    if s=="" :
        return 0
    else :
        if s[0]==l :
            return 1+nbOccurences(s[1:],l)
        else :
            return nbOccurences(s[1:],l)

##Palindromùes
"""
Question 7
"""
def estPalindrome(s):
    n = len(s)
    if n<2 :
        return True
    else :
        return s[0]==s[n-1] and estPalindrome(s[1:n-1])

##Anagrammes
"""
Question 8
"""
def anagrammes(s):
    if len(s)==0: #Cas de base, chaîne vide
        return []
    elif len(s)==1: #Cas de base, chaîne de 1 caractère
        return [s[0]]
    else :
        res = []
        for i in range(len(s)) : #On parcourt la chaîne
            if nbOccurences(s[:i],s[i])==0: #Si c'est la première fois qu'on croise la lettre s[i]
                liste = anagrammes(s[:i]+s[i+1:]) #On calcule les anagrammes de la chaîne à laquelle on a retiré s[i]
                for k in range(len(liste)):
                    res.append(s[i]+liste[k]) #On complète ces anagrammes avec la lettre s[i] et on les ajoute dans la liste résultat
        return res

##5.La suite de Fibonacci
"""
Question 9
"""
def fiboit(n):
    a,b = 1,1
    for i in range(n):
        a,b = b,a+b
    return a

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

# On constatera que pour des valeurs élevées de n la version récursive ne marchera plus alors l'itérative y arrive sans problème.

"""
Question 10
"""
def fibo_term(a,b,n):
    if n==0:
        return a
    else :
        return fibo_term(b,a+b,n-1)

def fiborec2(n):
    return fibo_term(1,1,n)

##6.Plus difficile
"""
Question 11
"""

def recherche_dicho(l,a):
    n = len(L)
    m = n//2
    if n==0 :
        return False
    elif a < L[m] :
        return recherche_dicho(l[:m],a)
    else :
        return recherche_dicho(l[m+1:],a)

"""
Question 12
"""
def pgcd_bezout(n1,n2):
    q = n1//n2  #quotient de la division euclidienne
    r = n1%n2   #reste de la division euclidienne
    if r==0 :
        return (n2,0,1)
    else :
        (pgcd,uprime,vprime) = pgcd_bezout(n2,r)
        return (pgcd,vprime,uprime-vprime*q)

"""
Question 13
"""
def supprime_doublon(L):
    n = len(L)
    if n < 2 :
        return L
    else :
        bool = True #booléen servant à tester si le premier élément de la liste est un doublon
        for i in range(2,n):
            if L[i]==L[0] :
                bool = False
        out = supprime_doublon(L[1:])
        if bool :
            out.append(L[0])
        return temp

##7.Les tours de Hanoï
"""
Question 14
"""
#Voir le résultats affiché question 16 avec le paramètre n=3

"""
Question 15
"""
def deplacement(i,j):
    print(i,"->",j)

def Auxiliaire(i,j,k,n):
    if n>0 :
        Auxiliaire(i,k,j,n-1)
        deplacement(i,j)
        Auxiliaire(k,j,i,n-1)

"""
Question 16
"""
def hanoi(n):
    Auxiliaire("A","C","B",n)

hanoi(3)