import sys
### Exercice 1
def estDedans(el,list):
    for e in list:
        if e==el:
            return True
    return False
    
def index(el,list):
    for i in range(len(list)):
        if list[i]==el:
            return i
    return -1
    
### Exercice 3
def fibonacci(n):
    if n==0:
        return 0
    def fib(n):
        if n==1:
            return (0,1)
        a,b=fib(n-1)
        return (b,a+b)
    
    return fib(n)[1]

sys.setrecursionlimit(1000000000)
print(fibonacci(fibonacci(fibonacci(fibonacci(7)))))
    
### Exercice 4
somme = lambda f,l: sum([f(s) for s in l])
sommeRec = lambda f,l: 0 if l==0 else f(l)+sommeRec(f,l-1)

id = lambda x:x

print(sommeRec(id,42))


### Exercice 5
fact = lambda x: 1 if x==0 else x*fact(x-1)
catalan = lambda n: fact(2*n)//fact(n)//fact(n+1)