07 Fonctions Recursives Aut 2012

  • Published on
    18-Oct-2015

  • View
    22

  • Download
    0

Transcript

  • 1 1 Programmation en C++ sous Linux Master MSI, Automne 2012 Prof Abdelaziz Bouroumi 07. Fonctions récursives Prof. Abdelaziz Bouroumi a.bouroumi@gmail.com 20/01/2013 C++ sous Linux, Master MSI, © 2013 A. Bouroumi 2 07. Fonctions récursives 07. Fonctions récursives20/01/2013 C++ sous Linux, Master MSI, © 2013 A. Bouroumi
  • 2 33 Récursivité • Moyen simple et efficace de programmer, de façon élégante, des tâches qu’on peut successivement diviser en: – Une tâche qu’on sait réaliser (cas de base), et – Une ou plusieurs autres tâches qui se définissent de la même façon que la tâche initiale. • Une fonction récursive est une fonction qui s’appelle elle-même 07. Fonctions récursives qui s appelle elle-même. • C’est un cas particulier d’application de la technique "diviser pour mieux régner" sur laquelle repose la PS. C++ sous Linux, Master MSI, © 2013 A. Bouroumi20/01/2013 44 Exemples simples 1. // fact(n)=1*2*…*(n-1)*n unsigned long fact(unsigned short n) {unsigned long fact(unsigned short n) { return n
  • 3 5 Autre exemple classique http://fr.wikipedia.org/wiki/Tours_de_Hanoï Si n=1 déplacer le disque directement de A à C; i { A B C 07. Fonctions récursivesC++ sous Linux, Master MSI, © 2013 A. Bouroumi Sinon { déplacer n-1 disques de A à B; déplacer le disque restant de A à C; déplacer les n-1 disques de B à C; } 20/01/2013 6 Cas de 3 disques (7 déplacements) 07. Fonctions récursivesC++ sous Linux, Master MSI, © 2013 A. Bouroumi20/01/2013
  • 4 7 4 disques (au moins 15 déplacements) h // iki di / iki/I T f H i 4 if 07. Fonctions récursivesC++ sous Linux, Master MSI, © 2013 A. Bouroumi http://commons.wikimedia.org/wiki/Image:Tower_of_Hanoi_4.gif 20/01/2013 8 Fonctionnement des appels récursifs cout
  • 5 99 Récursivité et répétitions • Théoriquement, tout ce qu’on peut programmer à l’aide d’une structure itérative peut l’être moyennant la récursivité t i tet inversement. • Pratiquement, le choix entre la récursivité et les structures itératives doit être fait en se basant sur des critères comme: – la complexité spatiale (mémoire) et temporelle (temps d’exécution) de l’algorithme, l li ibilité t l’élé d d 07. Fonctions récursives – la lisibilité et l’élégance du code, – l’efficacité, – la facilité de maintenance. 20/01/2013 C++ sous Linux, Master MSI, © 2013 A. Bouroumi 1010 Exemple des tours de Hanoï // Hanoï1, version récursive void Hanoi1(int n, int a, int b, int c){ if(n){ Hanoi1(n-1 a c b);Hanoi1(n-1,a,c,b); cout
  • 6 1111 Mauvaise récursivité // testFibo.cpp (Janvier 2013) #include "masterTools.hpp" unsigned n; int main(int argc, char* argv[]) {// Programme paramétré if(argc!=2) { cout
  • 7 1313 Complexité de la fonction fibo • La complexité d’un algorithme, ou du code qui l’implémente, se mesure par l’ordre de grandeur du de la fonction T(n) qui traduit la variation du temps d’exécution T en fonction de la taille des données (ici le nombre n). • Dans le cas d’algorithmes récursifs, ce calcul nécessite deux étapes: l’établissement puis la 07. Fonctions récursives nécessite deux étapes: l établissement puis la résolution de l’équation de récurrence qui traduit la façon dont l’algorithme utilise la technique « diviser pour régner. » 20/01/2013 C++ sous Linux, Master MSI, © 2013 A. Bouroumi 1414 Complexité de la fonction fibo • Equation de récurrence: • La redondance des traitements suggère une )1()2()( −+−= nTnTnT gg complexité exponentielle. • En posant , l’équation devient: • D’où: nnT α=)( 12 −− += nnn ααα 012 =−−αα  + 51 ⇒ 07. Fonctions récursives    =−= =+= )( 2 51 )(or d' nombre 2 51 2 1 ϕα ϕα 20/01/2013 C++ sous Linux, Master MSI, © 2013 A. Bouroumi
  • 8 1515 Solution de l’équation de récurrence • , avecnn BAnT 21)( αα +=  =+= 0)0( BAT 1BA   =+= + 0)1( 0)0( 21 αα BAT BAT 5 =−= BA⇒ ⇒ nnnnT 6.1 2 51 2 51 5 1)( ≈        −−    += 07. Fonctions récursives • Combien de temps faudrait-il pour calculer fibo(100) sur une machine qui réalise 109 opérations par seconde? • T(100)=1.6100/109/60/60/24/30/12/100=83 siècles 20/01/2013 C++ sous Linux, Master MSI, © 2013 A. Bouroumi 1616 Programmation dynamique • Existe-t-il de méthode plus efficace pour calculer fibo(n)? • La programmation dynamique est une technique de conception d’algorithmes qui vise à sacrifier la mémoire pour gagner en temps d’exécution. • Pour cela, on mémorise les calculs intermédiaires au lieu de les refaire. unsigned int fibo2(int n) { 07. Fonctions récursives20/01/2013 C++ sous Linux, Master MSI, © 2013 A. Bouroumi unsigned int t[n]; t[0]=0; t[1]=1; for(int i=2;i
  • 9 1717 Exercice • Ecrire une version de la fonction fibo qui ne conserve en RAM que les deux derniers termes calculés de la suite de Fibonacci. • Ecrire un programme de test de cette fonction. 07. Fonctions récursives20/01/2013 C++ sous Linux, Master MSI, © 2013 A. Bouroumi 1818 Exemple des tours de Hanoï Hanoi(n,a,c,b)=Hanoi(n-1,a,b,c)+Hanoi(1,a,c,b)+Hanoi(n-1,b,c,a) • Equation de récurrence: )1()1(2)( TnTnT +−= • • • • ⇒=== ccteOT )1()1( cnTnTcnTnT 3)2(4)()2(2)1( +−=⇒+−=− cnTnTcnTnT 7)3(8)()3(2)2( +−=⇒+−=− cnTnTcnTnT 15)4(16)()4(2)3( +−=⇒+−=− 07. Fonctions récursives • Généralisation: • Cas de base: n-i=1 ⇒ ⇒ 20/01/2013 C++ sous Linux, Master MSI, © 2013 A. Bouroumi cinTnT ii )12()(2)( −+−= ccTnT nn −+= −− 11 2)1(2)( )2()12()( nn OcnT =−=
  • 10 19 Autre méthode de résolution 07. Fonctions récursives20/01/2013 C++ sous Linux, Master MSI, © 2013 A. Bouroumi 2020 Exercices 1. En supposant que chaque déplacement élémentaire de disque demande une seconde, combien de temps faut-il pour déplacer 32 disques? 2. Calculer le temps qui nous sépare de la fin du monde selon la légende des tours de Hanoï (lorsque 64 disques seront déplacés de la tour A vers la tour C) en supposant que chaque déplacement demande une seconde. annéesannéess 08.13812/30/24/60/60/22 3232 == 07. Fonctions récursives 3. Existe-t-il de méthode plus efficace pour résoudre le problème des tours de Hanoï? 4. Peut-on savoir s’il est possible de trouver une méthode plus efficace? 20/01/2013 C++ sous Linux, Master MSI, © 2013 A. Bouroumi