P
Fiche de révision Python

Fonctions, récursivité et listes

Chapitre 33 — les trois outils de Python qui tombent au bac : les fonctions, qui isolent un calcul, la récursivité, reflet informatique de la récurrence, et les listes, qui servent à énumérer et à dénombrer.

Cas de base = initialisation ; appel récursif = hérédité.

Naviguez avec les flèches ← → du clavier, ou via le Sommaire.

Chapitre 33 Vue d'ensemble

Au programme

Fonctions et récursivité
  • def, return, portée, tests par assert
  • Fonctions en argument, module math
  • Factorielle, Fibonacci, Hanoï, RecursionError
Listes et dénombrement
  • Listes, tranches, compréhensions, chaînes, tuples
  • Diviseurs, crible, combinaisons, triangle de Pascal
  • Coût linéaire, quadratique, exponentiel
L'idée forte

Une fonction renvoie une valeur réutilisable ; une fonction récursive se valide exactement comme une récurrence.

Partie 1 Fonctions

Définir et appeler une fonction

Définition

Une fonction porte un nom, reçoit des paramètres et renvoie une valeur avec return. Définir n'exécute rien : le calcul a lieu à l'appel. Un paramètre peut avoir une valeur par défaut ; la docstring dit ce que fait la fonction.

def carre(x) :
    return x**2

def puissance(x, n=2) :
    """Renvoie x**n, avec n=2 par defaut."""
    p = 1
    for i in range(n) :
        p = p*x
    return p

>>> carre(3), carre(1.5) + 1
(9, 3.25)
>>> puissance(3), puissance(3, 4), puissance(n=3, x=2)
(9, 81, 8)
Partie 1 ★ L'erreur n°1 des copies

print n'est pas return

def bonjour(nom) :
    print("Bonjour", nom)

>>> r = bonjour("Julien")
Bonjour Julien
>>> print(r)
None
À retenir

print affiche pour l'utilisateur ; return renvoie au programme. Sans return, une fonction renvoie None. Une fonction qui affiche $u_{10}$ ne permet pas de calculer $u_{10}+1$.

return interrompt immédiatement la fonction : ce qui le suit n'est jamais exécuté.

Partie 1 Local ou global

Portée des variables

Propriété
  • Une variable créée dans une fonction (paramètre ou affectation) est locale : elle naît à l'appel et meurt à la fin de l'appel.
  • Une variable globale peut être lue par une fonction, mais pas modifiée par une simple affectation.
def f(x) :
    y = 2*x          # y est locale a f
    return y + 1

>>> f(3)
7
>>> y
NameError: name 'y' is not defined
Partie 1 Méthode

Concevoir et tester avec assert

Quatre questions

Entrées (type, conditions), sortie (une valeur, rien d'affiché), exemples calculés à la main, cas limites compris, puis corps et tests. assert condition ne fait rien si la condition est vraie, et arrête tout avec une AssertionError sinon.

def nb_chiffres(n) :
    """Nombre de chiffres de l'entier naturel n."""
    c = 1
    while n >= 10 :
        n = n // 10
        c = c + 1
    return c

assert nb_chiffres(0) == 1
assert nb_chiffres(7) == 1
assert nb_chiffres(2026) == 4      # aucun message : tests passes

>>> assert nb_chiffres(2026) == 5
AssertionError
Partie 2 Les fonctions comme objets

Une fonction est une valeur

Propriété

Sans parenthèses, f désigne la fonction elle-même, que l'on peut passer en argument ; avec parenthèses, f(a) l'appelle. La dichotomie du chapitre Continuité résout ainsi toute équation $f(x)=0$.

import math

def f(x) :
    return x**3 + x - 1

def dicho(f, a, b, p) :
    while b-a > 10**(-p) :
        m = (a+b)/2
        if f(a)*f(m) < 0 :
            b = m
        else :
            a = m
    return b

>>> dicho(f, 0, 1, 3), dicho(math.cos, 0, 3, 6)
(0.6826171875, 1.5707967281341553)
>>> math.factorial(5), math.comb(25, 10), math.perm(5, 2)
(120, 3268760, 20)
Module math

math.comb(n, k) $=\dbinom{n}{k}$, math.perm(n, k) $=\dfrac{n!}{(n-k)!}$ ; aussi sqrt, exp, log (népérien), cos, sin (radians), pi, floor, gcd.

Partie 3 Récursivité

Une fonction qui s'appelle elle-même

Définition

Une fonction récursive comporte un ou plusieurs cas de base, traités sans appel, et un cas général qui s'appelle sur des arguments plus petits. Avec $0!=1$ et $n!=n\times(n-1)!$ :

def factorielle(n) :
    if n == 0 :
        return 1
    return n*factorielle(n-1)

appel factorielle(3)
  appel factorielle(2)
    appel factorielle(1)
      appel factorielle(0)
      factorielle(0) renvoie 1
    factorielle(1) renvoie 1
  factorielle(2) renvoie 2
factorielle(3) renvoie 6
Partie 3 ★ Le lien avec la récurrence

Valider une fonction récursive

Trois contrôles
  • Cas de base atteint et juste : c'est l'initialisation.
  • L'argument décroît strictement à chaque appel : la fonction termine.
  • La relation est celle de la définition : c'est l'hérédité (forte).
def somme(n) :
    if n == 0 :
        return 0
    return somme(n-1) + n

>>> somme(100)
5050
>>> factorielle(1000)
RecursionError: maximum recursion depth exceeded
Pile d'appels

Chaque appel non terminé occupe un étage d'une pile limitée à environ $1000$ : au-delà, RecursionError, même si la fonction est juste. Sans cas de base, même erreur.

Partie 3 Deux appels récursifs

Fibonacci : juste, mais lent

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

def fibo_boucle(n) :
    a, b = 0, 1            # F_0, F_1
    for i in range(n) :
        a, b = b, a+b
    return a

>>> [fibo(n) for n in range(12)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
>>> fibo_boucle(50)
12586269025
Calculs répétés

fibo(n) provoque $a_n=2F_{n+1}-1$ appels, nombre exponentiel en $n$ : $2\,692\,537$ appels pour fibo(30). La boucle, elle, ne fait que $n$ additions : la lenteur vient des calculs répétés, pas de la récursivité.

Partie 3 Un classique

Les tours de Hanoï

Idée

Pour déplacer $n$ disques de départ vers arrivée : les $n-1$ du dessus vers l'intermédiaire, le grand disque vers l'arrivée, puis les $n-1$ sur lui.

def hanoi(n, depart, arrivee, inter) :
    if n == 0 :
        return
    hanoi(n-1, depart, inter, arrivee)
    print(depart, "->", arrivee)
    hanoi(n-1, inter, arrivee, depart)

>>> hanoi(2, "A", "C", "B")
A -> B
A -> C
B -> C
Nombre de déplacements
$$d_0=0,\quad d_n=2d_{n-1}+1 \quad\Longrightarrow\quad d_n=2^n-1$$
Partie 4 Listes

Listes : indices et création

Définition

Les indices commencent à $0$ : le dernier élément est L[len(L)-1], ou L[-1]. La compréhension traduit $\{k^2 \mid k\in\llbracket 0,5\rrbracket\}$, avec un filtre éventuel.

>>> L = [3, 1, 4, 1, 5]
>>> len(L), L[0], L[4], L[-1], L[-2]
(5, 3, 5, 5, 1)
>>> L[5]
IndexError: list index out of range
>>> [], list(range(1, 6)), [0]*4
([], [1, 2, 3, 4, 5], [0, 0, 0, 0])
>>> [k**2 for k in range(6)]
[0, 1, 4, 9, 16, 25]
>>> [k for k in range(20) if k % 3 == 0]
[0, 3, 6, 9, 12, 15, 18]
Partie 4 Modifier une liste

Tranches, méthodes, appartenance

>>> L = [3, 1, 4, 1, 5]
>>> L[1:3], L[:2], L[2:], L[::-1]
([1, 4], [3, 1], [4, 1, 5], [5, 1, 4, 1, 3])
>>> L.append(9)
>>> L.pop(0)
3
>>> L.insert(1, 7)
>>> L[0] = 2
>>> L
[2, 7, 4, 1, 5, 9]
>>> sum(L), max(L), min(L), sorted(L)
(28, 9, 1, [1, 2, 4, 5, 7, 9])
>>> 5 in L, 8 in L
(True, False)
Sur place ou copie

L[i:j] va de $i$ à $j-1$, comme range(i, j). L.append(x) modifie L et renvoie None : L = L.append(9) détruit la liste. sorted(L) renvoie une copie triée ; L.sort() trie sur place.

Partie 4 Parcourir, tabuler

Parcours et listes de listes

M = [3, 1, 4, 1, 5, 9, 2, 6]
for i in range(len(M)) :        # par indices
    if M[i] == max(M) :
        print("maximum a l'indice", i)
s = 0
for x in M :                    # par elements
    s = s + x**2
print(s)

maximum a l'indice 5
173
Tableau

Avec T = [[1, 2, 3], [4, 5, 6]], T[i][j] est en ligne $i$, colonne $j$ : T[1][2] vaut 6. Un tableau de zéros se crée par [[0]*3 for i in range(2)].

Alias

[[0]*3]*2 répète la même ligne : après H[0][0] = 7, on lit [[7, 0, 0], [7, 0, 0]]. De même B = A ne copie pas : B = list(A) le fait.

Partie 4 Suites immuables

Chaînes de caractères et tuples

>>> mot = "python"
>>> len(mot), mot[0], mot[-1], mot[1:4], mot[::-1]
(6, 'p', 'n', 'yth', 'nohtyp')
>>> mot[0] = "P"
TypeError: 'str' object does not support item assignment
>>> str(2026)[::-1], int("2026") + 1
('6202', 2027)
>>> a, b = 1, 2
>>> a, b = b, a
>>> a, b
(2, 1)
À retenir

Une chaîne se manipule comme une liste mais est immuable ; mot == mot[::-1] teste un palindrome. Un tuple (3, 4) est immuable aussi : l'affectation multiple échange deux valeurs, et return a//b, a%b renvoie un couple que l'on récupère par q, r = division(17, 5).

Partie 5 Énumérer

Diviseurs et crible d'Ératosthène

def diviseurs(n) :
    L = []
    for k in range(1, n+1) :
        if n % k == 0 :
            L.append(k)
    return L

def crible(N) :
    premier = [True]*(N+1)
    premier[0] = False
    premier[1] = False
    for p in range(2, N+1) :
        if premier[p] :
            for m in range(2*p, N+1, p) :
                premier[m] = False
    return [p for p in range(N+1) if premier[p]]

>>> diviseurs(36)
[1, 2, 3, 4, 6, 9, 12, 18, 36]
>>> crible(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
>>> len(crible(10000))
1229
Remarque

$n\geqslant 2$ est premier si et seulement si diviseurs(n) == [1, n]. Le crible barre les multiples de chaque premier rencontré : range(2*p, N+1, p) va de $2p$ à $N$ par pas de $p$.

Partie 5 ★ Pascal en programme

Énumérer les combinaisons

Boucles imbriquées

Deux boucles sur E = [1, 2, 3, 4] et la condition i < j donnent les $\dbinom{4}{2}=6$ parties à deux éléments ; avec i != j, les $4\times 3=12$ arrangements. Mais il faut une boucle par élément choisi.

def combinaisons(L, k) :
    """Liste des parties a k elements de la liste L."""
    if k == 0 :
        return [[]]
    if len(L) < k :
        return []
    reste = L[1:]
    avec = [[L[0]] + P for P in combinaisons(reste, k-1)]
    sans = combinaisons(reste, k)
    return avec + sans

>>> combinaisons([1, 2, 3, 4], 2)
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
>>> len(combinaisons(list(range(1, 11)), 3)), math.comb(10, 3)
(120, 120)
Relation de Pascal

Une partie contient L[0] ou non : $\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}$. Cas de base : une seule partie à $0$ élément ([[]]), aucune si len(L) < k ([]).

Partie 5 Compter sans énumérer

Le triangle de Pascal

def pascal(n) :
    T = [[1]]
    for i in range(1, n+1) :
        prec = T[i-1]
        ligne = [1]
        for k in range(1, i) :
            ligne.append(prec[k-1] + prec[k])
        ligne.append(1)
        T.append(ligne)
    return T

>>> pascal(4)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
>>> pascal(25)[25][10], sum(pascal(10)[10])
(3268760, 1024)
Lecture

$\dbinom{n}{k}$ est pascal(n)[n][k], et la somme de la ligne $n$ vaut $2^n$, le nombre de parties d'un ensemble à $n$ éléments.

Compter n'est pas énumérer

Un ensemble à $25$ éléments a $2^{25}=33\,554\,432$ parties : on ne les construit pas en mémoire, on les compte par les formules, math.comb ou ce triangle.

Partie 6 Complexité

Compter les opérations

Ordre de grandeur, pour une entrée de taille $n$
  • Linéaire, de l'ordre de $n$ : une boucle de $n$ tours (somme, fibo_boucle, un parcours).
  • Quadratique, de l'ordre de $n^2$ : deux boucles imbriquées (les $\dfrac{n(n-1)}{2}$ paires $i<j$).
  • Exponentiel, de l'ordre de $c^n$ avec $c>1$ : fibo, les $2^n$ parties, hanoi.
En pratique

Quand $n$ double, un coût linéaire double et un coût quadratique est multiplié par $4$. Quand $n$ augmente de $5$, les appels de fibo sont multipliés par $\varphi^5\simeq 11{,}09$. Linéaire et quadratique traitent des milliers d'éléments ; l'exponentiel s'arrête à quelques dizaines.

Synthèse À revoir 5 min avant

Mémo express

Fonctiondef f(x) : … return ; sinon None
Testsassert f(0) == 1 : silence si juste
Récursivitécas de base + argument qui décroît strictement
Pileenviron $1000$ appels, puis RecursionError
Indicesde 0 à len(L)-1 ; L[-1] = dernier
TrancheL[i:j] : indices $i$ à $j-1$ ; L[::-1] renverse
Compréhension[k**2 for k in range(6) if k % 2 == 0]
Dénombrermath.comb(n, k), math.perm(n, k)
Vigilance Le jour J

Les pièges à éviter

Piège
  • Une fonction de calcul renvoie avec return, elle n'affiche pas avec print.
  • Une variable affectée dans une fonction est locale : compteur = compteur + 1 y provoque une UnboundLocalError.
  • Récursivité sans cas de base, ou argument qui ne décroît pas : aucune terminaison.
  • L[len(L)] n'existe pas : IndexError. Et range(1, n) s'arrête à $n-1$.
  • L = L.append(x) détruit la liste ; B = A et [[0]*3]*2 ne copient pas.
  • On ne modifie pas un caractère d'une chaîne : elle est immuable.
Auto-évaluation Cliquez pour la réponse

Quiz éclair

Q1Après def f(x) : print(x+1), qu'affiche print(f(2)) ?
3 puis None : f affiche mais ne renvoie rien.
▸ cliquer pour révéler
Q2Qu'affiche L = [3, 1, 4]; L.append(1); print(L[-1], len(L)) ?
1 4
▸ cliquer pour révéler
Q3Qu'affiche L = [1, 2, 3]; M = L; M[0] = 9; print(L) ?
[9, 2, 3] : M est un second nom de la même liste.
▸ cliquer pour révéler
Q4Qu'affiche print([k**2 for k in range(5) if k % 2 == 1]) ?
[1, 9]
▸ cliquer pour révéler
Q5Avec la fonction fibo récursive du cours, qu'affiche print(fibo(6), "abcde"[1:3]) ?
8 bc
▸ cliquer pour révéler
01 / 22

Sommaire

Chapitre 33 — Fonctions, récursivité et listes