009_Récursivité

La récursivité

Reprenons le calcul de x^n. On suppose que l’on a fait une partie du travail, disons on a calculé x^{i}. C’est fini si i= n. Sinon, en multipliant le résultat déjà calculé par x, on obtient x^{i+1} Par changement de i en i + 1, on se ramène à l’hypothèse de départ. Pour démarrer, on peut prendre i = 1 et x^{i} = x.

La récurrence joue donc de la façon suivante:

  • si j’ai pu calculer x^{i}, je peux calculer x^{i+1}
  • or je peux calculer x^{1}.

Sans rien changer à cette forme de raisonnement, nous pouvons construire un algorithme « récursif ».

expr(x, n)
{
    if (n == 1) return x ;
    else return x * expr(x, n-1) ;
}

Pour écrire la définition récursive de exp (x, n), nous avons utilisé la propriété bien connue

    \[x^{n} =x\times x^{n-1}\]

Construction

Reprenons le calcul de x^n :

 \begin{tabular}{l} {\tt exp$(x, n) = \underbrace{x \times x \times x \times ... \times x}_{(n x {\rm\ dans\;cette\;formule})}$}\\ Encadrons les $n - 1$ $x$ de droite \\ {\tt exp$(x, n)=x \times$ \fbox{$x\times x\times ... \times x$}} \\ \hspace*{2.5cm} ($n-1$ $x$ dans la bo\^\i te)\\ \end{tabular}

On retrouve la relation connue

exp (x, n)=x \times exp (x,n -1)

Comme cas singulier, on peut prendre exp (x, 1) = x ou exp (x, 0) = 1 (qui a l’avantage d’étendre la définition au cas n = 0)

exp(x, n)
{
    if (n == 0)
        return 1 ;
return x * exp(x, n-1) ;
}

On peut grouper autrement les x dans exp (x, n). Supposons n pair. On peut partager les x en deux paquets égaux : exp(x,n)= x\times x\times\ldots\times x \times x\times x\times\ldots\times x avec \frac{n}{2} x dans chaque paquet
Dans ce cas

exp (x,n)= exp (x,\frac{n}{2})^{2}

Si maintenant n est impair, nous pouvons faire de même, en mettant à part le premier x
exp (x, n)=x \times x\times x\times\ldots\times x \times x\times \ldots\times x

On obtient ainsi une deuxième définition :

exp2(x, n)
{
    if (n == 0)
      return 1 ;

    y = expr2(x, n/2) ;
    if (pair(n))
        return y * y ;
   return y * y * x ;
}

Nous pouvons faire, quand n est pair, les groupements d’une autre façon, en enfermant les paires de x dans des boîtes.

exp (x,n)=x\times x \times \ldots\timesx\times x

Il y a \frac{n}{2} boîtes ayant chacune deux x

exp3(x, n)
{
    if (!n) return 0 ;
    if (pair(n))
        return exp3(x*x, n/2) ;
    return x * exp3(x*x, n/2) ;
}

Le pgcd d’Euclide

Euclide (300 av. J.-C.) a donné un algorithme pour trouver le PGCD de 2 nombres entiers positifs :

PGCD (a, b)
    if (b == 0) return (a) ;
    else        return (PGCD(b, a % b)) ;

ou son équivalent sous forme d’une boucle

PGCD (a, b)
1 PGCD (a, b)
2     while (b != 0)
      {
3         t = a ;
4         a = b ;
5         b = t % b ;
      }
6     return a ;

Preuve mathématique

  1. Si PGCD (a, b) alors d divise a et b
  2. (a \% b)=a-q.b (q = reste de la division de a par b)
    \longrightarrow (a \% b) est une combinaison linéaire de a et b
    comme d divise b et a et que (a \% b) est une combinaison linéaire de a et b alors d divise (a \% b) cela permet de dire que d divise PGCD (b, a \% b)

Cela implique que :

d qui est PGCD (a, b) divise PGCD (b, a \% b) donc, PGCD (a, b) divise PGCD

idem pour PGCD (b, a \% b) divise PGCD (a, b) donc : PGCD (a, b) = PGCD (b, a \% b)

Preuve de l’algorithme

Trace de l’algorithme pour 30 et 21

Lignes 1 3 4-5 3 4-5 3 4-5
a 30 30 21 21 9 9 3 \longleftarrow PGCD
b 21 21 9 9 3 3 0 \longleftarrow condition d’arrêt
t 30 30 21 21 9 9

b ne peut jamais devenir négatif et il est toujours diminué de la valeur (a \% b) qui est b.

Modulo est une fonction qui

  • ramène toujours une valeur inférieure d’au moins 1 par rapport à l’opérande droit.Ex :3 \%2 = 1,\quad 1 < 2,
  • possède aussi comme caractéristique de donner 0 si b vaut 1, car \forall x, x/1 = x, donc (x \% 1) = 0,
  • renvoie a, si a < b .

Donc, b diminue de un moins 1 à chaque appel, et à la fin il doit valoir 0, donc la condition de sortie de la fonction arrivera toujours, quelles que soient les valeurs a et b données en entrées entières positives. Cette première validation est extrêmement importante, il est fondamental qu’un programme récursif, une boucle, ait une condition d’arrêt.