TP - Les tableaux en récursif☘

La fonction étudiée en préambule est nécessaire pour réussir l'ensemble des parties qui suivront. Ces parties sont ensuite globalement indépendantes. Elles ont pour objectif de vous faire travailler de manière récursive les algorithmes sur les tableaux étudiés en classe de 1^ère.

Téléchargez le fichier « à trous » TPD03.21.py (clic droit -> [Enregistrer sous]) et enregistrez-le dans le dossier [D03-Recursivite].

Préambule - Une fonction très utile☘

Complétez le corps de la fonction coupe_tableau() en respectant ses spécifications.
Attention, seule la méthode .append() est autorisée.

def coupe_tableau(tab):
    """
    tab - list, un tableau d'entiers
    Sortie: tuple - le premier élément du tableau,
            puis le tableau des éléments de tab sans le premier
    """
    pass

Vérifiez votre travail en copiant/collant les lignes suivantes dans le programme principal, à la place du commentaire # A compléter ici :
90 91 92 93 94
tab = [randint(0, 20) for x in range(8)] print(tab) elt, tab = coupe_tableau(tab) print(elt) print(tab)
L'exécution de ces lignes doit produire un tableau aléatoire de 8 éléments puis un couple constitué du premier élément de ce tableau et d'un tableau des éléments restant.
```
>>> (executing file "TPD03.21.py")
[7, 4, 9, 4, 3, 4, 8, 13]
7
[4, 9, 4, 3, 4, 8, 13]
```

Important

Il faudra faire appel à la fonction coupe_tableau() pour programmer les éléments demandés dans les parties suivantes.

Partie 1 - Somme des éléments d'un tableau☘

Complétez le corps de la fonction récursive somme_elt() en respectant ses spécifications. Cette fonction doit faire appel à la fonction coupe_tableau().
17 18 19 20 21 22
def somme_elt(tab): """ tab - list, un tableau d'entiers Sortie: int - La somme des éléments du tableau tab """ pass
Une piste
- Identifiez le cas de base.
- Identifiez la récursivité : la somme des éléments d'un tableau est la somme entre ... et ...
Vérifiez votre travail en exécutant votre programme puis en testant les commandes suivantes dans la console :
```
>>> somme_elt([])
0

>>> somme_elt([3])
3

>>> somme_elt([1, 2, 3, 4])
10
```
Sur votre cahier, prouvez que cette fonction termine en exhibant un variant de boucle.

Partie 2 - Appartenance à un tableau☘

Complétez le corps de la fonction récursive appartient() en respectant ses spécifications. Cette fonction doit faire appel à la fonction coupe_tableau().

def appartient(tab, valeur):
    """
    tab - list, un tableau d'entiers
    valeur - int
    Sortie: bool - True si valeur est dans tab, False sinon
    """
    pass

Vérifiez votre travail en exécutant votre programme puis en testant les commandes suivantes dans la console :

>>> appartient([], 3)
False

>>> appartient([3], 3)
True

>>> appartient([1, 2, 3, 4], 3)
True

>>> appartient([1, 2], 3)
False

Partie 3 - Produit des éléments d'un tableau☘

Complétez le corps de la fonction récursive produit_elt() en respectant ses spécifications. Cette fonction doit faire appel à la fonction coupe_tableau().
48 49 50 51 52 53
def produit_elt(tab): """ tab - list, un tableau non vide d'entiers Sortie: int - Le produit des éléments du tableau tab """ pass
Une piste
- Identifiez le cas de base.
- Identifiez la récursivité : le produit des éléments d'un tableau est le produit entre ... et ...
Vérifiez votre travail en exécutant votre programme puis en testant les commandes suivantes dans la console :
```
>>> produit_elt([3])
3

>>> produit_elt([1, 2, 3, 4])
24
```

Partie 4 - Plus petit élément d'un tableau☘

Complétez le corps de la fonction récursive minimum() en respectant ses spécifications. Cette fonction doit faire appel à la fonction coupe_tableau().
43 44 45 46 47 48
def minimum(tab): """ tab - list, un tableau NON VIDE d'entiers Sortie: int - Le plus petit élément du tableau tab """ pass
Une piste
Il peut être utile de définir une fonction auxiliaire...
Vérifiez votre travail en exécutant votre programme puis en testant les commandes suivantes dans la console :
```
>>> minimum([3])
3

>>> minimum([4, 1, 2, 3, 4])
1

>>> minimum([4, 1, 2, 0, 4])
0
```

Partie 5 - Un tableau est-il trié ?☘

Complétez le corps de la fonction récursive est_croissant() en respectant ses spécifications. Cette fonction doit faire appel à la fonction coupe_tableau().

def est_croissant(tab):
    """
    tab - list, un tableau d'entiers
    Sortie: bool - True si les éléments de tab sont rangés par ordre croissant,
            False sinon
    """
    pass

Vérifiez votre travail en exécutant votre programme puis en testant les commandes suivantes dans la console :

>>> est_croissant([3])
True

>>> est_croissant([4, 1, 2, 3, 4])
False

>>> est_croissant([1, 2, 3, 4])
True

Partie 6 - Nombre d'occurence d'un élément dans un tableau☘

Complétez le corps de la fonction récursive nb_occurrences() en respectant ses spécifications. Cette fonction doit faire appel à la fonction coupe_tableau().

def nb_occurrences(tab, valeur):
    """
    tab - list, un tableau d'entiers
    valeur - int
    Sortie: int - Le nombre d'occurences de valeur dans tab
    """
    pass

Vérifiez votre travail en exécutant votre programme puis en testant les commandes suivantes dans la console :
```
>>> nb_occurrences([5, 1, 2, 3, 5], 5)
2

>>> nb_occurrences([1, 2, 3, 4], 5)
0
```

Partie 7 - Comprendre le rôle d'une fonction☘

Effectuez différents tests afin de comprendre le rôle de la fonction ci-dessous :

def mystere(tab, acc = []):
    """
    tab - list
    acc - list, ce tableau est vide par défaut
    Sortie: 
    """
    if tab == [] :
        return acc
    else :
        elt, tab = coupe_tableau(tab)
        if elt not in acc:
            acc.append(elt)
        return mystere(tab, acc)

Complétez le docstring de cette fonction puis renommez cette fonction en lui donnant un nom plus explicite (attention à l'appel récursif).