Chapitre 5. Récursivité

Objectifs. Implémenter des versions récursives des algorithmes de recherche linéaire et dichotomique. Utiliser des paramètres de récursivité désignant des rangs dans un tableau.

Notebook dans Capytale

Soit $x$ un réel non nul. On sait que $x^0 = 1$ et on peut remarquer que : $$\begin{align*} x^1 &= x \times 1 = x \times x^0 \\ x^2 &= x \times x^1 \\ x^3 &= x \times x^2 \\ x^4 &= x \times x^3 \\ x^5 &= x \times x^4 \\ &\vdots \\ x^n &= x \times x^{n - 1}, \quad n \ge 1 \end{align*}$$

1. Écrire une fonction récursive puissance(x, n) calculant $x^n$.

   Code à trous

   1 2 3 4 5 6

   def puissance(x, n): if n == ...: # cas de base return ... else: return ... * puissance(x, ...)

   Réponse

   1 2 3 4 5 6

   def puissance(x, n): if n == 0: # cas de base return 1 else: return x * puissance(x, n - 1)

2. On donne ci-dessous la définition d’une fonction mystere(x, n) prenant en paramètre un réel x non nul et un entier positif n.

   1 2 3 4 5 6 7 8

   def mystere(x, n): if n == 0: return 1 m = mystere(x, n//2) if n%2 == 1: return x * m * m else: return m * m

   1. Calculer “à la main” mystere(x, 9). On pourra s’aider d’un schéma pour suivre l’empilement et le dépilement des appels récursifs.

      Réponse

      Le diagramme suivant montre l’empilement des appels récursifs successifs vers le bas puis le dépilement vers le haut avec passage de valeur d’un niveau récursivité vers le niveau supérieur. Le résultat obtenu pour mystere(x, 9) est donc $x^9$.

      graph TB
          m9["mystere(x, 9)"] --> m4["mystere(x, 4)"];
          m4 --> m2["mystere(x, 2)"];
          m2 --> m1["mystere(x, 1)"];
          m1 --> m0["mystere(x, 0)"];
          m0 -- 1 --> m1;
          m1 -- x fois 1 fois 1 = x --> m2;
          m2 -- x fois x = x^2 --> m4;
          m4 -- x^2 fois x^2 = x^4 --> m9;
          m9 -- x fois x^4 fois x^4 --> r9((x^9));
      

      Explications détaillées (diaporama)

   2. Que fait la fonction mystere ?

      Réponse

      mystere(x, n) renvoie $x^n$.

   3. Combien de multiplications ont été calculées au cours de l’appel mystere(x, 9). Comparer avec le nombre de multiplications calculées avec l’appel puissance(x, 9). Que peut-on en conclure ?

      Réponse

      L’appel puissance(x, 9) effectue toutes les multiplications de l’expression suivante c’est-à-dire 9 multiplications :

      $$\begin{align*} \underbrace{x \times x \times x \times x \times x \times x \times x \times x \times x}_{x^9 \text{(8 multiplications)}} \text{ }\times 1 \end{align*}$$

      D’après la figure de la question 2. a., l’appel mystere(x, 9) a nécessité le calcul e 6 multiplications.

      Conclusion. L’algorithme de calcul de la fonction mystere (exponentiation rapide) est plus économe en ressource de calcul que celui de la fonction puissance. Pour $x^n$, on peut approximer le nombre de multiplication nécéssaire au nombre de divisons par deux successives possibles pour $n$ c’est-à-dire $\log_2(n)$. On pourrait donc montrer que :

      Fonction	Complexité
      puissance(x, n)	${\cal O}(n)$
      mystere(x, n)	${\cal O}(\log_2(n))$

Le nombre $\pi$ peut être approximé en utilisant la formule suivante, que l’on peut interpréter comme la “limite” d’une suite dont les termes successifs comprennent un nombre croissant de terme d’une somme infinie. La suite s’approche de $\pi$ au fur et à mesure que l’on ajoute des termes à la somme : $$\begin{align*} \pi = 4\times \left(\frac{1}{1} - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} \cdots \right) \end{align*}$$

En utilisant cette formule (appelée série de Gregory-Leibniz), on souhaite écrire une fonction récursive pi(n) qui se rapproche de $\pi$ lorsque $n$ croît.

1. Déterminer en fonction de $n$ l’expression du terme ajouté à l’étape $n$

   Indications

   • Les dénominateurs sont impairs c’est-à-dire de la forme $2n + 1$.
   • l’alternance des signes peut se régler à l’aide de $(-1)^n$.
   Réponse

   Dans la parenthèse, chaque terme est de la forme :

   $$\begin{align*} \frac{(-1)^n}{2n + 1} &\phantom{= \dfrac{1}{1}} \end{align*}$$

   Cela fonctionne par exemple pour $n = 0$, $n = 1$ et $n = 2$:

   $$\begin{align*} \frac{(-1)^0}{2\times0 + 1} &= \frac{1}{1} \\ \frac{(-1)^1}{2\times1 + 1} &= -\frac{1}{3} \\ \frac{(-1)^2}{2\times2 + 1} &= \frac{1}{5} \end{align*}$$

   En tenant compte du facteur 4 devant la parenthèse, à l’étape $n$, le terme à ajouter est donc :

   $$\begin{align*} \frac{4(-1)^n}{2n + 1} &\phantom{= \dfrac{1}{1}} \end{align*}$$

2. Établir la définition par récurrence de $\text{pi}(n)$.

   Indications mathématiques

   • Le premier terme pour $n = 0$ est $4 \times \dfrac{1}{1} = 4$.
   • $\text{pi}(n)$ se calcule à partir de $\text{pi}(n - 1)$ en lui ajoutant le terme de l’étape $n$.
   Réponse

   $$\begin{align*} \left\{ \begin{array}{ll} \text{pi}(0) = 4 \quad \text{(cas de base pour }n = 0) \\ \text{pi}(n) = \text{pi}(n - 1) + \dfrac{4(-1)^n}{2n + 1} &\phantom{= \dfrac{1}{1}}, \quad \text{pour tout } n \geq 1 \quad \text{(formule de récurrence)} \end{array} \right. \end{align*}$$

3. En déduire une implémentation Python de la fonction récursive pi(n).

   Code à trous

   1 2 3 4 5 6

   def pi(n): if n == ...: # cas de base return ... else : return pi(...) + 4 * .../(...)

   Réponse

   1 2 3 4 5 6

   def pi(n): if n == 0: # cas de base return 4 else : return pi(n - 1) + 4*(-1)**n / (2*n + 1)

Cette exercice porte sur la programmation en général et la récursivité en particulier.

On considère un tableau de nombres de $n$ lignes et $p$ colonnes. Les lignes sont numérotées de $0$ à $n − 1$ et les colonnes sont numérotées de $0$ à $p − 1$. La case en haut à gauche est repérée par $(0\,,0)$ et la case en bas à droite par $(n−1\,,p−1)$ .

On appelle chemin une succession de cases allant de la case $(0\,,0)$ à la case $(n − 1\,,p − 1)$ , en n’autorisant que des déplacements case par case : soit vers la droite, soit vers le bas.

On appelle somme d’un chemin la somme des entiers situés sur ce chemin. Par exemple, pour le tableau $tab$ suivant :

• Un chemin est $(0\,,0)$, $(0\,,1)$, $(0\,,2)$, $(1\,,2)$, $(2\,,2)$, $(2\,,3)$ (en rouge sur le tableau) ;
• La somme du chemin précédent est $14$.
• $(0\,,0)$, $(0\,,2)$, $(2\,,2)$, $(2\,,3)$ n’est pas un chemin.

L’objectif de cet exercice est de déterminer la somme maximale pour tous les chemins possibles allant de la case $(0\,, 0)$ à la case $(n−1\,,p−1)$ .

1. On considère tous les chemins allant de la case $(0\,,0)$ à la case $(2\,,3)$ du tableau $tab$ donné en exemple.

   1. Un tel chemin comprend nécessairement 3 déplacements vers la droite. Combien de déplacements vers le bas comprend-il ?

      Réponse

      On a représenté ci-dessous l’allure du tableau $tab$ donné en exemple. Les cases $(0\,, 0)$ et $(2\,, 3)$ ont été repérées.

      

      Un chemin allant de la case $(0\,,0)$ à la case $(2\,,3)$ comprend nécessairement 2 déplacements vers le bas car le tableau possède 3 lignes.

      Remarque. La question ne demandait pas clairement de justifier la réponse. Dans le doute, il faut mieux le faire. Une figure est toujours appréciée pour justifier mais attention à la gestion de votre temps.

   2. La longueur d’un chemin est égal au nombre de cases de ce chemin. Justifier que tous les chemins allant de $(0\,, 0)$ à $(2\,, 3)$ ont une longueur égale à $6$.

      Réponse

      D’après la question précédente, un déplacement de la case $(0\,, 0)$ à la case $(2\,, 3)$ comprend nécessairement 2 déplacements vers le bas et 3 déplacements vers la droite. Donc au cours de ce déplacement, on visite 5 cases auxquelles il faut ajouter la case de départ. Ainsi, 6 cases sont visitées. Donc, tous les chemins allant de la case $(0\,, 0)$ à la case $(2\,, 3)$ ont une longueur égale à 6.

2. En listant tous les chemins possibles allant de $(0\,,0)$ à $(2\,,3)$ du tableau $tab$, déterminer un chemin qui permet d’obtenir la somme maximale et la valeur de cette somme.

   Réponse

   Un chemin qui permet d’obtenir la somme maximale est $(0\,,0)$, $(1\,,0)$, $(2\,,0)$, $(2\,,1)$, $(2\,,2)$, $(2\,,3)$. On l’a représenté en rouge ci-dessous :

   $4$	$1$	$1$	$3$
   $2$	$0$	$2$	$1$
   $3$	$1$	$5$	$1$

   La somme maximale est donc $4 + 2 + 3 + 1 + 5 + 1 = 16$.

   Remarque. Cette question semble demander de lister tous les chemins possibles mais ils sont très nombreux. Ce serait une perte de temps importante. Ici, il semble pertinent de répondre sans justifier en donnant directement la réponse. Il existe cependant une méthode permettant d’explorer tous les chemins possibles à l’aide d’un arbre binaire.

   • la racine de l’arbre représente la case de départ $(0\,,0)$ ;
   • tout autre nœud correspond à une case du tableau visitée lors d’un chemin ;
   • une arrête reliant un nœud à son nœud fils de gauche représente un déplacement vers le bas ;
   • une arrête reliant un nœud à son nœud fils de droite représente un déplacement vers la droite ;
   • une arrête reliant un nœud à un unique fils représente un éplacement obligatoire vers le bas ou la droite (cas où un bord du tableau a été atteint);
   • une feuille de l’arbre a pour valeur la somme des valeurs des cases rencontrées sur le chemin reliant la racine à la feuille.

   Voici l’arbre en question :

   graph TB
   A(4) --> B(2);
   B --> C(3) ;
   C --> D(1);
   D --> E(5);
   E --> F(1);
   F --> G[16];
   B --> H(0);
   H --> I(1);
   I --> J(5);
   J --> K(1);
   K --> L[13];
   H --> M(2);
   M --> N(5);
   N --> O(1);
   O --> P[14];
   M --> Q(1);
   Q --> R(1);
   R --> S[10];
   A --> T(1);
   T --> U(0);
   U --> V(1);
   V --> W(5);
   W --> X(1);
   X --> Y[12];
   U --> Z(2);
   Z --> a(5);
   a --> b(1);
   b --> c[13];
   Z --> d(1);
   d --> e(1);
   e --> f[9];
   T --> g(1);
   g --> h(2);
   h --> i(5);
   i --> j(1);
   j --> k[14];
   h --> l(1);
   l --> m(1);
   m --> n[10];
   g --> o(3);
   o --> p(1);
   p --> q(1);
   q --> r[11];
   

3. On veut créer le tableau $tab2$ où chaque case $(i\,,j)$ contient la somme maximale pour tous les chemins possibles allant de $(0\,,0)$ à $(i\,,j)$.

   1. On considère le tableau $tab$ ci-dessous.

      $4$	$1$	$1$	$3$
      $2$	$0$	$2$	$1$
      $3$	$1$	$5$	$1$

      Compléter et recopier sur votre copie le tableau $tab2$ donné ci-dessous associé au tableau $tab$ précédent.

      $4$	$5$	$6$	$?$
      $6$	$?$	$8$	$10$
      $9$	$10$	$?$	$16$

      Réponse

      $4$	$5$	$6$	$9$
      $6$	$6$	$8$	$10$
      $9$	$10$	$15$	$16$

      Explications :

      Case $(0\,,3)$

      

      La seule façon d’arriver à cette case est par la gauche par la case $(0\,,2)$ qui contient la somme maximale 6 dans le tableau $tab2$. Il faut ajouter à ce nombre le nombre contenu dans la case d’arrivée $(0\,,3)$ du tableau $tab$ c’est-à-dire 3. Le résultat à reporter dans le tableau $tab2$ est donc $6 + 3 = 9$.

      Case $(1\,,1)$

      

      Il y a deux façons d’arriver à cette case : par la case $(0\,,1)$ ou par la case $(1\,,0)$. Parmi ces deux cases, la somme maximale dans $tab2$ est 6. Il faut ajouter à ce nombre le nombre contenu dans la case d’arrivée $(1\,,1)$ du tableau $tab$ c’est-à-dire 0. Le résultat à reporter dans le tableau $tab2$ est donc $6 + 0 = 6$.

      Case $(2\,,2)$

      

      Il y a deux façons d’arriver à cette case : par la case $(1\,,2)$ ou la case $(2\,,1)$. Parmi ces deux cases, la somme maximale dans $tab2$ est 10. Il faut ajouter à ce nombre le nombre contenu dans la case d’arrivée $(2\,,2)$ du tableau $tab$ c’est-à-dire 5. Le résultat à reporter dans le tableau $tab2$ est donc $10 + 5 = 15$.

   2. À partir de cette question, on choisit de représenter les tableaux $tab$ et $tab2$ par un tableau Python (type list) père contenant des tableaux Python (type list) fils. Chaque tableau fils représente une ligne du tableau. Par exemple, le tableau $tab$ de la question précédente est représenté en Python comme suit.

      1 2 3 4 5

      tab = [ [4, 1, 1, 3], [2, 0, 2, 1], [3, 1, 5, 1] ]

      Justifier que si j est différent de 0, alors : tab2[0][j] = tab[0][j] + tab2[0][j-1].

      Réponse

      tab2[0][j] désigne la somme maximale de la case $(0\,,j)$ qui se trouve dans la première ligne du tableau (case de départ $(0\,,0)$ exclue car j est différent de 0). La seule façon d’arriver à cette case est de venir de la gauche par la case $(0\,,j-1)$ comme présenté sur la figure ci-dessous :

      

      Pour calculer tab2[0][j] il faut donc additionner :

      • la somme maximale de la case $(0\,,j-1)$ c’est-à-dire tab2[0][j-1] ;
      • et la valeur du tableau de départ contenue dans la case $(0\,,j)$ c’est-à-dire tab[0][j].

      Donc si j est différent de 0, alors : tab2[0][j] = tab[0][j] + tab2[0][j-1].

4. Justifier que si i et j sont différents de 0, alors : tab2[i][j] = tab[i][j] + max(tab2[i-1][j], tab2[i][j-1]).

   Réponse

   tab2[i][j] désigne la somme maximale d’une case $(0\,,j)$ qui ne se trouve ni dans la première ligne ni dans la première colonne. Pour une telle case, il y a deux façons d’y arriver :

   • de la gauche par la case $(i\,,j-1)$;
   • du haut par la case $(i-1\,,j)$.

   

   Pour calculer tab2[0][j] il faut donc :

   • déterminer des deux cases précédentes celle qui contient la plus grande somme maximale c’est-à-dire max(tab2[i-1][j], tab2[i][j-1]);
   • ajouter ce maximum à la valeur du tableau de départ contenue dans la case $(i\,,j)$ c’est-à-dire tab[i][j].

   Donc si i et j sont différents de 0, alors : tab2[i][j] = tab[i][j] + max(tab2[i-1][j], tab2[i][j-1]).

5. On veut créer la fonction récursive somme_max ayant pour paramètres un tableau tab, un entier i et un entier j. Cette fonction renvoie la somme maximale pour tous les chemins possibles allant de la case $(0\,,0)$ à la case $(i\,,j)$ de tab.

   Aide

   Exécution visuelle sur le tableau exemple (diaporama)

   1. Quel est le cas de base, à savoir le cas qui est traité directement sans faire appel à la fonciton somme_max ? Que renvoie-t-on dans ce cas ?

      Réponse

      Le cas de base correspond au traitement de la case de départ $(0\,,0)$ c’est à dire pour $i = j = 0$. Dans ce cas, il n’y a aucun calcul à réaliser. Il suffit de renvoyer la valeur de la case $(0\,,0)$ c’est-à-dire tab[0][0]. En effet, le chemin venant de débuter, la somme des valeurs rencontrées se limite simplement à la valeur de la case de départ.

   2. À l’aide de la question précédente, écrire en Python la fonction récursive somme_max.

      Réponse

      Dans les questions précédentes, nous avons vu :

      • le cas de base : la case de départ $(0\,,0)$ ;
      • le cas d’une case de la première ligne : $(0\,,j)$, $j\neq 0$.

      Il manque le cas d’une case de la première colonne : $(i\,,0)$, $i\neq 0$.

      On suit la même approche qu’à la question 3.b. :

      

      Le schéma permet d’en déduire comment calculer tab2[i, 0] :

      tab2[i, 0] = tab[i, 0] + tab2[i-1, 0]

      On peut maintenant écrire la fonction somme_max :

      1 2 3 4 5 6 7 8 9 10

      def somme_max(tab, i, j): if i == 0 and j == 0: #(1)! return tab[0][0] elif i == 0 and j > 0: #(2)! return tab[i][j] + somme_max(tab, i, j-1) elif i > 0 and j == 0: #(3)! return tab[i][j] + somme_max(tab, i-1, j) else: #(4)! maxi = max(somme_max(tab, i, j-1), somme_max(tab, i-1, j)) return tab[i][j] + maxi

      1. Cas de base. Case de départ $(0\,,0)$.
      2. Case en première ligne (sauf case de départ)
      3. Case en première colonne (sauf case de départ)
      4. Case quelconque (sauf premières ligne et colonne)

   3. Quel appel de fonction doit-on faire pour résoudre le problème initial ?

      Réponse

      Remarque La question me semble ambigüe. Doit-on répondre à cette question dans le cas général ou avec l’exemple vu en début d’énoncé ? La deuxième option me semble plus simple.

      • Option 1. Exemple de tableau vu en début dénoncé

        On suppose que le tableau tab donné en exemple en début d’énoncé a été préalablement déclaré.

        Pour connaître la somme maximale pour tous les chemins possibles allant de la case $(0\,,0)$ à $(2\,,3)$ dans ce tableau, il faut exécuter l’appel somme_max(tab, 2, 3) renvoyant 16.

        Tester dans Python Tutor

      • Option 2. Cas général

        On suppose qu’un tableau tab contenant n lignes et p colonnes a été préalablemant déclaré.

        Remarque. À partir de tab, on peut obtenir n et p de la façon suivante :

        1 2	n = len(tab) p = len(tab[0])

        Pour connaître la somme maximale pour tous les chemins possibles allant de la case $(0\,,0)$ à $(n-1\,,p-1)$ dans ce tableau, il faut exécuter l’appel somme_max(tab, n-1, p-1).

• Énoncé
• Correction
• Exécution visuelle de l’algorithme récursif (diaporama)