Le but est d’initier à l’écriture d’algorithmes récursifs terminaux, sur des objets mathématiquement simples. Les bouts de codes en python sont rassemblés dans le fichier arith_int.py.
définition
On note (lire factorielle ) le produit des nombres entiers de à : .
Quand vaut , la liste des facteurs est vide, le résultat doit être l’élément neutre de la multiplication : .
Le code python qui correspond à cette définition est :
def fact1(n):
f = 1
for j in range(1,n+1):
f = f*j
return f
Mais en python, on peut plus directement utiliser reduce :
def fact1bis(n):
return reduce(n.__mul__,range(1,n+1),1)
Il y a aussi une définition récursive de : le cas de base est , et le cas de récursion est , ce qui conduit au code :
def fact2a(n):
if n==0:
return 1
else:
return n*fact2a(n-1)
Là encore python dispose d’une syntaxe souple et riche pour les expressions conditionnelles :
def fact2abis(n):
return 1 if n==1 else n*fact2abis(n-1)
Le problème avec cette version récursive est la limitation de la taille de la pile qui permet à python de gérer les appels récursifs.
On peut chercher une version récursive terminale :
def fact2b(n,f=1):
# return f if n==1 else fact3(n-1,n*f)
return f if n==0 else fact2b(n-1, n*f)
(noter l’argument optionnel f qui sert d’accumulateur et prend par défaut la valeur 1) puis la dérécursifier, ce qui donne peu ou prou la première version :
def fact2(n, f=1):
while n>0:
n, f = n-1, n*f
else:
return f
On a gardé l’argument optionnel : le résultat de fact2(n,f) est . C’est aussi l’invariant de la boucle while.
Pour s’entainer, généralisons aux nombres d’arrangements.
définition
On note (lire puissance sousligné) le produit dégressif de facteurs commençant à : .
La définition récursive est limpide : si vaut , le résultat est ; sinon, le résultat est fois le résultat obtenu pour et à la place de et :
Il en découle que et que dès que . On obtient le code :
def puis_sous(n,p):
if p==0:
return 1
elif p==1:
return n
else:
return n*puis_sous(n-1,p-1)
C’est bien mais c’est récursif, pas terminal.
exercice
Dérécursifier la fonction puis_sous comme on l’a fait pour fact2.
On veut maintenant calculer , qui est le produit de facteurs égaux à . Bien sûr on peut utiliser la définition récursive évidente : si vaut , le résultat est , et sinon le résultat est . On a alors multiplications à effectuer (car on ne compte évidemment pas la première, de la forme ).
On peut décomposer le problème en deux : si , on calcule . Par exemple si le résultat est ou encore . Si on note le nombre de multiplications éffectuées pour élever à la puissance le nombre , cette méthode donne si , mais seulement quand . Pour les petites valeurs on obtient :
n 1 2 4 8 C(n) 0 1 2 3
On devine, et on peut démontrer par récurrence, que , ie pour une puissance entière de deux.
Quand est impair, il y a une mutliplication par de plus : . En notant et le quotient et le reste dans la division euclidienne de par , la formule générale est .
Voici trois versions de l’algorithme correspondant. Les bits de (ie les chiffres de son écriture en base 2) sont lus et utilisés dans l’ordre des poids croissants : d’abord , puis , puis , puis , etc. C’est en rapport avec l’écriture sous forme de polynôme, ou de série :
Nous avons décidé de ne pas prendre en compte dans la suite le cas trivial . Les fonctions suivantes sont correctes quand leur argument n est un entier naturel non nul.
def puis_rap1a(a,n): if n==1: return a else: b = puis_rap1a(a,n/2) return (1 if n%2==0 else a)*b*b
def puis_rap1b(a,n,b=1): return a*b if n==1 else puis_rap1b(a*a, n/2, b if n%2==0 else a*b)
def puis_rap1(a,n,b=1): while n>1: a, n, b = a*a, n/2, b if n%2==0 else a*b else: return a*b
exercice
Démontrer que dans cet algotihtme . On a noté la partie entière d’un réel , c’est-à-dire le plus grand entier tel que .
Les multiplications que l’on effectue dans cet algorithme concernent des nombres dont la taille augmente au cours du calcul.
Voici maintenant un algorithme où les multiplications sont soit des mises au carré soit des multiplication par . Il est relié au shéma de Hörner pour l’évaluation de l’écriture polynômiale de :
En revanche, puisqu’il utilise les bits de dans l’ordre des poids décroissants, il faut commencer par décomposer en base .
def puis_rap2(a,n,b=1):
l=[]
while n>1:
l.append(n%2)
n=n/2
else:
x=a
while l<>[]:
x=x*x
if l.pop()==1:
x=x*a
else:
return x*b
théorème
Étant donné un couple d’entiers relatifs, , il existe un unique couple tel que et .
définition
On dit que est le quotient et le reste dans la division de par .
démonstration
Appelons amissibles les couples vérifiants . Alors est admissible. Et, si l’est alors et le sont aussi. On cherche un couple admissible tel que les deux conditions et soient vraies. On a toujours au moins une des deux. On part de . Si est fausse, on applique , ce qui augmente qui était trop petit ; si est fausse, on applique , ce qui diminue qui était trop grand. On répète jusqu’à ce que la condition fausse devienne vraie, ce qui est obligé d’arriver car l’ordre usuel sur est bien fondé : il n’existe pas de suite infinie strictement décroissante d’entiers naturels. Et alors les deux conditions sont vérifiées.
L’unicité revient à dire, en faisant la différence de deux solutions, que parmi les vérifiant , le seul multiple de est .
L’algorithme évident contenu dans la démonstration demande soustraction. En voici une version qui est correcte si l’argument a fourni est un entier naturel et l’argument b un entier naturel non nul.
def quo_res1(a,b):
q,r=0,a
while r>=b:
q,r=q+1,r-b
else:
return q,r
De même que pour les puissances, on peut chercher un algorithme plus efficace, qui obtient les bits du quotient q dans l’ordre des poids décroissants. La première boucle détermine en montant le poid du bit de poid maximal. La boucle suivante redescend et met à jour le quotient et le reste.
def quo_res2(a,b):
k,c=0,b
while c<=a:
k,c=k+1,c*2
q,r,c=0,a,c/2
for j in range(k):
if r<c:
q,c=q*2,c/2
else:
q,r,c=q*2+1,r-c,c/2
return q,r
exercice
Pour les deux fonctions quo_res1 et quo_res2, donner pour chaque boucle les propriétés invariantes et justifier la terminaison.
Dans cet algorithme, les opérations binaires k=k+1, c=c*2, c=c/2, q=q*2 et q=q*2+1 sont considérées comme élémentaires et négligeables. Les opérations importantes sont les soustractions r=r-c. Il y en a au plus k, c’est-à-dire le nombre de bits dans l’écriture de en base : .
définition
Le plus grand commun diviseur (en abrégé pgcd) de deux entiers relatifs et est l’entier naturel le plus grand parmi ceux qui divisent à la fois et . On le note .
Deux entiers relatifs sont premiers entre eux quand leur pgcd est .
Le calcul du pgcd de deux entiers est une opération courante en arithmétique, par exemple pour simplifier ou additionner des fractions. On dispose pour cela de l’algorithme d’Euclide qui repose sur les constatations suivantes :
exercice
Écrire une fonction qui retourne le pgcd de ses deux arguments supposés entiers naturels, en suivant l’algorithme décrit ci-dessus.
On peut accélerer l’algorithme en remarquant que si l’étape 2 est répétée plusieurs fois sans échanger les deux nombres, c’est que l’on est en train de calculer le reste dans la division euclidienne du plus grand par le plus petit. Cela donne, en utilisant l’opérateur standard a%b pour le reste de a divisé par b (mais on pourrait tout aussi bien utiliser nos fonctions quo_res1 ou quo_res2 :
def pgcd1(x,y):
while y<>0:
x,y=y,x%y
return x
Là encore on pourrait chercher une version binaire. Pour cela on commence éliminer le cas où l’un des nombres est nul. Puis on extrait la plus grande puissance de 2 commune, puis on se ramène au cas de deux nombres impairs :
def pgcd2(x,y):
if x==y or y==0:
return x
elif x==0:
return y
c=1
while x%2==0 and y%2==0:
x,y,c=x/2,y/2,c*2
if y%2==0:
x,y=y/2,x
while True:
while x%2==0:
x=x/2
if x>y:
x=(x-y)/2
elif x<y:
x,y=(y-x)/2,x
else:
return c*x
théorème
Soit et deux entiers relatifs.
définition
En particulier, il existe deux entiers relatifs et tels que . Ceux sont des coefficients de Bezout des nombres .
La partie 2 du théorème et la définition des coefficients de Bezout se généralise en l’étude de l’équation . Les coefficients sont des entiers relatifs. Une solution de l’équation est un couple d’entiers relatifs qui vérifient l’équation.
Si n’est pas un multiple de , il n’y a pas de solutions. Si , alors l’ensemble des solutions n’est pas vide. Il y a existence mais pas unicité : si est solution, alors pour tout , le couple est encore solution, où vérifient (et donc aussi , ceux sont même les plus grands diviseurs respectivement de et premiers entre eux).
C’est le même principe de décomposition en solution particulière de l’équation complète (avec second membre ) plus solution générale de l’équation homogène () que pour les systèmes linéaires et les équations différentielles linéaires.
Pour trouver une solution particulière de l’équation complète, on se ramène à avec maintenant . Si on connaît des coefficients de Bezout pour les nombres premiers entre eux , on peut choisir comme solution particulière .