T.D.

3 

Itératif / Récursif

Pour la plupart des programmes suivants, on s'attachera à évaluer leur complexité ainsi qu'à prouver
leur bon fonctionnement.

I - Boucles for
Exercice 1. (-) Donner le contenu de la liste L à l'issue des lignes de commandes suivantes.

L = []
n = 3
for i in range(-1, n):
if i != 0:
L.append(i)

for i in range(1, 13, 2*n):

for i in range(1, n+1):

for i in range(1, 13, 2*n):

Exercice 2. (-) Quel est le résultat renvoyé par la fonction suivante ?

def f(n) :
u = 1
for x in range(1,n) :
u = u * x
return u

Exercice 3. (-) On suppose que les listes manipulées dans cet exercice sont des listes de nombres.
1. Écrire une fonction somme(liste) qui retourne la somme des éléments de liste.
2. Écrire une fonction moyenne(liste) qui retourne la moyenne des éléments de liste.
3. Écrire une fonction carre(liste) qui retourne la liste des éléments de liste élevés au carré.
4. Écrire une fonction pair(liste) qui retourne la liste des éléments pairs de liste.
Exercice 4. (♥) Écrire une fonction max1(L) (resp. min1(L)) qui, étant donnée une liste L de nombres,
retourne le plus grand (resp. plus petit) élément de L.
Exercice 5. Écrire une fonction en_commun(l1,l2) qui renvoie la liste des éléments de la liste l1 qui se
retrouvent dans l2.
Exercice 6. (♥) Écrire une fonction occurences(mot,lettre) qui retrourne le nombre d'occurences de
l'entier lettre dans la liste d'entiers mot.
Chapitre 10. Itératif / Récursif MPSI 1

Exercice 7. (♥) Écrire une fonction suite_ab(n) qui, pour tout entier naturel n, renvoie une valeur
approchée du n-ième élément de la suite dénie par un = abnn , où


 a0 = 3
b0 = 2


 an+1 = an + 2bn
bn+1 = a n + bn


Calculer le 10-ième puis le 100-ième élément de cette suite. Que conjecturez-vous ?

II - Boucles while
Exercice 8. (-) Écrire une fonction seuil_som_car(M) qui, pour tout entier M, renvoie le plus petit entier
n tel que 12 + 22 + · · · + n2 ≥ M.
Exercice 9. (-)
1. Écrire une fonction fact(n) qui étant donné un entier n renvoie n !.
2. En déduire une fonction est_fact(n) qui détermine si un entier n s'écrit sous la forme n = k!, où k
est un entier naturel.
Exercice 10. (♥)
1. Écrire, à la main, une fonction inverse(mot) qui reçoit une liste, la recopie en inversant l'ordre des
éléments et renvoie le résultat.
2. En déduire une fonction booléenne palindrome(mot) qui teste si une liste est un palindrome.
3. Écrire une fonction palindrome_rapide(mot) qui parcourt le mot au plus une fois pour tester si mot
est un palindrome.
Exercice 11. (♥) Écrire une fonction trouve(mot, lettre) qui renvoie l'indice de la première occurence
de lettre dans la liste mot et renvoie False si lettre n'apparaît pas dans mot.
Exercice 12. ( !) Écrire une fonction zero(liste) qui reçoit une liste, la recopie en insérant des 0 entre
les éléments, et renvoie le résultat. Par exemple, zero([1,2,3]) devra renvoyer [1,0,2,0,3].
Exercice 13. (Syracuse, ♥) La suite de Syracuse est dénie par u0 ∈ N? et par la relation de récurrence :

si un = 1

 1
un+1 = un
2 si un est pair

3un + 1 sinon

Écrire une fonction syr2(u0) prenant pour argument u0 et renvoyant le nombre minimum d'itérations
nécessaires pour aboutir à 1.
On ne sait pas à ce jour s'il existe un réel u0 pour lequel cette suite n'atteint jamais 1. On ne cherchera pas à
prouver que ce programme termine. . .

III - Récursivité
Exercice 14. (-) Écrire une fonction récursive fibo_rec(n) qui prend en entrée un entier n et retourne
le terme de rang n de la suite de Fibonacci.
Exercice 15. (-) Écrire une fonction récursive palindrome_rec(mot) qui prend comme argument une
liste mot et retourne True si cette liste est un palindrome, False sinon.
Exercice 16. (Exponentiation rapide,♥) Étant donnés un réel positif a et un entier n, remarquer que

 a n2 2 si n est pair,


n
a =  n−1 2
 a· a 2 si n est impair.

Écrire une fonction récursive puissance_rapide(a,n) qui utilise cette remarque pour calculer an . Évaluer
la complexité de cet algorithme.

L •ycée Sˆta’nˆiŒs„laŒš 24 A. C€a’m€a’n€eš