Exercices sur la récursivité ¶

4ème TD, sur la récursivité.

TD4 au Lycée Lakanal (sujet rédigé par Arnaud Basson).

Date : jeudi 12 novembre 2015,
Auteur : Lilian Besson, pour le cours d’informatique pour tous en prépa MP (http://perso.crans.org/besson/infoMP/),
Licence : MIT Licence (http://lbesson.mit-license.org).

exos_rec.moyArithGeom(a, b, n)[source]¶: Calcule les énièmes termes des deux suites adjacentes \(u_n, v_n\), définies selon :

\[u_0 = a,\;\; v_0 = b\]

\[u_{n+1}=\frac{u_n+v_n}{2}, v_{n+1}=\sqrt{u_n v_n}\]

exos_rec.pgcdRec(a, b)[source]¶

Calcule le PGCD de a et b récursivement.

Note : elle a un temps logarithmique mais une pile d’appels logarithmique aussi (la version itérative est meilleure, car sans pile d’appel).
Complexité temporelle en \(O(\log(\min(a,b)))\).
Voir dans le TP4 pour plus d’exemples de fonctions récursives.

exos_rec.pgcdBinaire(a, b)[source]¶

Autre algorithme de calcul du PGCD de a et b, plus lent.

Termine bien en considérant l’ordre lexicographique sur le nombre de bits de a et de b.
Complexité temporelle en \(O(\log(a) + \log(b))\).
Complexité mémoire en \(O(1)\).

exos_rec.f(x, n)[source]¶

“Fonction mystère” de l’exercise 3.

Termine toujours car n est strictement décroissant et minoré par 1.
Ohoh, apparemment \(f(x,n) = x^n\) (mais avec la convention \(x^0 = x\) et pas 1). Invariant : x**(n-i) == a à chaque boucle (vrai au début i = n, a = 1, reste vrai en considérant les deux cas sur le bit suivant de n, et à la fin ça donne x**(n-1) == a donc x**n == a*x = f(x,n) prouve la correction).
En fait, c’est l’écriture itérative des appels récursifs successifs (dépliés) de l’exponentiation rapide.
Le nombre de multiplication concernant a est le nombre de bit à 1 dans n et le nombre d’exponentiation concernant x est exactement le nombre de bit de n, donc le tout est bien en \(O(\log(n))\).

exos_rec.sommeChiffres(n)[source]¶: Calcule récursivement la somme des chiffres d’un entier n.

exos_rec.contient9(n)[source]¶

Teste si l’écriture décimale de n contient un n.

Meilleur des cas : pas d’appel récursif si n termine par un 9 (\(O(1)\)),
Pire des cas : obligé de lire tout les chiffres jusqu’au dernier, donc \(O(\log_{10}(n))\).
En moyenne : C est comme une loi géométrique tronquée, de paramètre \(p = 1/10\) (chaque chiffre est uniformément réparti) : on pioche un chiffre, on s’arrête si = 9, on continue sinon. Le paramètre k est la taille (décimale) du nombre entier n. (TODO better explanations !)

Sortie du script¶

$ python3 exos_rec.py


Exercice 1 : Moyenne arithmetico-geometrique
Exemples de moyenne arithmetico-geometrique :

Pour a = 10 et b = 500
	Pour n = 0 u_n = 10 et v_n = 500
	Pour n = 1 u_n = 255.0 et v_n = 70.71067811865476
	Pour n = 2 u_n = 162.85533905932738 et v_n = 134.28038918716672
	Pour n = 3 u_n = 148.56786412324703 et v_n = 147.87926937233112
	Pour n = 4 u_n = 148.22356674778908 et v_n = 148.22316687601008
	Pour n = 5 u_n = 148.22336681189958 et v_n = 148.22336681176472
	Pour n = 6 u_n = 148.22336681183214 et v_n = 148.22336681183216
	Pour n = 7 u_n = 148.22336681183214 et v_n = 148.22336681183216
	Pour n = 8 u_n = 148.22336681183214 et v_n = 148.22336681183216
	Pour n = 9 u_n = 148.22336681183214 et v_n = 148.22336681183216
	Pour n = 10 u_n = 148.22336681183214 et v_n = 148.22336681183216
	Pour n = 11 u_n = 148.22336681183214 et v_n = 148.22336681183216

Pour a = 2 et b = 6000
	Pour n = 0 u_n = 2 et v_n = 6000
	Pour n = 1 u_n = 3001.0 et v_n = 109.54451150103323
	Pour n = 2 u_n = 1555.2722557505167 et v_n = 573.361211641144
	Pour n = 3 u_n = 1064.3167336958304 et v_n = 944.316040840656
	Pour n = 4 u_n = 1004.3163872682433 et v_n = 1002.522500577471
	Pour n = 5 u_n = 1003.4194439228571 et v_n = 1003.4190430398912
	Pour n = 6 u_n = 1003.4192434813742 et v_n = 1003.4192434813542
	Pour n = 7 u_n = 1003.4192434813642 et v_n = 1003.4192434813642
	La suite a converge !
	Pour n = 8 u_n = 1003.4192434813642 et v_n = 1003.4192434813642
	La suite a converge !
	Pour n = 9 u_n = 1003.4192434813642 et v_n = 1003.4192434813642
	La suite a converge !
	Pour n = 10 u_n = 1003.4192434813642 et v_n = 1003.4192434813642
	La suite a converge !
	Pour n = 11 u_n = 1003.4192434813642 et v_n = 1003.4192434813642
	La suite a converge !

Pour a = 19 et b = 93
	Pour n = 0 u_n = 19 et v_n = 93
	Pour n = 1 u_n = 56.0 et v_n = 42.035699113967404
	Pour n = 2 u_n = 49.017849556983705 et v_n = 48.518029127141745
	Pour n = 3 u_n = 48.767939342062725 et v_n = 48.767299008204134
	Pour n = 4 u_n = 48.76761917513343 et v_n = 48.76761917408246
	Pour n = 5 u_n = 48.767619174607944 et v_n = 48.767619174607944
	La suite a converge !
	Pour n = 6 u_n = 48.767619174607944 et v_n = 48.767619174607944
	La suite a converge !
	Pour n = 7 u_n = 48.767619174607944 et v_n = 48.767619174607944
	La suite a converge !
	Pour n = 8 u_n = 48.767619174607944 et v_n = 48.767619174607944
	La suite a converge !
	Pour n = 9 u_n = 48.767619174607944 et v_n = 48.767619174607944
	La suite a converge !
	Pour n = 10 u_n = 48.767619174607944 et v_n = 48.767619174607944
	La suite a converge !
	Pour n = 11 u_n = 48.767619174607944 et v_n = 48.767619174607944
	La suite a converge !
Exercice 2 : Calcul recursif du pgcd

Quelques essais de pgcdRec(a, b) :
pgcdRec de 10 et 0 = 10
pgcdRec de 10 et 1 = 1
pgcdRec de 10 et 2 = 2
pgcdRec de 10 et 5 = 5
pgcdRec de 10 et 10 = 10
pgcdRec de 10 et 37 = 1
pgcdRec de 10 et 69 = 1
pgcdRec de 10 et 117 = 1
pgcdRec de 10 et 673 = 1
pgcdRec de 10 et 7894651 = 1
pgcdRec de 10 et 74147894651 = 1
pgcdRec de 20 et 0 = 20
pgcdRec de 20 et 1 = 1
pgcdRec de 20 et 2 = 2
pgcdRec de 20 et 5 = 5
pgcdRec de 20 et 10 = 10
pgcdRec de 20 et 37 = 1
pgcdRec de 20 et 69 = 1
pgcdRec de 20 et 117 = 1
pgcdRec de 20 et 673 = 1
pgcdRec de 20 et 7894651 = 1
pgcdRec de 20 et 74147894651 = 1
pgcdRec de 30 et 0 = 30
pgcdRec de 30 et 1 = 1
pgcdRec de 30 et 2 = 2
pgcdRec de 30 et 5 = 5
pgcdRec de 30 et 10 = 10
pgcdRec de 30 et 37 = 1
pgcdRec de 30 et 69 = 3
pgcdRec de 30 et 117 = 3
pgcdRec de 30 et 673 = 1
pgcdRec de 30 et 7894651 = 1
pgcdRec de 30 et 74147894651 = 1
pgcdRec de 200 et 0 = 200
pgcdRec de 200 et 1 = 1
pgcdRec de 200 et 2 = 2
pgcdRec de 200 et 5 = 5
pgcdRec de 200 et 10 = 10
pgcdRec de 200 et 37 = 1
pgcdRec de 200 et 69 = 1
pgcdRec de 200 et 117 = 1
pgcdRec de 200 et 673 = 1
pgcdRec de 200 et 7894651 = 1
pgcdRec de 200 et 74147894651 = 1
pgcdRec de 400 et 0 = 400
pgcdRec de 400 et 1 = 1
pgcdRec de 400 et 2 = 2
pgcdRec de 400 et 5 = 5
pgcdRec de 400 et 10 = 10
pgcdRec de 400 et 37 = 1
pgcdRec de 400 et 69 = 1
pgcdRec de 400 et 117 = 1
pgcdRec de 400 et 673 = 1
pgcdRec de 400 et 7894651 = 1
pgcdRec de 400 et 74147894651 = 1
pgcdRec de 10000 et 0 = 10000
pgcdRec de 10000 et 1 = 1
pgcdRec de 10000 et 2 = 2
pgcdRec de 10000 et 5 = 5
pgcdRec de 10000 et 10 = 10
pgcdRec de 10000 et 37 = 1
pgcdRec de 10000 et 69 = 1
pgcdRec de 10000 et 117 = 1
pgcdRec de 10000 et 673 = 1
pgcdRec de 10000 et 7894651 = 1
pgcdRec de 10000 et 74147894651 = 1
pgcdRec de 94749651 et 0 = 94749651
pgcdRec de 94749651 et 1 = 1
pgcdRec de 94749651 et 2 = 1
pgcdRec de 94749651 et 5 = 1
pgcdRec de 94749651 et 10 = 1
pgcdRec de 94749651 et 37 = 1
pgcdRec de 94749651 et 69 = 3
pgcdRec de 94749651 et 117 = 9
pgcdRec de 94749651 et 673 = 673
pgcdRec de 94749651 et 7894651 = 1
pgcdRec de 94749651 et 74147894651 = 1
pgcdRec de 789465179864519465 et 0 = 789465179864519465
pgcdRec de 789465179864519465 et 1 = 1
pgcdRec de 789465179864519465 et 2 = 1
pgcdRec de 789465179864519465 et 5 = 5
pgcdRec de 789465179864519465 et 10 = 5
pgcdRec de 789465179864519465 et 37 = 1
pgcdRec de 789465179864519465 et 69 = 1
pgcdRec de 789465179864519465 et 117 = 1
pgcdRec de 789465179864519465 et 673 = 1
pgcdRec de 789465179864519465 et 7894651 = 1
pgcdRec de 789465179864519465 et 74147894651 = 1

Quelques essais de pgcdBinaire(a, b) :
pgcdBinaire de 10 et 0 = 10
pgcdBinaire de 10 et 1 = 1
pgcdBinaire de 10 et 2 = 2
pgcdBinaire de 10 et 5 = 5
pgcdBinaire de 10 et 10 = 10
pgcdBinaire de 10 et 37 = 1
pgcdBinaire de 10 et 69 = 1
pgcdBinaire de 10 et 117 = 1
pgcdBinaire de 10 et 673 = 1
pgcdBinaire de 10 et 7894651 = 1
pgcdBinaire de 10 et 74147894651 = 1
pgcdBinaire de 20 et 0 = 20
pgcdBinaire de 20 et 1 = 1
pgcdBinaire de 20 et 2 = 2
pgcdBinaire de 20 et 5 = 5
pgcdBinaire de 20 et 10 = 10
pgcdBinaire de 20 et 37 = 1
pgcdBinaire de 20 et 69 = 1
pgcdBinaire de 20 et 117 = 1
pgcdBinaire de 20 et 673 = 1
pgcdBinaire de 20 et 7894651 = 1
pgcdBinaire de 20 et 74147894651 = 1
pgcdBinaire de 30 et 0 = 30
pgcdBinaire de 30 et 1 = 1
pgcdBinaire de 30 et 2 = 2
pgcdBinaire de 30 et 5 = 5
pgcdBinaire de 30 et 10 = 10
pgcdBinaire de 30 et 37 = 1
pgcdBinaire de 30 et 69 = 3
pgcdBinaire de 30 et 117 = 3
pgcdBinaire de 30 et 673 = 1
pgcdBinaire de 30 et 7894651 = 1
pgcdBinaire de 30 et 74147894651 = 1
pgcdBinaire de 200 et 0 = 200
pgcdBinaire de 200 et 1 = 1
pgcdBinaire de 200 et 2 = 2
pgcdBinaire de 200 et 5 = 5
pgcdBinaire de 200 et 10 = 10
pgcdBinaire de 200 et 37 = 1
pgcdBinaire de 200 et 69 = 1
pgcdBinaire de 200 et 117 = 1
pgcdBinaire de 200 et 673 = 1
pgcdBinaire de 200 et 7894651 = 1
pgcdBinaire de 200 et 74147894651 = 1
pgcdBinaire de 400 et 0 = 400
pgcdBinaire de 400 et 1 = 1
pgcdBinaire de 400 et 2 = 2
pgcdBinaire de 400 et 5 = 5
pgcdBinaire de 400 et 10 = 10
pgcdBinaire de 400 et 37 = 1
pgcdBinaire de 400 et 69 = 1
pgcdBinaire de 400 et 117 = 1
pgcdBinaire de 400 et 673 = 1
pgcdBinaire de 400 et 7894651 = 1
pgcdBinaire de 400 et 74147894651 = 1
pgcdBinaire de 10000 et 0 = 10000
pgcdBinaire de 10000 et 1 = 1
pgcdBinaire de 10000 et 2 = 2
pgcdBinaire de 10000 et 5 = 5
pgcdBinaire de 10000 et 10 = 10
pgcdBinaire de 10000 et 37 = 1
pgcdBinaire de 10000 et 69 = 1
pgcdBinaire de 10000 et 117 = 1
pgcdBinaire de 10000 et 673 = 1
pgcdBinaire de 10000 et 7894651 = 1
pgcdBinaire de 10000 et 74147894651 = 1
pgcdBinaire de 94749651 et 0 = 94749651
pgcdBinaire de 94749651 et 1 = 1
pgcdBinaire de 94749651 et 2 = 1
pgcdBinaire de 94749651 et 5 = 1
pgcdBinaire de 94749651 et 10 = 1
pgcdBinaire de 94749651 et 37 = 1
pgcdBinaire de 94749651 et 69 = 3
pgcdBinaire de 94749651 et 117 = 9
pgcdBinaire de 94749651 et 673 = 673
pgcdBinaire de 94749651 et 7894651 = 1
pgcdBinaire de 94749651 et 74147894651 = 1
pgcdBinaire de 789465179864519465 et 0 = 789465179864519465
pgcdBinaire de 789465179864519465 et 1 = 1
pgcdBinaire de 789465179864519465 et 2 = 1
pgcdBinaire de 789465179864519465 et 5 = 5
pgcdBinaire de 789465179864519465 et 10 = 5
pgcdBinaire de 789465179864519465 et 37 = 1
pgcdBinaire de 789465179864519465 et 69 = 1
pgcdBinaire de 789465179864519465 et 117 = 1
pgcdBinaire de 789465179864519465 et 673 = 1
pgcdBinaire de 789465179864519465 et 7894651 = 1
pgcdBinaire de 789465179864519465 et 74147894651 = 1
Exercice 3 : fonction mystere
Testons cette fonction mystère sur quelques valeurs :
Pour x = 0
	Pour n = 1
	f(x, n) = 0
	Pour n = 2
	f(x, n) = 0
	Pour n = 3
	f(x, n) = 0
	Pour n = 4
	f(x, n) = 0
	Pour n = 5
	f(x, n) = 0
	Pour n = 100
	f(x, n) = 0
Pour x = 1
	Pour n = 1
	f(x, n) = 1
	Pour n = 2
	f(x, n) = 1
	Pour n = 3
	f(x, n) = 1
	Pour n = 4
	f(x, n) = 1
	Pour n = 5
	f(x, n) = 1
	Pour n = 100
	f(x, n) = 1
Pour x = 2
	Pour n = 1
	f(x, n) = 2
	Pour n = 2
	f(x, n) = 4
	Pour n = 3
	f(x, n) = 8
	Pour n = 4
	f(x, n) = 16
	Pour n = 5
	f(x, n) = 32
	Pour n = 100
	f(x, n) = 1267650600228229401496703205376
Pour x = 3
	Pour n = 1
	f(x, n) = 3
	Pour n = 2
	f(x, n) = 9
	Pour n = 3
	f(x, n) = 27
	Pour n = 4
	f(x, n) = 81
	Pour n = 5
	f(x, n) = 243
	Pour n = 100
	f(x, n) = 515377520732011331036461129765621272702107522001
Pour x = 10
	Pour n = 1
	f(x, n) = 10
	Pour n = 2
	f(x, n) = 100
	Pour n = 3
	f(x, n) = 1000
	Pour n = 4
	f(x, n) = 10000
	Pour n = 5
	f(x, n) = 100000
	Pour n = 100
	f(x, n) = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Pour x = -1
	Pour n = 1
	f(x, n) = -1
	Pour n = 2
	f(x, n) = 1
	Pour n = 3
	f(x, n) = -1
	Pour n = 4
	f(x, n) = 1
	Pour n = 5
	f(x, n) = -1
	Pour n = 100
	f(x, n) = 1
Pour x = -2
	Pour n = 1
	f(x, n) = -2
	Pour n = 2
	f(x, n) = 4
	Pour n = 3
	f(x, n) = -8
	Pour n = 4
	f(x, n) = 16
	Pour n = 5
	f(x, n) = -32
	Pour n = 100
	f(x, n) = 1267650600228229401496703205376
Exercice 4 : Manipulation recursive de l'ecriture decimale d'un entier
Exemple de somme des chiffres d'un entier :
Pour n = 7 on a sommeChiffres(n) = 7
Pour n = 1658 on a sommeChiffres(n) = 20
Pour n = 749861 on a sommeChiffres(n) = 35
Pour n = 7948978546 on a sommeChiffres(n) = 67
Pour n = 79849788974659786547894 on a sommeChiffres(n) = 158
Pour n = 100000000000000000000000 on a sommeChiffres(n) = 1
Pour n = 10000000000000000000000000000001 on a sommeChiffres(n) = 2
Exemple de chiffres qui contiennent ou ne contiennent pas 9 :
Pour n = 7 on a contient9(n) = False
Pour n = 1658 on a contient9(n) = False
Pour n = 749861 on a contient9(n) = True
Pour n = 7948978546 on a contient9(n) = True
Pour n = 79849788974659786547894 on a contient9(n) = True
Pour n = 100000000000000000000000 on a contient9(n) = False
Pour n = 10000000000009000000000000000001 on a contient9(n) = True

Le fichier Python se trouve ici : exos_rec.py.

Exercices sur la récursivité¶

Sortie du script¶

Exercices sur la récursivité ¶