[PDF] La récursivité Lalgorithme dEuclide Implémentation en Python

View - Download La récursivité Lalgorithme dEuclide Implémentation en Python

Previous PDF

Next PDF

La récursivité

Lycée Blaise Pascal

Octobre 2015

1/29L"algorithme d"Euclide

Extrait d"un cours de TS :Proposition

Soientaetbdeux entiers naturels non nuls et soitrle reste dans la division euclidienne deaparb. On a : PGCD(a;b) =PGCD(b;r).Ummagumma

Mise en abyme ou récursivité?

4/29

2/29Implémentation en Python

Puisque le PGCD deaet debet le PGCD est le reste debet du resterdans la division euclidienne deaparb:defp gcd(a,b): return p gcd(b,a%b)

3/29Ummagumma

Mise en abyme ou récursivité?

4/29

Implémentation en Python

On obtient :>>>pgcd(1768,1001)

ZeroDivisionError: integer division

o r m odulob y zero ... puisque pour calculer PGCD(1768,1001), il faut calculer PGCD(1001,767) et pour cela calculer PGCD(767,234) et pour cela calculer PGCD(26,13) et pour cela calculer PGCD(13,0) et pour cela calculer le reste dans une division euclidienne par 0.

5/29Inclure un test d"arrêt

On arrête le processus lorsqueb=0 :defp gcd(a,b): if b = =0 : return a else return p gcd(b,a%b) donne comme espéré : >>>pgcd(1768,1001) 13

6/29Une suite récurrente

Soit(un)la suite définie surNpar :

?u0=1 u n=n×un-1pourn>0 Cette suite s"implémente naturellement par :deff actorielle(n): if n = =0 : return 1 else return n *factorielle(n-1)

7/29La fonction factorielle

La fonctionfactorielle()donne :>>>factorielle(120) ou bien (après un long moment d"attente) : >>>factorielle(-2)

RuntimeError: maximum recursion depth exceeded

in c omparison 8/29

La fonction factorielle

Nous améliorons la fonctionfactorielle():deff actorielle(n): assert n >= 0, n d oit tre p ositif if n = =0 : return 1 else return n *factorielle(n-1) >>>>>>factorielle(-2)

AssertionError: n doit être positif

9/29Terminaison d"une fonction récursive : le cas de factoriel

La fonctionfactorielle()termine. En effet :

Sin<0, la fonction renvoie une exception.

Sin=0, la fonction renvoie 1.

Sin>0, la fonction s"appelle elle-même pour une suite strictement décroissante de nombres entiers positifs : le nombre d"appels est doncfini.

10/29Terminaison d"une fonction récursive

Pour la suite de Syracuse, on ne sait pas démontrer que la fonction termine ou non.defs yracuse(n): assert n> 0, n d oit tre s trictement positif if n = =1 : return 1 elif n %2= =0 : return s yracuse(n//2) else return s yracuse(3*n+1)

11/29Correction d"une fonction récursive : le cas factoriel

Afin de démontrer que la fonctionfactorielle(n)calcule bienn! pour tout entier natureln, on procède à l"aide d"une démonstration par récurrence : Pour tout entier natureln, on noteP(n)la proposition :

P(n): " La fonctionfactorielle(n)retournen!"

12/29 Correction d"une fonction récursive : le cas factoriel

Démonstration par récurrence :

Initialisation:

factorielle(0)renvoie 1.

Hérédité:

Or par hypothèse de récurrence,factorielle(n)renvoien!, doncfactorielle(n+1)renvoie(n+1)×n! = (n+1)!.

Conclusion:

Pour tout entier natureln,factorielle(n)renvoien!. La correction de l"algorithme est démontrée.

13/29Complexité d"une fonction récursive : le cas factoriel

Pour calculerfactorielle(n), il faut faire une comparaison, une multiplication et calculerfactorielle(n-1).

Si on notecnla complexité, on a donc :

?n?N?,cn=1+1+cn-1 Ainsi(cn)est une suite arithmétique de raison 2.

La fonction factorielle est de complexitéO(n).

14/29La pile d"exécution : le cas factoriel

A chaque appel récursif de la fonction, il faut stocker dans une pile les résultats intermédiaires pour les restituer ensuite :>>> factorielle(4)

factorielle <- 4#E mpilaged e4 factorielle <- 3#E mpilaged e3 factorielle <- 2#E mpilaged e2 factorielle <- 1#E mpilaged e1 factorielle <- 0#E mpilaged e0 factorielle -> 1#D épilagee tr etourd e1

factorielle -> 1#D épilagee tr etourd e1*1 factorielle -> 2#D épilagee tr etourd e2*1 factorielle -> 6#D épilagee tr etourd e3*2 factorielle -> 24#D épilagee tr etourd e4*6 A ne pas perdre de vue : compter le nombre d"opérations est une

chose, évaluer l"espace mémoire nécessaire en est une autre...15/29La pile d"exécution : faut pas pousser Mémé

Quand on remplit trop la pile d"exécution :RuntimeError: maximum recursion depth exceeded Certes, Python permet d"utiliser la récursivité, mais ce n"était pas la préoccupation principale de Guido Van Rossum lorsqu"il a créé ce langage. Par défaut, le nombre d"appels récursifs est limité à 1000.

Pour changer cela :>>>i mports ys

>>> sys.setrecursionlimit(10000) 16/29 La récursivité terminale : variante de la fonction factorielle def f actorielle(n): if n = =0 : return 1 else return n *factorielle(n-1) def f actorielleTerm(n,accu=1): if n = =0 : return a ccu else return f actorielleTerm(n-1,n * a ccu) Cette fonction se distingue de la précédente par l"usage d"un paramètre supplémentaire et l"absence d"opération entre l"appel récursif et l"instructionreturn.

17/29La récursivité terminale : variante de la fonction factorielle

>>> factorielleTerm(4) factorielleTerm <- (4,)

factorielleTerm <- (3, 4)#a ccu= 4 factorielleTerm <- (2, 12)#a ccu= 1 2factorielleTerm <- (1, 24)#a ccu= 2 4factorielleTerm <- (0, 24)#a ccu= 2 4factorielleTerm -> 24

factorielleTerm -> 24 factorielleTerm -> 24 factorielleTerm -> 24 factorielleTerm -> 24 Il n"est pas nécessaire d"empiler les valeurs puisqu"on ne les réutilise pas : pas de problème de pile d"exécution. Cela dit, Python ne tire pas profit de cette idée et la récursivité terminale est sans intérêt dans ce langage.

18/29Nouvel exemple : la recherche dichotomique

On dispose d"un tableautde nombres triés dans l"ordre croissant et on veut déterminer si un nombrexappartient ou non à ce tableau.

On comparexavec la valeur centrale du tableau :?

Sixest la valeur centrale, c"est terminé!

Sixest inférieur à la valeur centrale, on cherche dans le sous-tableau des valeurs inférieures à cette dernière. Sixest supérieur à la valeur centrale, on cherche dans le sous-tableau des valeurs supérieures à cette dernière.

19/29Recherche dichotomique : une version récursive

def r echDicho(x,t ab): d = 0 f = l en (tab)-1 return r d(x,t ab,d ,f ) def r d(x,t ab,d ,f ): m = (d + f)//2 if t ab[m]= =x : return T rue if f = =d : return

F alse

if t ab[m]> x : return r d(x,t ab,d ,m -1) else return r d(x,t ab,m +1,f ) 20/29

Complexité d"une recherche dichotomique

Notonsnla longueur du tableautab.

Pour effectuer une recherche dichotomique sur un tableau de longueurn, il faut faire 3 comparaisons, 2 opérations et effectuer la recherche dichotomique sur un tableau de longueur (presque) n2 En notantcnla complexité pour un tableau de longueurn, on a : c n=5+cn2

21/29Complexité d"une recherche dichotomique

c n=5+cn2 =10+cn4 =15+cn8 c n=5p+cn2 p oùpest tel quen2 p=1.

C"est-à-dire :

p=log2(n) Ainsi la complexité de la recherche dichotomique est enO(log(n)).

22/29Nouvel exemple : la suite de Fibonacci

On considère la suite définie pour tout entier naturelnpar : ?f 0=1 f 1=1 f n+2=fn+1+fn dont on rappelle pour mémoire les premiers termes :

1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,258423/29La suite de Fibonacci en Python

Une version naturelle :deff ibo(n):

P our n >=1 if n < =2 : return n else return f ibo(n-1)+fibo(n-2) 24/29

Complexité de la suite de Fibonacci

Notons à nouveaucnla complexité. On a :

?n?3,cn=1+cn-1+cn-2[E]

On définit alorsdntel que :cn=2dn+1-1.

[E] donne alors :

2dn+1-1=1+2dn-1+2dn-1-1

c"est-à-dire : d n+1=dn+dn-1 La suite(dn)est la suite de Fibonacci(fn). Comme on sait que en +∞,fn≂1⎷5

1+⎷5

2 n, alors on en déduit que la complexité de la suite de Fibonacci est enO(φn).

25/29La suite de Fibonacci : arbre des appels

f 6f 5f 4f 3f 2f 1f 2f 3fquotesdbs_dbs44.pdfusesText_44

[PDF] automobile in corsa

[PDF] pélican volant de marey (1882)

[PDF] dynamisme d'un cycliste

[PDF] le futurisme mouvement artistique

[PDF] futurisme caractéristiques

[PDF] futurisme définition

[PDF] l5a les clans majeurs pdf

[PDF] l5a pdf

[PDF] l5a 4eme edition pdf

[PDF] pendule élastique vertical

[PDF] l5a 4eme edition pdf download

[PDF] pendule elastique definition

[PDF] l5a 4 edition pdf

[PDF] legende des 5 anneaux 4eme edition pdf

[PDF] pendule élastique horizontal exercice