Exercices sur la récursivité

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

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

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.

  1. Termine toujours car n est strictement décroissant et minoré par 1.
  2. 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).
  3. En fait, c’est l’écriture itérative des appels récursifs successifs (dépliés) de l’exponentiation rapide.
  4. 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.

  1. Meilleur des cas : pas d’appel récursif si n termine par un 9 (\(O(1)\)),
  2. Pire des cas : obligé de lire tout les chiffres jusqu’au dernier, donc \(O(\log_{10}(n))\).
  3. 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.