TD 2: Fonctions, Recursivité

Rappels

Exercice 1: Fonctions, #include, déclarations

  1. Écrire un fichier 1.1.cc contenant uniquement une fonction int LaSolution(int x) qui renvoie toujours x + 42. Vérifiez-la avec le fichier 1.1.main.cc suivant (donc en faisant g++ 1.1.main.cc && ./a.out):
    #include <iostream>
    using namespace std;
    
    #include "1.1.cc"
    
    int main() {
      cout << LaSolution(3) << endl;
      cout << LaSolution(-1) << endl;
    }
    RENDU: 1.1.cc

  2. Copiez 1.1.main.cc dans 1.2.main.cc puis modifiez ce dernier en enlevant #include "1.1.cc", et tentez de le compiler manuellement avec g++. Comment faire pour que ça marche?
    Indices:
    RENDUS: 1.2.main.cc et un fichier 1.2.txt contenant la ligne de commande pour compiler

Exercice 2: Récursivité (ou pas), stack overflow

On dit qu'une fonction est récursive quand elle s'appelle elle-même.
  1. Écrire un fichier 2.1.cc contenant juste une fonction FactorielleMod qui prend un entier n et qui calcule n! modulo 1000000007.
    La fonction devra être récursive: sans utiliser de boucle for, while ou do.
    Attention aux overflow: un entier int ne va pas au-dessus de 231-1. Un entier long va jusqu'à 263-1 par contre.

    Testez-le et corrigez-le avec ce fichier main.cc, comme avant.
    Note: 100! mod 1000000007 = 437918130.
    #include <iostream>
    using namespace std;
    
    #include "2.1.cc"
    
    int main() {
      cout << "Entrez un entier n: ";
      int n;
      cin >> n;
      cout << FactorielleMod(n) << endl;
    }
    RENDU: 2.1.cc

  2. Essayez avec n=10000000 (10 millions). Que voyez-vous?

    C'est un stack overflow! Pour s'en sortir, deux solutions:
    1. Augmenter la taille maximum de la pile (stack). Cf aide en ligne:
      • Ajouter #include <sys/resource.h> dans votre main
      • Et au début de la fonction main(), ajoutez ces lignes:
        struct rlimit r;
        getrlimit(RLIMIT_STACK, &r);
        r.rlim_cur = 100 << 20;  // 100 MB.
        setrlimit(RLIMIT_STACK, &r);
      C'est à éviter en général, sauf cas très rare.

    2. Transformer votre code récursif en code itératif, qui est bien plus dans l'esprit de C++:

      Recodez une autre version FactorielleMod2(n) dans un nouveau fichier 2.2.cc, sans récursion mais avec une boucle for. Vous pouvez le tester avec le main d'avant, sans oublier de changer le 2.1.cc en 2.2.cc et FactorielleMod en FactorielleMod2.

      RENDU: 2.2.cc

  3. Optionel (non compabilisé, à faire en fin de TD): vous pouvez comparer les vitesses de FactorielleMod() et FactorielleMod2(), par exemple, en calculant la somme de n! pour n allant de 1 à 10000).
    Que cela donne-t-il?.

  4. Écrivez dans un fichier 2.4.cc une fonction récursive FiboRec qui calcule le n-ième terme de la suite de Fibonacci, donnée par:
    Fn = Fn-1 + Fn-2 et F0 = F1 = 1.
    Essayez de calculer FiboRec(60). Que se passe-t'il? Pourquoi?

    RENDU: 2.4.cc

  5. Écrivez dans un fichier 2.5.cc une fonction FiboIter qui calcule Fn, mais itérativement cette fois. Changez sa valeur de retour en double.
    Comparez les valeurs de FiboIter et FiboRec pour de petits nombres, puis essayez de calculer FiboIter(60), puis FiboIter(1000).

    RENDU: 2.5.cc

  6. Écrivez dans un fichier 2.6.cc une fonction récursive Pgcd qui calcule le plus grand diviseur commun entre deux long.

    Vérifiez que Pgcd(2250, 1000) = 250; et essayez Pgcd(129387194869817412L, 19827398170419240L) et Pgcd(1000000007, 1). Si ca ne marche pas (ou prend trop de temps), essayez un autre algorithme plus efficace!

    RENDUS: 2.6.cc et une brève explication (dans un fichier 2.6.txt) de pourquoi on a pas le problème de stack overflow avec cette fonction