Feuille 2 : récursivité

18. Feuille 2 : récursivité#

Le symbole \(\blacksquare\) indique les exercices ou questions obligatoires. Commencez pas ceux-là.
Les symboles \(\star\) et \(\star\star\) indiquent les exercices ou questions de difficulté relative plus importante.

Focus

récursivité et notions associées : arbre et pile des appels, environnements
recherche dichotomique

Compétences

Savoir conduire une approche diviser pour régner et en déduire une solution récursive : application à des exemples calculatoires simples – comme ceux vus en cours, e.g. factorielles, exponentiation entière, exponentiation rapide.
Savoir identifier la (ou les) terminaison, la récursion et l’initialisation d’un traitement avec un algorithme récursif : application à des exemples simples – comme ceux vus en cours, e.g. factorielles, exponentiation entière, exponentiation rapide.
Savoir exprimer la complexité d’un algorithme récursif
Savoir écrire sous la forme d’une fonction de même signature les versions itérative et récursive d’un traitement calculatoire simple
Construire la pile des appels et son évolution lors d’un traitement récursif

18.1. Objectif 10#

18.1.1. \(\blacksquare\) Exercice.#

Écrire puis coder une version itérative de \(u(n)= 2^n\) pour \(n>0\)
Écrire puis coder une version récursive de ce même calcul.
Expliciter l’arbre des appels et les calculs associés lors de l’évaluation de \(u(5)\). Combien d’appels récursifs à \(u\) sont nécessaires ?
Expliciter l’évolution de la pile des appels lors de l’évaluation de \(u(5)\).
Compter le nombre d’opérations arithmétiques effectuées dans le calcul itératif de \(u(5)\).
Faire de même pour le calcul récursif.
Conclure.

18.1.2. \(\blacksquare\) Exercice.#

De façon plus générale qu’à l’exercice précédent, on calcule la valeur de \(x^n\) où \(n\) et un entier positif, et \(x\) un flottant. On rappelle que \(x^0 = 1.0\).

Rappeler et écrire les algorithmes itératif et récursif (naïf) qui calculent \(x^n\).
Expliciter l’évolution de la pile des appels lors de l’évaluation de \(x^n\) pour \(n = 8\) et \(n = 9\).
Combien de multiplications sont nécessaires à ces calculs pour \(n=2, 4, 8, 16, \dots, 2^p\) ?
Rappeler le principe de l’exponentiation entière rapide.
Ecrire les versions itératives et récursives de cet algorithme. On pourra utiliser l’opérateur python divmod.
Dans chacun des cas, combien de multiplications sont nécessaires à ce calcul pour \(n=2, 4, 8, 16, \dots, 2^p\) ? Conclure.
Compter le nombre d’appels récursifs pour les valeurs suivantes de \(n = 7, 8, 9\) et \(n = 63, 64, 65\). Conclure.
(\(\star\)) Expliciter l’évolution de la pile des appels lors de l’évaluation de \(x^n\) pour des valeurs de \(n\) que vous choisirez dans la liste précédentes comme significatives des différents cas de traitement.

18.1.3. \(\blacksquare\blacksquare\) Exercice. Si il n’y avait qu’un seul exercice à faire, c’est celui-ci !#

Donner la forme récursive qui produit le même traitement que celui d’une boucle for qui (parcourt et) affiche les indices entiers successifs de 11 à 1.
Même question pour obtenir l’affichage : 1, 2, …, 10, 11.

18.1.4. \(\blacksquare\) Exercice. (recherche dichotomique)#

Écrire un algorithme itératif qui calcule un booléen indiquant si un tableau d’entiers donné trié par ordre croissant contient une valeur donnée. La recherche sera effectuée par dichotomie.
Écrire une fonction récursive trouve (c’est-à-dire son en-tête, puis l’appel puis le corps) qui retourne le booléen précédent en appliquant aussi une recherche par dichotomie.

18.1.5. \(\blacksquare\) Exercice. (recherche dichotomique)#

Dérouler l’algorithme de recherche dichotomique (version itérative) pour rechercher la valeur 3 dans le tableau [0,1,2,3,4,5,6,7,8,9].
Donner une valeur à rechercher qui minimise le nombre d’itérations de la recherche.
Même question pour celle qui maximise ce nombre.
Coder ces traitements et vérifier votre analyse.
Reprendre les questions précédentes sur une version récursive de cette recherche en complétant avec l’évolution de la pile des appels de ce traitement (rechercher la valeur 3 dans le tableau indiqué).

18.1.6. Exercice. (palindrome … encore)#

Dans l’exercice de la feuille 1, on a défini et donné un algorithme itératif qui vérifie si un mot est ou non un palindrome.

Donner une version récursive de cette vérification.
Vérifier sa correction avec les tests unitaires de la version itérative.
Expliciter l’évolution de la pile des appels des vérifications de “kayak” et de “mamama”.

18.1.7. Exercice. (produit scalaire … encore)#

Dans l’exercice de la feuille 1, on a écrit un algorithme itératif qui calcule le produit scalaire de deux vecteurs de taille \(n\).

Donner une version récursive de ce calcul.

Comme dans la feuille 1, appliquer cette version récursive pour vérifier si deux vecteurs donnés sont ou non orthogonaux.

18.2. Objectif 20#

18.2.1. Exercice.#

Ecrire une fonction récursive nbChiffresDec(n: int) -> int qui calcule et retourne le nombre de chiffres de l’écriture décimale de l’entier \(n \ge 0\).

Par exemple, nbChiffresDec(12345) == 5.

18.2.2. Exercice. (Info).#

Ecrire une fonction récursive nbBits(n: int) -> int qui calcule et retourne le nombre de bits valant 1 dans l’écriture binaire de l’entier \(n \ge 0\). L’entier \(n\) est donné en décimales.

Par exemple, nbChiffresDec(255) == 8.

18.2.3. (\(\star\)) Exercice. (Maths)#

Dans l’exercice de la feuille 1, on a défini et donné une version itérative du calcul du pgcd de deux entiers par l’algorithme d’Euclide.

En écrire une version récursive.
Application. Ecrire une fonction qui prend en entrée 2 entiers \(a\) et \(b\), calcule et retourne les entiers \(c\) et \(d\) tels que \(\frac{c}{d}\) soit la forme irréductible de \(\frac{a}{b}\).

18.2.4. (\(\star\)) Exercice. (suite de Syracuse)#

La suite de Syracuse \(s\) d’un nombre \(N\) donné est définie de façon récursive comme suit.

On commence avec \(s(0) = N\), puis :

\(s(n+1) = s(n)/2\), si \(s(n)\) est pair,
\(s(n+1) = 3s(n)+1\), si \(s(n)\) est impair.

Ainsi définie, \(s\) est une suite infinie de valeurs entières construites à partir de la valeur de départ \(N\).

A la main pour commencer.
1. Calculer à la main les valeurs de la suite pour les valeurs de départ \(N = 4, 2, 1\). Qu’en déduire ?
2. Calculer à la main les valeurs de la suite pour les valeurs de départ \(N = 3, 5, 6, 7, 8, 16, 32\). Il peut être utile de représenter les valeurs obtenues sous la forme d’un tableau où chaque colonne (ou ligne) à la forme \(N u_1 u_2 \dots u_n \dots\) où les \(u_i\) sont les valeurs de la suite pour la valeur de départ \(N\). Qu’en déduire et en particulier que penser de la terminaison de cette suite ?
La coder de façon récursive et observer son comportement pour l’une de ces valeurs de \(N\). Attention !!!
Terminaison : on arrête la suite \(s(n)\) quand on rencontre \(s(n) = 1\). D’après la conjecture de Collatz, cette valeur est rencontrée quelque soit le terme de départ \(N\).
1. Compléter votre code précédent avec cette condition d’arrêt.
2. Compléter votre code précédent avec l’affichage de chaque valeur calculée avant la terminaison.
Écrire des fonctions qui calculent les notions suivantes (source Wikipédia) :
1. le temps de vol qui est le plus petit indice \(n\) tel que \(s(n) = 1\), i.e. jusqu’à la terminaison.
2. le temps de vol en altitude qui est le plus petit indice \(n\) tel que \(s(n) \le N\).
3. l’altitude maximale qui est la valeur maximale \(s(n)\) de la suite.
Coder ces fonctions et proposer des graphiques instructifs.
Coder le calcul avec terminaison de façon itérative.

18.2.5. (\(\star\)) Exercice. (récursivité terminale)#

Une fonction récursive est dite récursive terminale lorsque l’appel récursif est la dernière instruction exécutée.

Donner la liste de telles fonctions récursives terminales qui apparaissent dans les exemples du chapitre. Justifier votre réponse.
Donner une version récursive terminale du calcul de \(n!\). Vous pouvez modifier la signature vue en cours pour cette fonction.
Déduire une version récursive terminale du calcul de \(n!\) de même signature que la fonction vue en cours.

18.2.6. (\(\star\)) Exercice. (addition de 2 entiers)#

On souhaite additionner deux entiers de \(p\) chiffres décimaux. On dispose pour cela d’une fonction add(c1,c2) qui calcule et retourne un couple (r,s) où :

c1, c2, s sont des entiers compris entre 0 et 9,
r est égal à 0 ou à 1, et
c1 + c2 = 10 r + c.

Ainsi r est la retenue de l’addition des chiffres c1 et c2 et s est la valeur “des unités” de cette somme. Par exemple : add(2,3) retourne (0,5) et add(8,5) retourne (1,3).

On représente un entier \(n\) à \(p\) chiffres décimaux par un tableau \(N\) de longueur \(p\). On peut choisir par exemple \(n = \sum_{i=0}^{p-1} N[i]\cdot 10^i\). Dit plus simplement dans ce cas, le dernier chiffre de \(n\) (celui des unités) est stocké en position 0 dans le tableau \(N\), l’avant-dernier (celui des dizaines) en position 1, … — et on notera qu’il est ainsi plaisant que les tableaux soient indicés à partir de 0. Il est aussi possible de choisir une écriture plus classique où les chiffres sont stockés dans l’ordre des puissances décroissantes (numération de position habituelle).

Coder la fonction add et la vérifier avec des tests unitaires bine choisis.
Utiliser la fonction add pour écrire un algorithme qui calcule la somme de deux entiers \(n1\) et \(n2\) respectivement représentés par les tableaux \(N1\) et \(N2\). Le résultat \(s = n1+n2\) sera aussi représenté par un tableau adapté.
Soient \(n1 = 1234\), \(n2=4567\) et \(n3=9876\). Dérouler l’algorithme pour les deux calculs \(n1+n2\) et \(n1+n3\).
Coder et valider ces fonctions.