Exercices récursivité

Lang 08

Exercices

Exercice 1 *

La somme des entiers s’écrit: $$0+1+2+…+n$$

  1. Écrire la fonction itérative somme(n: int) $\rightarrow$ int qui calcule la somme des entiers de 0 à n.
  2. Estimer la complexité de cette fonction.
  3. Donner une définition récursive de la somme des entiers.
  4. Écrire la fonction récursive somme_rec(n: int) $\rightarrow$ int qui implémente la définition précédente.
  5. Estimer la complexité de cette fonction.

Il existe une formule mathématique permettant de calculer la somme des n entiers: $$\sum_{k=0}^{n}{k} = \frac{n\times(n+1)}{2}$$

  1. Écrire la fonction somme_rapide(n: int) $\rightarrow$ int qui implémente cette formule.
  2. Estimer sa complexité.

Exercice 2 *

La fonction factorielle est définie par: $$n!=1\times2\times3…\times n \qquad si\qquad n>0 \qquad et \qquad 0!=1$$

  1. Écrire la fonction itérative factorielle(n: int) $\rightarrow$ int qui calcule n!.
  2. Estimer la complexité de cette fonction.
  3. Donner une définition récursive qui correspond au calcul de la fonction factorielle.
  4. Écrire la fonction récursive factorielle_rec(n: int) $\rightarrow$ int qui implémente cette fonction.
  5. Estimer la complexité de cette fonction.

Exercice 3 *

  1. Écrire une fonction récursive entiers(i: int, k: int) $\rightarrow$ None qui affiche les entiers entre i et k. Par exemple, entiers(0,3) doit afficher 0 1 2 3.
  2. Écrire une fonction récursive impairs(i: int, k: int) $\rightarrow$ None qui affiche les nombres impairs entre i et k.

Exercice 4 **

Soit $u_n$ la suite d’entiers définie par $u_0>1$ et:

$$ u_{n+1} = \left\lbrace \begin{array}{cc} u_n/2 & si~u_n ~est~ pair \\ 3\times u_n+1 & ~sinon \end{array} \right. $$

  1. Écrire la fonction syracuse(u: int) $\rightarrow$ None qui affiche les valeurs successives de la suite $u_n$ tant que $u_n>1$. L’appel de la fonction s’effectuera avec une valeur de $u_0$ quelconque.
  2. Proposer une version syracuse2(u: int, l: list) $\rightarrow$ None qui stocke les valeurs successives dans un tableau.

Exercice 5 **

Soit $u_n$ la suite d’entiers définie par: $$ u_{n} = \left\lbrace \begin{array}{ll} 0 & si~n=0\\ 1 & si~n=1\\ 3\times u_{n-1}+2\times u_{n-2}+5 & \forall n\geq2 \end{array} \right. $$ Écrire la fonction récursive suite(n: int) $\rightarrow$ int qui renvoie le n-ième terme de la suite.

Exercice 6 **

  1. Construire par compréhension un tableau de 10 entiers aléatoires compris entre 1 et 100.
  2. Écrire la fonction itérative somme(tab: list) $\rightarrow$ int qui renvoie la somme des entiers de tab.
  3. Écrire la fonction récursive somme_rec équivalente. Le nombre de paramètres pourra évoluer par rapport à la fonction précédente.

Exercice 7 **

  1. Construire par compréhension un tableau de 30 entiers aléatoires compris entre 1 et 1000.
  2. Écrire la fonction itérative mini(tab: list) $\rightarrow$ int qui renvoie le minimum de tab.
  3. Écrire la fonction récursive mini_rec équivalente. Le nombre de paramètres pourra évoluer par rapport à la fonction précédente.

Exercice 8 **

Pour compter le nombre de chiffres d’un nombre, il suffit de diviser ce nombre par 10, jusqu’à ce que la partie entière de la valeur obtenue soit strictement inférieure à 10. Écrire la fonction récursive nombre_chiffres(n: int) $\rightarrow$ int qui renvoie le nombre de chiffres qui composent n.

Exercice 9 **

Écrire la fonction récursive somme_chiffres(n: int) $\rightarrow$ int qui ajoute tous les chiffres du nombre n.

Exercice 10 ***

Un nombre descriptif décrit la quantité de chaque chiffre du nombre. Par exemple:

  • nombre: 1124
  • nombre descriptif: 0 2 1 0 1 0 Dans 1124, il y a 0 zéros, 2 uns, 1 deux …

Dans l’exercice, le nombre descriptif sera représenté sous forme d’un tableau de 10 cellules. Ainsi le nombre descriptif de 1124 sera:

[0, 2, 1, 0, 1, 0, 0, 0, 0, 0]
  1. Créer, par compréhension, le tableau chiffres qui contient 10 zéros.
  2. Écrire la fonction récursive compter_chiffres(nb: int, chiffres: list) $\rightarrow$ None qui compte chaque chiffre de nb et modifie le tableau chiffres en conséquence.

Remarque: Un nombre descriptif est autodescriptif si sa représentation est identique au nombre décrit. Par exemple, 2020 est un nombre autodescriptif car il contient:

  • 2 zéros
  • 0 un
  • 2 deux
  • 0 trois

Exercice 11 ***

Le paradoxe de Zénon: Zénon (environ 490–430 av. J-C.) se tient à huit mètres d’un arbre, tenant une pierre. Il lance sa pierre dans la direction de l’arbre. Avant que le caillou puisse atteindre l’arbre, il doit traverser la première moitié des huit mètres. Il faut un certain temps, non nul, à cette pierre pour se déplacer sur cette distance. Ensuite, il lui reste encore quatre mètres à parcourir, dont elle accomplit d’abord la moitié, deux mètres, ce qui lui prend un certain temps. Puis la pierre avance d’un mètre de plus, progresse après d’un demi-mètre et encore d’un quart, et ainsi de suite, jusqu’à l’infini, et à chaque fois avec un temps non nul. Zénon en conclut que la pierre ne pourra pas frapper l’arbre, puisqu’il faudrait pour cela que soit franchie effectivement une série infinie d’étapes, ce qui est impossible. Pourtant, l’expérience le prouve aisément : il n’y a guère de difficulté à faire en sorte qu’une pierre heurte un arbre situé à 8 m de distance ! D’où le paradoxe…

Cette situation peut se modéliser à l’aide d’une suite définie par récurrence: $$d_1=4 ~et~ d_{n+1}=d_n + \frac{4}{2^n}$$

  1. Écrire la fonction zenon(d: int, n: int, n_max: int) $\rightarrow$ float qui renvoie la valeur de $d_n$. On pourra vérifier que:
>>> zenon(4, 1, 2)
6.0
>>> zenon(4, 1, 20)
7.999992370605469
  1. Une autre écriture possible de la suite récursive est: $$d_{n+1}= \frac{1}{2}\times d_n+4$$ Écrire la fonction zenon2(d: int, n: int) $\rightarrow$ float qui renvoie la valeur de $d_n$.

Exercice 12 ***

La méthode de Heron (ou méthode babylonienne) est une méthode efficace d’extraction de racine carrée, c’est-à-dire de résolution de l’équation $x^2 = a$, avec a positif. Pour déterminer la racine carrée du nombre (positif) a, il convient dès lors de considérer la suite définie par récurrence de la façon suivante : $$x_{n+1}=\frac{x_n+\frac{a}{x_n}}{2}$$ Le premier terme $x_0>0$ sera choisi assez proche de $\sqrt{a}$, en général la partie entière de $\sqrt{a}$.

Écrire la fonction heron(x: float, a: int, n: int) $\rightarrow$ float qui calcule la racine carrée de a avec une précision de rang n. On pourra vérifier que:

# racine de 2, avec le rang de précision 5
>>> heron(1, 2, 5)
1.414213562373095

# racine de 5, avec le rang de précision 5
>>> heron(2, 5, 5)
2.23606797749979

Exercice 13 ***

L’algorithme d’Euclide est l’un des plus anciens algorithmes (300 avant JC). Il permet de déterminer le Plus Grand Commun Diviseur (PGCD) de deux entiers.

Détermination du PGCD de 20 et 35:

  • $35=20\times1+15$
  • $20 = 15\times1 + 5$
  • $15 = 5\times3 + 0$
  • Le PGCD est 5.
  1. Dans l’exemple, on note $a=20$ et $b=35$. Dans la division $b÷a$, que représente 15? Observer alors le lien entre la première et la deuxième ligne.
  2. Écrire la fonction itérative pgcd(a: int, b: int) $\rightarrow$ int qui renvoie le Plus Grand Commun Diviseur de a et b. On donne comme précondition: a < b.
  3. Écrire la fonction récursive pgcd_rec(a: int, b: int) $\rightarrow$ int qui renvoie le Plus Grand Commun Diviseur de a et b.

Exercice 14 ***

En mathématiques, les coefficients binomiaux, définis pour tout entier naturel n et tout entier naturel k inférieur ou égal à n, donnent le nombre de parties de k éléments dans un ensemble de n éléments. $$C_{n}^{k}=\frac{n!}{k!\times(n-k)!}$$ La formulation récursive ci-après permet de calculer les coefficients binomiaux: $$ C(n,k) = \left\lbrace \begin{array}{ll} 1 & si~ k=0 ~ou~ n=k \\ C(n-1,k-1)+C(n-1,k) & sinon \\ \end{array} \right. $$

  1. Écrire une fonction récursive C(n: int, k: int) $\rightarrow$ int qui renvoie la valeur de C(n,k).
  2. Le triangle de Pascal est une présentation des coefficients binomiaux sous la forme d’un triangle. Dessiner le triangle de Pascal à l’aide d’une double boucle for pour n variant de 0 à 10.
1         
1 1       
1 2 1     
1 3 3 1   
1 4 6 4 1