008_Schéma fonctionnel

Récursivité

010_Temps et espace d’exécution

La récursivité

Reprenons le calcul de . On suppose que l’on a fait une partie du travail, disons on a calculé . C’est fini si . Sinon, en multipliant le résultat déjà calculé par , on obtient Par changement de en , on se ramène à l’hypothèse de départ. Pour démarrer, on peut prendre et . La récurrence joue donc de la façon suivante:

• si j’ai pu calculer , je peux calculer
• or je peux calculer .

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 , nous avons utilisé la propriété bien connue

   

Construction

Reprenons le calcul de :

On retrouve la relation connue

exp exp

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

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

On peut grouper autrement les dans exp . Supposons pair. On peut partager les en deux paquets égaux : exp avec dans chaque paquet Dans ce cas

exp exp

Si maintenant est impair, nous pouvons faire de même, en mettant à part le premier exp 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 est pair, les groupements d’une autre façon, en enfermant les paires de dans des boîtes.

exp

Il y a boîtes ayant chacune deux

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 alors divise et
2. reste de la division de par est une combinaison linéaire de et comme divise et et que est une combinaison linéaire de et alors divise cela permet de dire que divise PGCD

Cela implique que :

qui est PGCD divise PGCD donc, PGCD divise PGCD

idem pour PGCD divise PGCD donc : PGCD PGCD

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	PGCD
b	21	21	9	9	3	3	0	condition d’arrêt
t	–	30	30	21	21	9	9

ne peut jamais devenir négatif et il est toujours diminué de la valeur qui est . Modulo est une fonction qui

• ramène toujours une valeur inférieure d’au moins 1 par rapport à l’opérande droit.Ex :,
• possède aussi comme caractéristique de donner si vaut , car , donc ,
• renvoie , si .

Donc, 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 et 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.

008_Schéma fonctionnel

010_Temps et espace d’exécution