# TP 14: RECURSIVITE

# Ce fichier est le "squelette" du TP 14.
# Dans ce document, les lignes à compléter sont notées (LAC)

##################################################################
# EXEMPLE 0 - Définition itérative de la factorielle (que vous connaissez déjà)
##################################################################

def fact_iter(n):
    p =   # (LAC1)
    for k in range(1,n+1):
        ... # (LAC2)
    return p

##################################################################
# EXEMPLE 1 - Définition récursive de la factorielle
##################################################################

def fact_rec(n):
    assert   # on vérifie que n est positif (LAC1)
    if n==0:
        return   # terminaison (LAC2)
    else:
        return   # appel récursif (LAC3)

##################################################################
# EXEMPLE 1 BIS - Définition récursive des coefficients binomiaux
##################################################################

def bino(n,p):
    if n == 0:
        return 0
    if p == 0:
        return   # (LAC1)
    if p == 1:
        return   # (LAC2)
    if p > 0 and n > 0:
        return    # (LAC3)

##################################################################
# FIGURES ALPHANUMERIQUES
##################################################################

# Exemple de l'énoncé

def figure(n):
    if n>0:
        print(n*'*')
        figure(n-1) # appel récursif

# EXERCICE 1

def figureB(n):
    if n>0:
        ... # (LAC1)
        ... # (LAC2)

##################################################################
# ALGORITHME DE RECHERCHE DICHOTOMIQUE RECURSIVE
##################################################################

# EXERCICE 2

def DichoREC(x,L):
    if  : # (LAC1)
        return False
    p =    # indice de l'élément "central" (LAC2)
    if x == L[p]:
        return   # (LAC3)
    elif x < L[p]:
        return DichoREC(...,...) # (LAC4)
    else:
        return DichoREC(...,...) # (LAC5)

##################################################################
# ALGORITHME DE TRI ET RECURSIVITE
##################################################################

# EXERCICE 3 (on demande une fonction non récursive ici)

def Separe(L):
    LG = [L[0]]
    LD = []
    x = L[0]

    # PARTIE A COMPLETER (plusieurs lignes!)

    return LG,LD

# EXERCICE 4 - Algorithme de tri rapide

def TriRapide(L):
    if len(L) < 2:
        return # LAC1

    # PARTIE A COMPLETER

    return