Cours No 4 : Fonctions Récursives.
i. Un calcul itératif se programme par une boucle (for ou while ou repeat-until). 6. Page 7. Exemple de fonction itérative pour le calcul de factorielle (en C)
cours 2:Complexité des algorithmes récursifs
?La factorielle de N est définie en fonction de la factorielle de N-1 A l'opposé de la récursion l'itération utilise les structures de contrôle.
Cours 7 – Récursivité I Introduction II Exemples de fonctions
Exemple : Fonction factorielle. Commençons par écrire une version itérative de la fonction factorielle i.e. une fonction.
ALGO 1.1 œ Correction TD N°5.
Calcul de la factorielle d'un entier naturel (avec une structure itérative « Pour »). Variables n : entier factorielle : entier indice : entier.
Récursivité
4/10/2017 1.1 Fonction factorielle. La fonction factorielle fac peut être définie ainsi : ... Écrire une version itérative de la suite de Fibonacci.
Algorithmique et programmation avancée
Une fonction récursive est une fonction qui fait appel à Variante de la fonction factorielle ... Factorielle récursif ? itératif int fact(int n).
Chapitre 18 Algorithmique de base
La méthode itérative nécessite l'utilisation de variables locales pour effectuer le calcul demandé. fonction factorielle(1) a été appelée en rendant 1.
Cours No 4 : Premi`eres Fonctions Récursives 1 Fonctions récursives
Un calcul itératif se programme par une boucle (for ou while ou repeat-until). Exemple de fonction itérative pour le calcul de factorielle (en C).
Correction TP de programmation no3 - Fonctions et procédures
Exercice 1. Fonction factorielle et coefficients du binôme de Newton. La fonction pour calculer la factorielle d'un entier est donnée dans le fichier binome.cpp
RÉCURSIVITÉ PLAN CALCUL DE FACTORIELLE CODAGE ITÉRATIF
Une fonction récursive n'a pas forcément un argument numérique. def reverse(s): if s == "": return s else: return reverse(
[PDF] Programmation itérative/récursive - limsi
La fonction factorielle - Cours S2-1 La valeur de la fonction factorielle d'un nombre entier n est le Itératif i = 1 res = 1 while( i
[PDF] Cours No 4 : Fonctions Récursives - LIRMM
Exemple de fonction itérative pour le calcul de factorielle (en C) 1 int fact(n) { // n entier 2 int i = 0; 3 int result = 1; 4 while (i < n){
[PDF] RÉCURSIVITÉ PLAN CALCUL DE FACTORIELLE CODAGE ITÉRATIF
On écrit une fonction récursive appartient testant l'appartenance ou non d'un objet x à une liste L def appartient(L x): if len(L) == 0: return False else:
[PDF] Chapitre 18 Algorithmique de base
Calcul factoriel ? Une approche itérative int factorielle(int i){ int resultat; for(resultat=1;i>1;i--) resultat*=i; return(resultat);
[PDF] cours 2:Complexité des algorithmes récursifs - Esentn
?La factorielle de N est définie en fonction de la factorielle de N-1 A l'opposé de la récursion l'itération utilise les structures de contrôle
[PDF] ALGO 11 œ Correction TD N°5
Calcul de la factorielle d'un entier naturel (avec une structure itérative « Pour ») Variables n : entier factorielle : entier indice : entier
Fonction itérative pour factorielle en PHP - WayToLearnX
15 avr 2020 · Dans ce tutoriel nous allons découvrir comment calculer le factorielle de façon itérative en utilisant la boucle for en PHP Exemple: Fonction
[PDF] TP Informatique no 3 Récursivité et programmation dynamique
La définition récursive de fonctions est possible en Python Illustrons ce procédé avec la fonction factorielle 1 def factrec(n): 2
Récursif et itératif : factorielle boucle en récursif - France-IOI
Il est cependant possible de donner une définition récursive de la fonction factorielle : La factorielle d'un nombre N vaut 1 si N est égal à 0 et N multiplié
[PDF] Correction TP de programmation no3
Fonction factorielle et coefficients du binôme de Newton La fonction pour calculer la factorielle d'un entier est donnée dans le fichier binome cpp
Comment calculer la complexité d'un algorithme récursif ?
La complexité d'un algorithme récursif se fait par la résolution d'une équation de récurrence en éliminant la récurrence par substitution de proche en proche.Comment écrire un algorithme récursif ?
On se propose de reprendre le jeu du Plus-Moins, et d'en écrire un algorithme récursif. Principe : le joueur choisit mentalement un nombre entier entre deux bornes, fixées préala- blement (n et p par exemple), et l'algorithme proc? alors par élimination dichotomique.Comment calculer le factoriel d'un nombre algorithme ?
Prenons par exemple le calcul de la factorielle d'un nombre, une fonction mathématique qui pour une valeur entière positive, retourne le produit de tous les entiers entre 1 et cette valeur. Pour une valeur nulle, la fonction retourne 1. Par exemple, la factorielle de 5, que l'on note "5", vaut 1*2*3*4*5 = 120.- Définition : la programmation récursive est une technique de programmation qui remplace les instructions de boucle (while, for, etc.) par des appels de fonction. et il faut appeler boucle(0). return (s) ; //Pour sommeRec(0, s), le calcul est immédiat } On lance x = sommeRec(0, 100).
RÉCURSIVITÉ
Théorie et pratique
Walter APPELCODAGE ITÉRATIF
n! =n? i=1i itératif#Définition itérative deffactorielle(n):p = 1 foriinrange (1, n + 1):p*= ireturnpWALTERAPPELRÉCURSIVITÉ5 / 45WALTERAPPELRÉCURSIVITÉ1 / 45PLAN1PREMIÈRE APPROCHEItératif vs. récursif
Les trois lois de la récursivité
Autres exemples
2UN PEU DE THÉORIETerminaison
Pourquoi c"est mal
3QUELQUES EXEMPLES CLASSIQUESDansNNNFlocon de von Koch
Courbe de Bolzano
Tri et tableaux
n! =n? i=1iitératif n! =?1 sin=0,
n·(n-1)!sinon.récursif WALTERAPPELRÉCURSIVITÉ4 / 45CODAGE ITÉRATIF n! =n? i=1i itératif#Définition itérative deffactorielle(n):p = 1 foriinrange (1, n + 1):p *= ireturnpWALTERAPPELRÉCURSIVITÉ5 / 45CODAGE RÉCURSIF
" Pour calculer 5!, je demande à mon voisin le résultat de 4!, je multiplie par 5 et j"annonce le résultat. »n! =?1 sin=0,
n·(n-1)!sinon.récursif#Définition récur sivesimpledeffacto(n):ifn <= 1:return1else:returnn*facto(n - 1)WALTERAPPELRÉCURSIVITÉ6 / 45LES TROIS LOIS DE LA RÉCURSIVITÉLoi 1
Une fonction récursive gère des cas de base
Loi 2 Une fonction récursive s"appelle elle-même dans un cas dif- férentLoi 3 La suite des appels doit nécessairement aboutir à un cas de baseWALTERAPPELRÉCURSIVITÉ7 / 45DESCENTE INFINIEIl ne faut surtout pas oublier la gestion du cas de base
sous peine de provoquer unedescente infinie!C"est une erreur fréquente...Dans la vraie vie, il n"y a évidemment jamais de véritable descente infinie. La pile de récursion a une taille finie.Lorsqu"elle déborde, on obtient le message suivant :RuntimeError : maximum recursion depth exceeded
incomparisonOn peut modifier la taille de la pile de récursion (de taille ≈1000 par défaut) :importsyssys.setrecursionlimit(100000) WALTERAPPELRÉCURSIVITÉ8 / 45Modifions légèrement notre programme : deffacto (n):ifn <= 1:return1else:print(" ==" *n+" >appeldefacto( { } ) " . format(n-1))m = n *facto (n-1)print(" --"*n+" >sortiedefacto( { } ) " . format(n-1))returnm»> facto(5)5! =
==========> appel de facto(4)=5×4! ========> appel de facto(3)=5×(4×3!) ======> appel de facto(2)=5×(4×(3×2!)) ====> appel de facto(1)=5×(4×(3×(2×1!))) ---> sortie de facto(1)=5×(4×(3×(2×1))) ----> sortie de facto(2)=5×(4×(3×2)) -----> sortie de facto(3)=5×(4×6) -------> sortie de facto(4)=5×24120=120WALTERAPPELRÉCURSIVITÉ9 / 45
EXERCICES
Pour calculerxn, on peut remarquer que
x n=? (x2)n/2sinest pair, x·(x2)(n-1)/2sinest impair.Écrire un algorithme, puis un programme en Python,permettant de calculer récursivementxn.Écrire un algorithmenon récursifqui calculexnselon la
même méthode!WALTERAPPELRÉCURSIVITÉ10 / 45THERE ARE MORE THINGS...Une fonction récursive n"a pas forcément un argument
numérique.defreverse(s):ifs ==" ":returnselse:returnreverse(s[1:]) + s[0]reverse(" t ruc" ) =reverse(" ruc")+"t " = [reverse(" uc")+"r"]+"t " = [{reverse(" c")+"u"}+"r"]+"t " = [{reverse(" " )+"c"+"u"}+"r"]+"t " #attention ici != [{" " +"c"+"u"}+"r"]+"t "
c urtDe plus, elle peut s"appeler plusieurs fois!
WALTERAPPELRÉCURSIVITÉ11 / 45PGCD DE DEUX NOMBRES#PGCDde deux entiers.defpgcd(a, b)ifb == 0:returnaelse:returnpgcd(b, a % b)Cette manière de programmer retranscrit très fidèlement
l"algorithme d"Euclide, et est particulièrement simple àécrire!Terminaison: à chaque appel, on a
0?a%b et arrêt lorsqueb=0.??Validité: on a transcrit l"algorithme d"Euclide en renvoyant le dernier reste non nul.??WALTERAPPELRÉCURSIVITÉ12 / 45PGCD D"UNE LISTE On utilise le fait que
PGCD(?0,?1,...,?n) =PGCD?
0,? PGCD(?1,...,?n)??
.#PGCDd"une liste L de nombres entiersdefPGCD(L)iflen (L) == 1 :returnL[0]else:returnpgcd(L[0], PGCD(L[1:]))
Ici, les arguments sont des objets, et la récursivité se fait avec une taille décroissante d"objets. WALTERAPPELRÉCURSIVITÉ13 / 45
UNE MALADRESSE
L"algorithme de Syracuse part d"un entieru0?1 et définit une suite(un)n?0par la relation de récurrence u n+1=? u n/2 siunest pair 3un+1 sinondefsyracuse (u0, k):#Calcule le k-ième terme ifk == 0:returnu0else:ifsyracuse (u0, k-1) % 2 == 0:returnsyracuse (u0, k-1) / / 2else:returnsyracuse (u0, k-1)*3 + 1WALTERAPPELRÉCURSIVITÉ14 / 45UNE MALADRESSE
L"algorithme de Syracuse part d"un entieru0?1 et définit une suite(un)n?0par la relation de récurrence u n+1=? u n/2 siunest pair 3un+1 sinondefsyracuse (u0, k):#Calcule le k-ième terme ifk == 0:returnu0else:a = syracuse (u0, k-1)ifa % 2 == 0:returna / / 2else:returna*3 + 1
On trace, en fonction de l"indicende la suite, lelogarithme du temps nécessaire à calculerun:46810121416182010 8 6 4 2 0 La pente estα≈23
≈ln2, donc on conjecture C(n) = Θ(eαn)= Θ(2n).WALTERAPPELRÉCURSIVITÉ16 / 45LE PROBLÈME DE LA TERMINAISON Toute suite de Syracuse est réputée finir par " boucler » 1→4→2→1→4→2→1→4→2→1→ ···defsuivant (n):ifn <= 1 :return1else:ifn % 2 == 0 :returnn / / 2else:return3*n + 1defcte (n):ifn == 1 :return1else:returncte ( suivant (n))
Conjecture:???est égale à 1 surNNN.WALTERAPPELRÉCURSIVITÉ17 / 45 DÉFINITION FORMELLE
On a besoin d"un ensemble bien ordonné (toute partie non vide admet un plus petit élément)E, n"admettant pas de suite décroissante infinie;(typiquement,NNN)et d"un sous-ensembleBdeE, appeléensemble des cas de base.Une fonctionfestrécursivesi elle s"écrit sous la forme
f(x) =??(x)six? B x,f?α1(x)?,...,f?αp(x)?? sinonThéorème Si lesαk(x)sont " strictement plus petits » que x, alors l"appel récursif se termine nécessairement. WALTERAPPELRÉCURSIVITÉ19 / 45EXEMPLE DE LA FACTORIELLE Une fonctionFest récursive si elle s"écrit sous la forme f(x) =??(x)six? B x,f?α1(x)?,...,f?αp(x)?? sinon f(n) =1 sin? {0}.f(n) =n·f?n-1???? 1(n)? Φ(n,f(α1(n)))Lorsque l"on travaille dansNNN, on a classiquementα(n)de la formen-1,?n/2?,...Sixest un tableau,α(x)pourra être une partie (stricte!) du tableau. WALTERAPPELRÉCURSIVITÉ20 / 45CALCULER36FOIS LA MÊME CHOSE Définissons
u n=? 1 sin=0
nu n-1+u2n-1sinon.Écrire un programme itératif calculantun.Écrire un programmerécursifcalculantun.Quelles sont leurs complexités?
WALTERAPPELRÉCURSIVITÉ21 / 45CALCULER36FOIS LA MÊME CHOSE Définissons la suite de Fibonacci par
?u 0=1 u 1=1 u n+2=un+1+un?n?0WALTERAPPELRÉCURSIVITÉ22 / 45 CALCULER36FOIS LA MÊME CHOSEdeffibo(n):ifn == 1orn == 2:return1else:returnfibo(n-1) + fibo(n-2)???????appelle???????et???????.
mais...???????appelle???????et??????? or...???????appelle???????et???????etc. ... et l"on peut noter que???????va être appelé deux fois, avec tout ce qu"il s"ensuit! WALTERAPPELRÉCURSIVITÉ23 / 45CALCULER36FOIS LA MÊME CHOSE Sous forme plus schématique :5
43
3221
211010
10 WALTERAPPELRÉCURSIVITÉ24 / 45LE PROBLÈME DU TEMPSLes calculs intermédiaires sont stockés dans une pile.
La pile peut grossir de manière intempestive, comme la profondeur de l"arbre de récursion, mais surtout passe son temps à êtreempilée et dépilée.Le nombre d"appels varie commendans l"algorithme calculantn!? " comme » eαndans Fibonacci (et plus précisément en Θ(ρn), où
ρ=1+⎷5
2 ≈1,618... est le nombre d"or)... 50≈28·109ρ100≈8·1020?
... voire pire.WALTERAPPELRÉCURSIVITÉ25 / 45EXEMPLES DANSNNNCalcul den!, dean, de la suite de Fibonacci, de Syracuse...Nombres de Catalan :C0:=1 etCn:=n-1?
k=0C kCn-1-k.Décomposition d"un entier en base 2 : 42=32????
2 5+8????
2 3+2=101010.Dénombrement (nombre de surjections, coefficients du
binôme...) WALTERAPPELRÉCURSIVITÉ27 / 45
FLOCON DE VONKOCH
Unebranche de von Kochest un objet constitué...de quatre branches de von Koch plus petites (1/3), disposées ainsi :Par conséquent, il est aussi comme ceci :
WALTERAPPELRÉCURSIVITÉ28 / 45FLOCON DE VONKOCH Mathématiquement, on a affaire à unpoint fixe(il existe, il est unique!) d"une certaine transformation... WALTERAPPELRÉCURSIVITÉ29 / 45PROGRAMMER VONKOCHdefUnPas(x ,y , r , arg ):returnx+r*cos (arg) , y+r*sin (arg)defVonKoch(n,x0 ,y0 , r , theta ):ifn == 0:#État de base !(xp ,yp) = UnPas(x0 ,y0 , r , theta )
plot ([ x0 ,xp ] ,[y0 ,yp] , color= b lack else:x ,y = x0 ,y0 VonKoch(n-1,x ,y , r /3 , theta )x ,y = UnPas(x ,y , r /3 , theta ) VonKoch(n-1,x ,y , r /3 , theta+pi /3)x ,y = UnPas(x ,y , r /3 , theta+pi /3) VonKoch(n-1,x ,y , r /3 , theta-pi /3)x ,y = UnPas(x ,y , r /3 , theta-pi /3)VonKoch(n-1,x ,y , r /3 , theta )WALTERAPPELRÉCURSIVITÉ30 / 45FLOCON DE VONKOCHWALTERAPPELRÉCURSIVITÉ31 / 45
LA COURBE DEBOLZANO
Un des premiers exemples de fonctions continues sur[0;1] mais dérivable en aucun point a été donné par Bolzano. Cette fonctionfest la limite simple de la suite(fn)n?0dont les graphes sont obtenus itérativement en brisant chaque ligne selon le schéma suivant :?-→ On obtient, en partant de la fonction identité sur[0;1], la séquence ci-après WALTERAPPELRÉCURSIVITÉ32 / 45LA COURBE DEBOLZANOWALTERAPPELRÉCURSIVITÉ33 / 45TRI FUSION On sait fusionner deux listes en temps linéaire.Je séparer ma liste en deux... ... je demande à deux grouillots de me les trier... ... puis je les fusionne. Chaque grouillot se cherche deux grouillots pour trier la moitié de sa propre liste.Chaque étape demandera une fusion linéaire, et il y a environlog2nétapes.La complexité du tri fusion est ennlog2nce qui est, asymptotiquement, optimal (comme déjà vu...). L"ennui dans Fibonacci récursif-naïf, c"est qu"on calcule plein de fois la même chose! L"idée est donc deretenirces calculs intermédiaires, en les stockant par exemple dans un tableau.L = [0 ,1] + [None] *200#L est définie globalementdeffibmem(n):ifL[n] == None:#F nn"a pas été calculéL[n] = fibmem(n-1) + fibmem(n-2)returnL[n]#Dans tous les cas Python n"arrive pas à calculerfibo(50)...mais effectue
fibmem(100)en une fraction de seconde.WALTERAPPELRÉCURSIVITÉ36 / 45 Dans le même esprit, on peut utiliser une fonction récursive auxiliaire :defFibo(n)L = [0,1] + [None] *(n-1)#La taille est adaptée au problème deffifi(k)ifL[k] == None:L[k] = fifi(k-1) + fifi(k-2) returnL[k]returnfifi(n)WALTERAPPELRÉCURSIVITÉ37 / 45ABAISSER L"ORDRE DE RÉCURSIONSi l"onvectorialisele problème, cela transforme la suite
récurrente d"ordre 2 en une suite récurrente d"ordre 1. L"arbre des appels récursifs n"explose plus : ce n"est plus qu"un tronc!On pose, pour toutn?N?, X n=?Fn F n-1? et X n+1=?1 1 1 0? X n.WALTERAPPELRÉCURSIVITÉ38 / 45CE QUI EST BIENC"est facile à écrire, c"est souvent la façon la plus
naturelle(von Koch...).Lapreuve decorrectionest en général facile à rédiger.On ne sait pas ce que fait l"ordinateurderrière les
instructions simples (baguette magique)! WALTERAPPELRÉCURSIVITÉ40 / 45CE QUI ESTM ALC"est facile à écrire, c"est souvent la façon la plus
naturelle(von Koch...).Explosion de la complexité en temps; de même, la pile peut exploser!Lapreuve decorrectionest en général facile à rédiger.
Lapreuve determinaisonest triviale... ou très difficile.On ne sait pas ce que fait l"ordinateurderrière les
instructions simples (baguette magique)! WALTERAPPELRÉCURSIVITÉ41 / 45
PASSAGE PAR VALEURS OU PAR ADRESSE
l"appartenance, ou non, d"un objetxà une listeL.defappartient(L, x):iflen (L) == 0:returnFalseelse:returnL[0] == xorappartient(L[1:], x)Nota bene :L"algorithme se termineaussitôtquexest trouvé
dansL, grâce à l"évaluation paresseusede l"opérateur??.>>> 1+1 == 2or1/0 = 42True Mais :Explosion de la pile et du temps de calcul!! En effet, on empile à chaque étape unenouvelleliste, qui consomme du temps et de la mémoire. WALTERAPPELRÉCURSIVITÉ42 / 45PASSAGE PAR VALEURS OU PAR ADRESSE Au lieu de passer comme argument lavaleurde la liste (?????est un nouvel objet, obtenu parslicing), on peut se contenter de ne passer que l"adresse:defappart2(L, x, i):n =len(L)ifi == n:returnFalseelse:returnx == L[i]orappart2(L, x, i+1)(C"est Python qui se charge de comprendre que seule
l"adresse deLcompte...)WALTERAPPELRÉCURSIVITÉ43 / 45PASSAGE PAR VALEURS OU PAR ADRESSEimportsysfromtimeimporttimesys . setrecursionlimit (10
**5)L = [1] *(10**4)t0 = time () appartient (L,0) t1 = time () print(t1-t0 )#1.398 t0 = time () appart2 (L,0 ,0) t1 = time () print(t1-t0 )#0.0130 WALTERAPPELRÉCURSIVITÉ44 / 45WALTERAPPELRÉCURSIVITÉ45 / 45quotesdbs_dbs44.pdfusesText_44
On utilise le fait que
PGCD(?0,?1,...,?n) =PGCD?
0,?PGCD(?1,...,?n)??
.#PGCDd"une liste L de nombres entiersdefPGCD(L)iflen (L) == 1 :returnL[0]else:returnpgcd(L[0], PGCD(L[1:]))
Ici, les arguments sont des objets, et la récursivité se fait avec une taille décroissante d"objets.WALTERAPPELRÉCURSIVITÉ13 / 45
UNE MALADRESSE
L"algorithme de Syracuse part d"un entieru0?1 et définit une suite(un)n?0par la relation de récurrence u n+1=? u n/2 siunest pair3un+1 sinondefsyracuse (u0, k):#Calcule le k-ième terme ifk == 0:returnu0else:ifsyracuse (u0, k-1) % 2 == 0:returnsyracuse (u0, k-1) / / 2else:returnsyracuse (u0, k-1)*3 + 1WALTERAPPELRÉCURSIVITÉ14 / 45UNE MALADRESSE
L"algorithme de Syracuse part d"un entieru0?1 et définit une suite(un)n?0par la relation de récurrence u n+1=? u n/2 siunest pair3un+1 sinondefsyracuse (u0, k):#Calcule le k-ième terme ifk == 0:returnu0else:a = syracuse (u0, k-1)ifa % 2 == 0:returna / / 2else:returna*3 + 1
On trace, en fonction de l"indicende la suite, lelogarithme du temps nécessaire à calculerun:46810121416182010 8 6 4 2 0La pente estα≈23
≈ln2, donc on conjecture C(n) = Θ(eαn)= Θ(2n).WALTERAPPELRÉCURSIVITÉ16 / 45LE PROBLÈME DE LA TERMINAISON Toute suite de Syracuse est réputée finir par " boucler »1→4→2→1→4→2→1→4→2→1→ ···defsuivant (n):ifn <= 1 :return1else:ifn % 2 == 0 :returnn / / 2else:return3*n + 1defcte (n):ifn == 1 :return1else:returncte ( suivant (n))
Conjecture:???est égale à 1 surNNN.WALTERAPPELRÉCURSIVITÉ17 / 45DÉFINITION FORMELLE
On a besoin d"un ensemble bien ordonné (toute partie non vide admet un plus petit élément)E, n"admettant pas de suite décroissante infinie;(typiquement,NNN)et d"unsous-ensembleBdeE, appeléensemble des cas de base.Une fonctionfestrécursivesi elle s"écrit sous la forme
f(x) =??(x)six? B x,f?α1(x)?,...,f?αp(x)?? sinonThéorème Si lesαk(x)sont " strictement plus petits » que x, alors l"appel récursif se termine nécessairement. WALTERAPPELRÉCURSIVITÉ19 / 45EXEMPLE DE LA FACTORIELLE Une fonctionFest récursive si elle s"écrit sous la forme f(x) =??(x)six? B x,f?α1(x)?,...,f?αp(x)?? sinon f(n) =1 sin? {0}.f(n) =n·f?n-1???? 1(n)? Φ(n,f(α1(n)))Lorsque l"on travaille dansNNN, on a classiquementα(n)de la formen-1,?n/2?,...Sixest un tableau,α(x)pourra être une partie (stricte!) du tableau. WALTERAPPELRÉCURSIVITÉ20 / 45CALCULER36FOIS LA MÊME CHOSEDéfinissons
u n=?1 sin=0
nun-1+u2n-1sinon.Écrire un programme itératif calculantun.Écrire un programmerécursifcalculantun.Quelles sont leurs complexités?
WALTERAPPELRÉCURSIVITÉ21 / 45CALCULER36FOIS LA MÊME CHOSEDéfinissons la suite de Fibonacci par
?u 0=1 u 1=1 u n+2=un+1+un?n?0WALTERAPPELRÉCURSIVITÉ22 / 45CALCULER36FOIS LA MÊME CHOSEdeffibo(n):ifn == 1orn == 2:return1else:returnfibo(n-1) + fibo(n-2)???????appelle???????et???????.
mais...???????appelle???????et??????? or...???????appelle???????et???????etc. ... et l"on peut noter que???????va être appelé deux fois, avec tout ce qu"il s"ensuit! WALTERAPPELRÉCURSIVITÉ23 / 45CALCULER36FOIS LA MÊME CHOSESous forme plus schématique :5
433221
211010
10WALTERAPPELRÉCURSIVITÉ24 / 45LE PROBLÈME DU TEMPSLes calculs intermédiaires sont stockés dans une pile.
La pile peut grossir de manière intempestive, comme la profondeur de l"arbre de récursion, mais surtout passe son temps à êtreempilée et dépilée.Le nombre d"appels varie commendans l"algorithme calculantn!? " comme » eαndans Fibonacci (et plus précisément enΘ(ρn), où
ρ=1+⎷5
2 ≈1,618... est le nombre d"or)...50≈28·109ρ100≈8·1020?
... voire pire.WALTERAPPELRÉCURSIVITÉ25 / 45EXEMPLES DANSNNNCalcul den!, dean, de la suite de Fibonacci, de Syracuse...Nombres de Catalan :C0:=1 etCn:=n-1?
k=0C kCn-1-k.Décomposition d"un entier en base 2 :42=32????
25+8????
23+2=101010.Dénombrement (nombre de surjections, coefficients du
binôme...)WALTERAPPELRÉCURSIVITÉ27 / 45
FLOCON DE VONKOCH
Unebranche de von Kochest un objet constitué...de quatrebranches de von Koch plus petites (1/3), disposées ainsi :Par conséquent, il est aussi comme ceci :
WALTERAPPELRÉCURSIVITÉ28 / 45FLOCON DE VONKOCH Mathématiquement, on a affaire à unpoint fixe(il existe, il est unique!) d"une certaine transformation...WALTERAPPELRÉCURSIVITÉ29 / 45PROGRAMMER VONKOCHdefUnPas(x ,y , r , arg ):returnx+r*cos (arg) , y+r*sin (arg)defVonKoch(n,x0 ,y0 , r , theta ):ifn == 0:#État de base !(xp ,yp) = UnPas(x0 ,y0 , r , theta )
plot ([ x0 ,xp ] ,[y0 ,yp] , color= b lack else:x ,y = x0 ,y0 VonKoch(n-1,x ,y , r /3 , theta )x ,y = UnPas(x ,y , r /3 , theta ) VonKoch(n-1,x ,y , r /3 , theta+pi /3)x ,y = UnPas(x ,y , r /3 , theta+pi /3)VonKoch(n-1,x ,y , r /3 , theta-pi /3)x ,y = UnPas(x ,y , r /3 , theta-pi /3)VonKoch(n-1,x ,y , r /3 , theta )WALTERAPPELRÉCURSIVITÉ30 / 45FLOCON DE VONKOCHWALTERAPPELRÉCURSIVITÉ31 / 45
LA COURBE DEBOLZANO
Un des premiers exemples de fonctions continues sur[0;1] mais dérivable en aucun point a été donné par Bolzano. Cette fonctionfest la limite simple de la suite(fn)n?0dont les graphes sont obtenus itérativement en brisant chaque ligne selon le schéma suivant :?-→ On obtient, en partant de la fonction identité sur[0;1], la séquence ci-après WALTERAPPELRÉCURSIVITÉ32 / 45LA COURBE DEBOLZANOWALTERAPPELRÉCURSIVITÉ33 / 45TRI FUSION On sait fusionner deux listes en temps linéaire.Je séparer ma liste en deux... ... je demande à deux grouillots de me les trier... ... puis je les fusionne. Chaque grouillot se cherche deux grouillots pour trier la moitié de sa propre liste.Chaque étape demandera une fusion linéaire, et il y a environlog2nétapes.La complexité du tri fusion est ennlog2nce qui est, asymptotiquement, optimal (comme déjà vu...). L"ennui dans Fibonacci récursif-naïf, c"est qu"on calcule plein de fois la même chose! L"idée est donc deretenirces calculs intermédiaires, en les stockant par exemple dans un tableau.L = [0 ,1] + [None]*200#L est définie globalementdeffibmem(n):ifL[n] == None:#F nn"a pas été calculéL[n] = fibmem(n-1) + fibmem(n-2)returnL[n]#Dans tous les cas Python n"arrive pas à calculerfibo(50)...mais effectue
fibmem(100)en une fraction de seconde.WALTERAPPELRÉCURSIVITÉ36 / 45 Dans le même esprit, on peut utiliser une fonction récursive auxiliaire :defFibo(n)L = [0,1] + [None] *(n-1)#La taille est adaptée au problème deffifi(k)ifL[k] == None:L[k] = fifi(k-1) + fifi(k-2)returnL[k]returnfifi(n)WALTERAPPELRÉCURSIVITÉ37 / 45ABAISSER L"ORDRE DE RÉCURSIONSi l"onvectorialisele problème, cela transforme la suite
récurrente d"ordre 2 en une suite récurrente d"ordre 1. L"arbre des appels récursifs n"explose plus : ce n"est plus qu"un tronc!On pose, pour toutn?N?, X n=?Fn F n-1? et X n+1=?1 1 1 0? Xn.WALTERAPPELRÉCURSIVITÉ38 / 45CE QUI EST BIENC"est facile à écrire, c"est souvent la façon la plus
naturelle(von Koch...).Lapreuve decorrectionest en général facile à rédiger.On ne sait pas ce que fait l"ordinateurderrière les
instructions simples (baguette magique)!WALTERAPPELRÉCURSIVITÉ40 / 45CE QUI ESTM ALC"est facile à écrire, c"est souvent la façon la plus
naturelle(von Koch...).Explosion de la complexité entemps; de même, la pile peut exploser!Lapreuve decorrectionest en général facile à rédiger.
Lapreuve determinaisonest triviale... ou très difficile.On ne sait pas ce que fait l"ordinateurderrière les
instructions simples (baguette magique)!WALTERAPPELRÉCURSIVITÉ41 / 45
PASSAGE PAR VALEURS OU PAR ADRESSE
l"appartenance, ou non, d"un objetxà une listeL.defappartient(L, x):iflen (L) == 0:returnFalseelse:returnL[0] == xorappartient(L[1:], x)Nota bene :L"algorithme se termineaussitôtquexest trouvé
dansL, grâce à l"évaluation paresseusede l"opérateur??.>>> 1+1 == 2or1/0 = 42True Mais :Explosion de la pile et du temps de calcul!! En effet, on empile à chaque étape unenouvelleliste, qui consomme du temps et de la mémoire. WALTERAPPELRÉCURSIVITÉ42 / 45PASSAGE PAR VALEURS OU PAR ADRESSE Au lieu de passer comme argument lavaleurde la liste (?????est un nouvel objet, obtenu parslicing), on peut secontenter de ne passer que l"adresse:defappart2(L, x, i):n =len(L)ifi == n:returnFalseelse:returnx == L[i]orappart2(L, x, i+1)(C"est Python qui se charge de comprendre que seule
l"adresse deLcompte...)WALTERAPPELRÉCURSIVITÉ43 / 45PASSAGE PAR VALEURS OU PAR ADRESSEimportsysfromtimeimporttimesys . setrecursionlimit (10
**5)L = [1] *(10**4)t0 = time () appartient (L,0) t1 = time () print(t1-t0 )#1.398 t0 = time () appart2 (L,0 ,0) t1 = time () print(t1-t0 )#0.0130 WALTERAPPELRÉCURSIVITÉ44 / 45WALTERAPPELRÉCURSIVITÉ45 / 45quotesdbs_dbs44.pdfusesText_44[PDF] operation factorielle
[PDF] différence entre algorithme itératif et algorithme récursif
[PDF] expression de couturiere
[PDF] fonction récursive
[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
