Cours 11 fonctions récursives, pile d’appel

sans copyright

, par Pierre

Le support du cours

Cours 11 EI
version écran
Cours 11 EI
version papier

Le programme montré en exemple

  1. /* Declaration de fonctionnalites supplementaires */
  2. #include <stdlib.h> /* EXIT_SUCCESS */
  3. #include <stdio.h> /* printf() */
  4.  
  5. /* Declarations constantes et types utilisateurs */
  6.  
  7. /* Declarations de fonctions utilisateurs */
  8. int factorielle(int n);
  9. int binomial(int n, int p);
  10. double faire_moyenne();
  11. double faire_moyenne_aux(double somme, int n);
  12. int sanscasbase(int n);
  13. int McCarthy(int x);
  14.  
  15. /* Fonction principale */
  16. int main()
  17. {
  18.     /* Declaration et initialisation des variables */
  19.     int x = 3; /* argument */
  20.     int res;   /* resultat */
  21.  
  22.     /* Pour créer un dépassement de pile
  23.     sanscasbase(1);
  24.     */
  25.  
  26.     /* 91 */
  27.     x = 23;
  28.     res =  McCarthy(x);
  29.     printf(" McCarthy(%d) = %d\n", x, res);
  30.  
  31.     /* factorielle */
  32.     res = factorielle(x);
  33.     printf("%d! = %d\n", x, res);
  34.  
  35.     /* coefficient binomial */
  36.     printf("binom(%d, %d) = %d\n", 5, 3, binomial(5, 3));
  37.  
  38.     /* moyenne */
  39.     printf("moyenne : %g\n", faire_moyenne());
  40.  
  41.     /* plus joli et plus sur */
  42.     printf("\n");
  43.     /* Valeur fonction */
  44.     return EXIT_SUCCESS;
  45. }
  46.  
  47. /* Definitions de fonctions utilisateurs */
  48. int factorielle(int n)
  49. {
  50.     int res; /* resultat */
  51.     printf("factorielle(%d) -- debut\n", n);
  52.     if (n > 1) /* cas récursif */
  53.     {
  54.         res = n * factorielle(n - 1);
  55.     }
  56.     else /* cas de base */
  57.     {
  58.         res = 1;
  59.     }
  60.     printf("factorielle(%d) -- fin\n", n);
  61.     return res;
  62. }
  63.  
  64. int binomial(int n, int p)
  65. {
  66.     printf("binom(%d, %d)\n", n, p);
  67.     if ( (p == 0) || (n == p) ) /* cas de base */
  68.     {
  69.         return 1;
  70.     }
  71.     return binomial(n - 1, p - 1) + binomial (n - 1, p);
  72. }
  73.  
  74. double faire_moyenne()
  75. {
  76.     return faire_moyenne_aux(0, 0);
  77. }
  78.  
  79. double faire_moyenne_aux(double somme, int n)
  80. {
  81.     int terme = -1;
  82.     printf("Entier positif : ");
  83.     scanf("%d", &terme);
  84.     if (terme < 0) /* case de base */
  85.     {
  86.         return somme / n; /* moyenne des termes precedents */
  87.     }
  88.     return faire_moyenne_aux(somme + terme, n + 1);
  89. }
  90.  
  91. int sanscasbase(int n)
  92. {
  93. /*  Pour prendre plus de place sur la pile :
  94.     int tab[1024] = {1};
  95. */
  96.     printf("sanscasbase(%d)\n",n);
  97.     return sanscasbase(n - 1);
  98. }
  99.  
  100. int McCarthy(int x)
  101. {
  102.     if (x > 100)
  103.     {
  104.         return (x-10);
  105.     }
  106.     else
  107.     {
  108.         return McCarthy(McCarthy(x + 11));
  109.     }
  110. }

Télécharger

Exercices

TD/TP 11 EI (non traité)
Revenu et logement, Je livre ici quelques éléments de comparaison concernant mon niveau de vie, pour couper court à quelques idées reçues, et un condensé de nombreuses (...)
Revenu et travail d’un enseignant-chercheur, Cet article complète l'article Revenu et logement, en détaillant un peu le budget de mon ménage, mon parcours d'enseignant-chercheur en terme de (...)
Cybersyn (el systemo synco), Au café, mardi 5 avril 2011, j'ai bien vu que, mis à part Antoine Allombert, personne ne connaissait l'histoire de l'extraordinaire projet chilien (...) [jpg, jpg, png]