Cours 11 fonctions récursives, pile d’appel

sans copyright

, par Pierre

Le support du cours

PDF - 410 ko
Cours 11 EI
version écran
PDF - 296 ko
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

PDF - 302.7 ko
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]