Exercices récursivité

Lang 08

Exercices

Exercice 1 *

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) -> int qui calcule n!.
  2. Estimer le coût 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) -> int qui implémente cette fonction.
  5. Estimer le coût de cette fonction.

Exercice 2 *

  1. Écrire une fonction récursive entiers(i: int, k: int) -> 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) -> None qui affiche les nombres impairs entre i et k.

Exercice 3 **

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) -> 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) -> None qui stocke les valeurs successives dans un tableau.

Exercice 4 **

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) -> int qui renvoie le n-ième terme de la suite.

Exercice 5 **

  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) -> 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 6 **

  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) -> 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 7 **

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) -> int qui renvoie le nombre de chiffres qui composent n.

Exercice 8 **

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