#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Oct  5 14:03:42 2021

@author: francois
"""
def somme (n): #renvoyer la somme des entiers de 0 à n
    if n == 0:
        return 0
    else:
        return n + somme(n-1)
    

    
import sys
print(sys.getrecursionlimit())
sys.setrecursionlimit(5000)

def fibo (n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibo(n-1)+fibo(n-2)

def fibo_memo (n):
    T = [-1]*(n+1) #-1 veut dire qu'on a pas encore calculé
    Fait = [False]*(n+1) #liste qui dit si le calcul a été fait
    return fibo_memo_aux(n,T,Fait)
    

    
def fibo_memo_aux(n,T,Fait):
    if Fait[n]:
        return T[n]
    else:
        Fait[n] = True
        if n == 0:
            T[0] = 0
            return 0
        elif n == 1:
            T[1] = 1
            return 1
        else:
            T[n] = fibo_memo_aux(n-1,T,Fait) + fibo_memo_aux(n-2,T,Fait)
            return T[n]

def pgcd(a,b):
    if b == 0:
        return a
    else:
        return pgcd(b, a % b)

def pgcd_iteratif(a,b):
    while b != 0:
        (a,b)=(b,a % b)
    return a

def somme_term(n): #retourne la somme des éléments jusqu'à n en utilisant une fonction récursive terminale
    return somme_aux(n,0)

def somme_aux(n,sum): # retourne la somme des éléments jusqu'à n plus sum
    if n == 0:
        return sum
    else:
        return somme_aux(n-1,n+sum)
    

def sommet(n,sum=0): # retourne la somme des éléments jusqu'à n, version plus concise
    if n == 0:
        return sum
    else:
        return sommet(n-1,n+sum)