## TP - Récursivité ##

#Q1
def somme(n):
    if n==0:
        return 0
    else :
        return n**5 + somme(n-1)
    
#print(somme(2),1**5+2**5)
#print(somme(4),1**5+2**5+3**5+4**5)

#Q2
def triangle(n):
    if n==1:
        return '*'
    else :
        return n*'*'+'\n'+triangle(n-1)

#print(triangle(10))

#Q3
def triangle2(n):
    if n==1:
        return '*'
    else:
        return triangle2(n-1)+'\n'+n*'*'
    
#print(triangle2(10))

#Q4
def maxrec(L):
    if len(L)==1:
        return L[0]
    else:
        max1=maxrec(L[0:len(L)//2])
        max2=maxrec(L[len(L)//2:])
        #print(max1,max2)
        if max1>max2:
            return max1
        else:
            return max2

#print(maxrec([1,5,9,31,2,4,10,20,30,10,2,5,8,9,15]))

#Q5

def maxrec2(L,a,b):
    if a+1==b:#liste de longueur 1
        return L[a]
    else:
        m=(a+b)//2
        max1=maxrec2(L,a,m)
        max2=maxrec2(L,m,b)
        print(max1,max2)
        if max1>max2:
            return max1
        else:
            return max2
#liste=[1,5,9,31,2,4,10,20,30,10,2,5,8,9,15]

#print(maxrec2(liste,0,len(liste)))

#Q6 et 7
def F(n):
    if n==0 or n==1:
        print("calcul F(",n,")")
        return 1
    else:
        print("calcul F(",n,")")
        return (F(n-1)+F(n-2))
print(F(1000))
    
#Q8
L = [ 1, [ [2,3], 4, [ [5,6], 7] ], [8,9]]

def somme(L):
    s=0
    for k in range(len(L)):
        if isinstance(L[k],int) is True : #si l'élément est un entier
            s+=L[k]
        else:
            s+=somme(L[k])
    return s
print(somme(L))

#Q9
def deplace(A,B):
    print("déplacer disque de",A," vers ", B)

def hanoi(p,A,B):
    if p==1:
        deplace(A,B)
    else:
        C=6-A-B
        hanoi(p-1,A,C)
        hanoi(1,A,B)
        hanoi(p-1,C,B)
hanoi(4,1,3)