Skip to content

Le maximum en récursif☘

Attention

Cette partie est hors programme. La programmation récursive sera au programme de la classe de terminale.

Exercice 1☘

Lire la documentation python sur les slices.

Info

On pourra traduire slice par tranche. Avec la notation liste[i:j] on découpe la liste en tranches, on saucissonne.

On dispose d'une liste L = ['saucisson', 'tranche', 'découpe', 'partage', 'morceau', 'tronçon', 'partie'].

A partir de la documentation sur slice (ou d'autres sources web), pouvez-vous dire comment créer

  • la liste M constituée de tous les éléments de L sauf le premier.
  • la liste N constituée de tous les éléments de L sauf le dernier.
  • la liste K constituée des éléments de L d'indices compris entre 2 et 4 (compris).
  • la liste P constituée des éléments de L d'indice impair.
Une solution

  • la liste M constituée de tous les éléments de L sauf le premier: 

    1
2
    >>> L[1:]
['tranche', 'découpe', 'partage', 'morceau', 'tronçon', 'partie']

  • la liste N constituée de tous les éléments de L sauf le dernier: 

    1
2
    >>> L[:-1]
['saucisson', 'tranche', 'découpe', 'partage', 'morceau', 'tronçon']

  • la liste K constituée des éléments de L d'indices compris entre 2 et 4 (compris): 

    1
2
    >>> L[2:5]
['découpe', 'partage', 'morceau']

  • la liste P constituée des éléments de L d'indice impair: 

    1
2
    >>> L[1::2]
['tranche', 'partage', 'tronçon']

Exercice 2☘

On peut programmer la détermination de la valeur maximale dans une liste de façon récursive comme suit:

1
2
3
4
5
6
7
8
9
def maxi_bin(a,b):
    return a if a > b else b


def element_max(tab):
    if len(tab) == 1:
        return tab[0]
    else:
        return maxi_bin( tab[0], element_max(tab[1:]) )

Votre mission est ici simplement de tester et de chercher à comprendre comment cela fonctionne.

Tests

On peut faire quelques tests au hasard comme suit:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def maxi_bin(a,b):
    return a if a > b else b


def element_max(tab):
    if len(tab) == 1:
        return tab[0]
    else:
        return maxi_bin( tab[0], element_max(tab[1:]) )


# tests
from random import randint

L = [ randint(-20,20) for _ in range(randint(1,10))]

print( max(L) == element_max(L) )
Une aide au décryptage

Cherchons à décomposer la recherche du maximum pour la liste tab = [3,5,2,6,1].

  1. element_max([3,5,2,6,1]) = maxi_bin( tab[0], element_max(tab[1:]) ) soit element_max([3,5,2,6,1]) = maxi_bin( 3, element_max([5, 2, 6, 1]) )
  2. element_max([5, 2, 6, 1]) = maxi_bin( 5, element_max([2, 6, 1]) )
  3. element_max([2, 6, 1]) = maxi_bin( 2, element_max([6, 1]) )
  4. element_max([6, 1]) = maxi_bin( 6, element_max([1]) )
  5. element_max([1]) = 1
  6. maintenant que element_max([1]) est connu, on remonte à l'étape 4: element_max([6, 1]) = maxi_bin( 6, element_max([1]) ) = maxi_bin( 6, 1) = 6.
  7. Maintenant que element_max([6, 1]) est connu, on remonte à l'étape 3: element_max([2, 6, 1]) = maxi_bin( 2, element_max([6, 1]) ) = maxi_bin( 2, 6 ) = 6.
  8. Maintenant que element_max([2, 6, 1]) est connu, on remonte à l'étape 2: element_max([5, 2, 6, 1]) = maxi_bin( 5, element_max([2, 6, 1]) ) = maxi_bin( 5, 6 ) = 6.
  9. Maintenant que element_max([5, 2, 6, 1]) est connu, on remonte à la première étape: element_max([3,5,2,6,1]) = maxi_bin( 3, element_max([5, 2, 6, 1]) ) = maxi_bin( 3, 6 ) = 6.
Quelques affichages

On peut aussi utiliser quelques print:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def maxi_bin(a,b):
    return a if a > b else b


def element_max(tab):
    if len(tab) == 1:
        print(f"Le max de {tab} est {tab[0]}")
        return tab[0]
    else:
        tete = tab[0]
        queue = tab[1:]
        print(f"Le max de {tab} est le max de {tete} et du max de {queue}")
        return maxi_bin(tete, element_max(queue))


# tests
from random import randint
L = [ randint(-20,20) for _ in range(randint(1,10))]
element_max(L)

On obtient par exemple:

1
2
3
4
5
Le max de [-17, 14, -12, 10, 4] est le max de -17 et du max de [14, -12, 10, 4]
Le max de [14, -12, 10, 4] est le max de 14 et du max de [-12, 10, 4]
Le max de [-12, 10, 4] est le max de -12 et du max de [10, 4]
Le max de [10, 4] est le max de 10 et du max de [4]
Le max de [4] est 4

Exercice 3☘

Tester le code suivant:

1
2
3
4
5
L = ['unpack', 'déballer', 'dégrouper', 'séparer', 'dépaqueter']

mot, *queue = L
print(mot)
print(queue)

En déduire une seconde écriture pour la version récursive de la recherche du max dans une liste.

Test du code

On obtient mot = 'unpack' et queue = [ 'déballer', 'dégrouper', 'séparer', 'dépaqueter']

Recherche récursive du max

Un code possible:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def maxi_bin(a,b):
    return a if a > b else b


def element_max(tab):
    if len(tab) == 1:
        return tab[0]
    else:
        tete,*queue = tab
        return maxi_bin( tete, element_max(queue) )


# tests
from random import randint
L = [ randint(-20,20) for _ in range(randint(1,10))]
print( max(L) == element_max(L) )

Variante:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def maxi_bin(a,b):
    return a if a > b else b


def element_max(tab):
    tete, *queue = tab
    return tete if queue == [] else maxi_bin(tete, element_max(queue))


# tests
from random import randint
L = [randint(-20,20) for _ in range(randint(1,10))]
print(max(L) == element_max(L))