### Exemple de fonction sans et avec memoïsation
def fibo_rec(n):
    if n <= 1:
        return 1
    else:
        return fibo_rec(n-1) + fibo_rec(n-2)

def fibo_memo(n):
    memo = {}
    def aux(i):
        if i in memo:
            return memo[i]
        else:
            if i <= 1:
                memo[i] = 1
                return memo[i]
            else:
                memo[i] = aux(i-1) + aux(i-2)
                return memo[i]
    return aux(n)

### Exercice 1
# Fonction récursive fournie
def rendu_rec(a_rendre, valeurs_pieces):
    if a_rendre == 0:
        return 0
    else:
        resultats_possibles = []
        for val in valeurs_pieces:
            if val <= a_rendre:
                reste = a_rendre - val
                nb_pieces_pour_reste = rendu_rec(reste, valeurs_pieces)
                nb_pieces_total = nb_pieces_pour_reste + 1
                resultats_possibles.append(nb_pieces_total)
        return min(resultats_possibles)
    
### Exercice 2
def grenouille_rec(hauteurs):
    n = len(hauteurs)
    def aux(depart):
        if depart == n-1:
            return 0
        if depart == n-2:
            return abs(hauteurs[n-2] - hauteurs[n-1])
        saut1 = abs(hauteurs[depart + 1] - hauteurs[depart])
        reste1 = aux(depart + 1)
        cout1  = saut1 + reste1
        saut2 = abs(hauteurs[depart + 2] - hauteurs[depart])
        reste2 = aux(depart + 2)
        cout2 = saut2 + reste2
        return min(cout1, cout2)
    return aux(0)

# Exemple de liste de hauteurs
exemple_hauteurs = [6, 7, 4, 8, 2, 9, 0]

# Génération aléatoire de listes en entrée
from random import randint

def liste_alea(taille):
    return [randint(0, 100) for i in range(taille)]


### Exercice 3

# Exemple de pyramide
ex_pyramide_1 = [
              { 0: 3 },
           { -1: 5 , 1: 4},
         {-2: 1, 0: 5, 2: 9},
      {-3: 2, -1: 6, 1: 5, 3: 3},
    {-4: 5, -2: 8, 0: 9, 2: 7, 4: 9}
    ]

# Fonction fournie
def pyramide_rec(pyr):
    hauteur = len(pyr)
    def aux (ligne, colonne):
        if ligne == hauteur - 1:
            return pyr[ligne][colonne]
        else:
            nombre = pyr[ligne][colonne]
            choix_gauche = nombre + aux(ligne+1, colonne-1)
            choix_droite = nombre + aux(ligne+1, colonne+1)
            return max(choix_gauche, choix_droite)
    return aux(0, 0)

# Génération aléatoire de pyramides d'entiers
def pyramide_alea(taille):
    res = []
    for i in range(taille):
        res.append({j : randint(1, 100) for j in range(-i, i+1, 2)})
    return res